/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 625 点
問題文
今年のクリスマスの季節も終わり、いよいよ年越しです。高橋君はクリスマスツリーを片付ける大掃除に追われています。
赤・青・緑の 3 色の電球に彩られたクリスマスツリーがあります。クリスマスツリーには N 個の電球があり、それらは N-1 本のリボンで結ばれています。電球を頂点、リボンを辺とみなしたとき、このグラフは木です。
電球には 1 から N までの番号が、リボンには 1 から N-1 までの番号がつけられており、リボン i は電球 u_i と v_i を結んでいます。電球 i ははじめ、c_i が R ならば赤で、G ならば緑で、B ならば青で点灯しています。
高橋君は、以下の操作を N-1 回行い、すべてのリボンを取り外そうと考えています。
- まだ取り外されていないリボンのうち、両端の電球の色が異なるものを 1 本選び、そのリボンを取り外す。
- 取り外したリボンの両端の電球の番号を u, v とする。電球 u, v それぞれについて、点灯している色を次の規則で変更する。
- 赤で点灯していた場合、緑で点灯させる。
- 緑で点灯していた場合、青で点灯させる。
- 青で点灯していた場合、赤で点灯させる。
高橋君がこの操作を繰り返してすべてのリボンを取り外すことが可能かどうかを判定し、可能ならばそのような操作方法を 1 つ出力してください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\leq T\leq 20000
- 2\leq N\leq 2000
- c_i は
R,G,Bのいずれか - 1\leq u_i,v_i\leq N
- 電球を頂点、リボンを辺とみなしたとき、与えられるグラフは木
- T,N,u_i,v_i は整数
- 1 つの入力ファイルに含まれる N^2 の総和は 2000^2 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N
c_1c_2\ldots c_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
出力
\mathrm{case}_1, \mathrm{case}_2, \ldots, \mathrm{case}_T に対する答えを順に以下の形式で出力せよ。
リボンをすべて取り外すことが不可能な場合、No と出力せよ。
可能な場合、i 回目の操作で取り外すリボンの番号を e_i として、
Yes
e_1 e_2 \ldots e_{N-1}
と出力せよ。(e_1, e_2, \ldots, e_{N-1}) は (1, 2, \ldots, N-1) の順列である必要がある。
解が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
3 4 GBBR 1 2 1 3 1 4 3 RRR 1 2 2 3 5 RGBRG 1 2 2 3 3 4 3 5
出力例 1
Yes 1 3 2 No Yes 1 4 2 3
1 つ目のテストケースについて、例えば以下のように操作を行うことですべてのリボンを取り外すことができます。
- はじめ、各電球の色は（電球 1 から）順に緑、青、青、赤である。
- リボン 1 を取り外す。取り外した後の各電球の色は順に青、赤、青、赤である。
- リボン 3 を取り外す。取り外した後の各電球の色は順に赤、赤、青、緑である。
- リボン 2 を取り外す。取り外した後の各電球の色は順に緑、赤、赤、緑である。
条件を満たす (e_1, e_2,e_3) は (1, 3, 2) または (2, 3, 1) の 2 つであり、どちらを出力しても正解となります。
2 つ目のテストケースについて、どのように操作をしてもすべてのリボンを取り外すことはできません。
Score : 625 points
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.
- Choose one ribbon among those not yet removed where the bulbs at both ends have different colors, and remove that ribbon.
- 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, orB. - 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.
Sample Input 1
3 4 GBBR 1 2 1 3 1 4 3 RRR 1 2 2 3 5 RGBRG 1 2 2 3 3 4 3 5
Sample Output 1
Yes 1 3 2 No Yes 1 4 2 3
For the first test case, for example, all ribbons can be removed by performing the operations as follows:
- Initially, the colors of the bulbs are green, blue, blue, red, in order (from bulb 1).
- Remove ribbon 1. After removal, the colors of the bulbs are blue, red, blue, red, in order.
- Remove ribbon 3. After removal, the colors of the bulbs are red, red, blue, green, in order.
- Remove ribbon 2. After removal, the colors of the bulbs are green, red, red, green, in order.
The (e_1, e_2, e_3) satisfying the condition are (1, 3, 2) and (2, 3, 1), and either one will be accepted as correct.
For the second test case, it is impossible to remove all ribbons no matter how you perform the operations.