DST - See you again?


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 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 (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

 

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. And print the lexicographically smallest path that contains the mentioned string as a subsequence.

Otherwise, print "NO".

Example

Input:

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


Output:
Case 1: YES
1 2 4 7 10 14 16 19 22 28 29 30 31
Notes:
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.

hide comments
pacific_kafka: 2021-01-24 14:26:42

wtf man the sample test case is wrong, 31 should not be there, I wasted an hour trying to figure this out
nvm Im a dumbass , the sample testcases are correct

Last edit: 2021-01-24 14:30:45
nadstratosfer: 2020-12-25 20:58:59

Enjoyed solving, although failed to get my original Python solution past the TL. Python performs really bad with what I felt was the cleanest idea here, might try a different approach later.

Condolences on your loss.


Added by:Bappy
Date:2020-09-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All