Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

See You Again?

By bappy.cse38 · Limits 500ms, 512 MB

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 n nodes and n1 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.

Input

The first line of the input contains one integer t t (1<=t<=1000 1 <= t <= 1000 ) - the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n n (1<=n<=105 1 <= n <= 10^{5} ) - number of nodes in the tree.

The next n1 n-1 lines contains two integers u u (1<=u<=n 1 <= u <= n ) and v v (1<=v<=n 1 <= v <= n ) denotes an edge between node u u and v v .

The next line contains n space separated characters where c[i] c[i] corresponds to the character in the ith i^{th} node. c[i] 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 105 10^{5}

Output

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".

Sample

InputOutput
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.

    Discussion

    Statistics


    78% Solution Ratio

    dip_BRUREarliest, 6M ago

    prodip_bsmrstuFastest, 0.0s

    dip_BRURLightest, 655 kB

    YouKnowWhoShortest, 1435B

    Submit

    Login to submit