Tareq and Shawon were two friends of the problem setter's. Many years ago, they died in a road accident. The problem setter still misses them. He gives you the following task in memory of his friends.
You're given a tree with $ n $ nodes and $ n-1 $ edges. Each node contains a single character(A node can contain any of the lowercase Latin letters 'a' to 'z' or a special symbol '&'). You've to answer if it is possible to find the string "tareq&shawon", without quotes, as a subsequence if you choose a path from the root node to a leaf node. If it is possible then print the path that contains the mentioned string as a subsequence. If there are multiple paths containing the above string as a subsequence, print the lexicographically smallest one. Note that 1 is the root of the tree and you've to print the whole path from the root node to a leaf node that contains the above string as a subsequence.
You have to answer t independent test cases.
The first line of the input contains one integer $ t $($ 1 <= t <= 1000 $) - the number of test cases. Then t test cases follow.
The first line of the test case contains one integer $ n $($ 1 <= n <= 10^{5} $) - number of nodes in the tree.
The next $ n-1 $ lines contains two integers $ u $($ 1 <= u <= n $) and $ v $($ 1 <= v <= n $) denotes an edge between node $ u $ and $ v $.
The next line contains n space separated characters where $ c[i] $ corresponds to the character in the $ i^{th} $ node. $ c[i] $ can be a lowercase Latin letter or special symbol '&'.
It is guaranted that the sum of n over all test cases does not exceed $ 10^{5} $
For each case print the case number and then print "YES" if there is a path from the root node to a leaf node that contains the mentioned string as a subsequence. In the next line print the lexicographically smallest path that contains the mentioned string as a subsequence.
Otherwise, print "NO".
| Input | Output |
|---|---|
1 31 1 2 2 3 3 8 8 9 9 13 13 17 17 18 18 23 2 4 4 7 7 10 10 14 14 16 16 19 19 22 22 28 28 29 29 30 30 31 2 5 5 6 6 11 11 12 12 15 15 20 20 21 21 24 24 25 25 26 26 27 t a r r r e e e q q q & & & s s s h h h a a a w o n m w o n x | Case 1: YES 1 2 4 7 10 14 16 19 22 28 29 30 31 |
Explanation:
There are two possible path from the root to a leaf that contains mentioned string as a subsequence.
They are 1 2 4 7 10 14 16 19 22 28 29 30 31 and 1 2 5 6 11 12 15 20 21 24 25 26 27.
But first one is lexicographically smaller.