Problem Statement

The Christmas season this year is over, and it is finally time for the new year. Takahashi is busy with the big cleanup of putting away the Christmas tree.

There is a Christmas tree decorated with bulbs in three colors: red, blue, and green. The Christmas tree has $N$ bulbs, and they are connected by $N-1$ ribbons. When viewing the bulbs as vertices and the ribbons as edges, this graph is a tree.

The bulbs are numbered from $1$ to $N$, and the ribbons are numbered from $1$ to $N-1$. Ribbon $i$ connects bulbs $u_i$ and $v_i$. Bulb $i$ is initially lit in red if $c_i$ is R, in green if it is G, and in blue if it is B.

Takahashi is considering performing the following operation $N-1$ times to remove all ribbons.

1. Choose one ribbon among those not yet removed where the bulbs at both ends have different colors, and remove that ribbon.
2. Let bulbs $u$ and $v$ be the bulbs at both ends of the removed ribbon. For each of the bulbs $u$ and $v$, change the color they are lit in according to the following rule:

• If it was lit in red, light it in green.
  • If it was lit in green, light it in blue.
  • If it was lit in blue, light it in red.

Determine whether it is possible for Takahashi to remove all ribbons by repeating this operation. If possible, output one such method.

You are given $T$ test cases. Solve each of them.

Constraints

• $1\leq T\leq 20000$
• $2\leq N\leq 2000$
• $c_i$ is R, G, or B.
• $1\leq u_i,v_i\leq N$
• When viewing the bulbs as vertices and the ribbons as edges, the given graph is a tree.
• $T,N,u_i,v_i$ are integers.
• The sum of $N^2$ in one input file is at most $2000^2$.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
c_1c_2\ldots c_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Output the answers for $\mathrm{case}_1, \mathrm{case}_2, \ldots, \mathrm{case}_T$ in order in the following format.

If it is impossible to remove all ribbons, output No.

If it is possible, let $e_i$ be the number of the ribbon removed in the $i$-th operation, and output:

Yes
e_1 e_2 \ldots e_{N-1}

$(e_1, e_2, \ldots, e_{N-1})$ must be a permutation of $(1, 2, \ldots, N-1)$.

If there are multiple solutions, any of them will be accepted as correct.