Strings in the Tree#2925
Given a tree, which is a connected graph with no cycles. Each edge in the tree is labeled with a lowercase Latin letter. For any two vertices, there is exactly one simple path between them: a path through the tree's edges that visits each vertex at most once. A string is assigned to each such path by reading the letters on the edges along the path. The path can be traversed starting from either of its endpoints.
You are given a string . Does there exist a simple path in the tree along which reading the edge labels yields this string?
The length of the string and the size of the tree do not exceed 3\cdot 10^5.
The first line contains the string . The second line contains the number of vertices in the tree . Each of the following n-1 lines describes an edge of the tree in the format , where and are vertices of the tree, and is the character on the edge between them.
Print on the first line if such a path exists, and otherwise.
If the path exists, also print the pair of vertices between which the path forms the given string.
Example 1