分数: 600 点
问题陈述
给你一个连通的无向图 G 与 N 顶点和 M 边缘。对于每个 i=1,2,\ldots,M, i第一条边连接顶点 a_i 和 b_i,如果 c_i= R 和蓝色如果 c_i= B.
判断是否存在生成树 G 满足以下条件,如果满足,则显示这样一棵树。
- 对于每个 i=1,2,\ldots,N,
- if s_i =
R,至少一条红边有顶点 i 作为终点; - if s_i =
B,至少一条蓝色边有顶点 i 作为其端点。
- if s_i =
约束
- 2 \leq N \leq 2 \times 10^5
- N-1 \leq M \leq 2 \times 10^5
- 1 \leq a_i \lt b_i \leq N
- c_i is
RorB. - (a_i,b_i,c_i) \neq (a_j,b_j,c_j) if i \neq j.
- 给定的图形已连接。
- s_i is
RorB. - N,M,a_i,b_i 是整数。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 c_1 \vdots a_M b_M c_M s_1 s_2 \ldots s_N
输出
如果没有生成树 G 满足条件,打印 No.
No
否则,按以下格式打印这样的树:
Yes
t_1 t_2 \ldots t_{N-1}
这意味着 i生成树的第边是 t_i第边缘 G.
如果多个生成树 G 满足条件,其中任意一项均被接受。
示例输入 1
3 3 1 2 R 1 3 B 2 3 B RRB
示例输出 1
Yes 2 1
这里我们展示了由第一条边和第二条边形成的生成树 G 满足条件。
- s_1 =
R,所以对于 i=1,至少一条红边必须有顶点 1 作为其端点。第一条边 G 就是这样一个边缘。 - s_2 =
R,所以对于 i=2,至少一条红边必须有顶点 2 作为其端点。第一条边 G 就是这样一个边缘。 - s_3 =
B,所以对于 i=3,至少一条蓝色边必须有顶点 3 作为其端点。第二个边缘 G 就是这样一个边缘。
示例输入 2
3 4 1 2 R 1 2 B 1 3 B 2 3 B RRR
示例输出 2
No
示例输入 3
8 16 5 7 B 2 7 R 1 6 R 1 4 R 6 7 R 4 6 B 4 8 R 2 3 R 3 5 R 6 7 B 2 6 B 5 6 R 1 3 B 4 5 B 2 7 B 1 8 B BRBRRBRB
示例输出 3
Yes 1 2 4 9 11 13 16
示例输入 4
8 10 1 7 R 1 3 B 2 5 B 2 8 R 1 5 R 3 6 R 2 6 B 3 4 B 2 8 B 4 6 B RRRBBBRB
示例输出 4
No