Rows in the Tree
Given a tree, which is a connected graph without cycles, each edge is labeled with a lowercase Latin letter. In this tree, there is exactly one simple path between any two vertices, meaning a path that traverses the tree's edges without visiting any vertex more than once. Each path corresponds to a string formed by reading the letters on the edges as you traverse the path. The path can be traversed starting from either of its endpoints.
You are provided with a string S. Your task is to determine if this string corresponds to any simple path in the given tree.
The length of the string and the number of vertices in the tree do not exceed 3·10^5.
Input
The first line contains the string s. The second line contains the number of vertices in the tree n. The following n-1 lines describe the tree's edges in the format u, v, c, where u and v are vertices of the tree, and c is the character on the edge connecting them.
Output
On the first line, print YES if such a path exists, and NO otherwise.
If the path exists, also print the pair of vertices between which the path forms the given string.