← 返回题目列表

AtCoder · abc437_g

G. 多彩圣诞树

中文机器翻译题面 查看原题

分数: 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 次移除所有色带。

  1. 从尚未移除且两端灯泡颜色不同的色带中选择一条,然后移除该色带。
  2. 让灯泡 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),并且任何一个都将被视为正确。

对于第二个测试用例,无论您如何执行操作,都不可能移除所有色带。