分数: 625 点
问题陈述
今年的圣诞节已经过去了,终于到了新年的时候了。高桥正忙着收拾圣诞树的大清理工作。
有一棵圣诞树,装饰着红、蓝、绿三种颜色的灯泡。圣诞树上有 N 灯泡,它们通过 N-1 丝带。当将球茎视为顶点并将丝带视为边缘时,该图是一棵树。
灯泡编号为 1 to N,丝带编号为 1 to N-1。丝带 i 连接灯泡 u_i 和 v_i。灯泡 i 最初呈红色亮起,如果 c_i is R,如果是,则呈绿色 G,如果是蓝色 B.
高桥正在考虑执行以下操作 N-1 次移除所有色带。
- 从尚未移除且两端灯泡颜色不同的色带中选择一条,然后移除该色带。
- 让灯泡 u 和 v 是移除的色带两端的灯泡。对于每个灯泡 u 和 v,根据以下规则更改它们点亮的颜色:
- 如果它呈红色亮起,则呈绿色亮起。
- 如果它亮起绿色,则亮起蓝色。
- 如果它亮起蓝色,则亮起红色。
确定高桥是否可以通过重复此操作来移除所有色带。如果可能,输出一种这样的方法。
你被给予 T 测试用例。解决它们中的每一个。
约束
- 1\leq T\leq 20000
- 2\leq N\leq 2000
- c_i is
R,G,或B. - 1\leq u_i,v_i\leq N
- 当将球茎视为顶点并将丝带视为边缘时,给定的图是一棵树。
- T,N,u_i,v_i 是整数。
- 总和 一个输入文件中的 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.
如果可能的话,让 e_i 是从打印机中取出的色带数量 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。拆下后,灯泡的颜色依次为蓝、红、蓝、红。
- 取下色带 3。拆下后,灯泡的颜色依次为红、红、蓝、绿。
- 取下色带 2。取下后,灯泡的颜色依次为绿、红、红、绿。
的 树的 (e_1, e_2, e_3) 满足条件的是 (1, 3, 2) 和 (2, 3, 1),并且任何一个都将被视为正确。
对于第二个测试用例,无论您如何执行操作,都不可能移除所有色带。