You are given a tree with $N$ vertices numbered $1$ through $N$. The $i$-th edge of the tree connects vertices $u_i$ and $v_i$. Initially, for each $i$ ($1 \le i \le N$), vertex $i$ contains one stone if $A_i = 1$ and no stone if $A_i = 0$.

You can repeatedly perform the following operation:

• Select an unchosen edge with a stone on exactly one of its endpoints, and move that stone to the other endpoint.

Determine whether you can perform the operation exactly $N - 1$ times. If possible, output the order in which the edges are selected.

Input

The input contains one or more test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^5$), which is the number of test cases. The descriptions of the $T$ test cases follow, each in the following format.

$$ \begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \\ &A_1 \ A_2 \ \ldots \ A_N \end{aligned} $$

The first line contains an integer $N$ ($2 \le N \le 2 \times 10^5$) representing the number of vertices.

For each $i$ ($1 \le i \le N - 1$), the $i$-th of the following $N - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$) separated by a space, representing that the $i$-th edge connects vertices $u_i$ and $v_i$. It is guaranteed that the given graph is a tree.

The last line contains $N$ integers $A_1, A_2, \ldots, A_N$ ($A_i \in \{0, 1\}$) separated by spaces. $A_i$ represents whether a stone is initially placed on vertex $i$.

The sum of $N$ over all test cases does not exceed $2 \times 10^5$.

Output

For each test case, print the answer as follows.

If it is impossible to perform the operation exactly $N - 1$ times, output No on a single line.

If it is possible, output Yes on the first line, followed by the sequence of edges on the second line in the following format:

$$ e_1 \ e_2 \ \ldots \ e_{N-1} $$

Here, $e_k$ ($1 \le e_k \le N - 1$) represents the index of the edge selected in the $k$-th operation. If there are multiple valid sequences, you can output any of them.

Example

Input 1

3
5
1 2
2 3
2 4
2 5
1 1 1 0 0
2
1 2
0 0
9
1 2
2 3
2 4
4 5
4 6
6 7
6 8
6 9
0 0 1 0 1 1 0 1 1

Output 1

Yes
3 2 4 1
No
Yes
6 7 4 2 1 3 5 8