← 返回题目列表

AtCoder · agc064_b

B. 红蓝生成树

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

分数: 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 作为其端点。

约束

  • 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 R or B.
  • (a_i,b_i,c_i) \neq (a_j,b_j,c_j) if i \neq j.
  • 给定的图形已连接。
  • s_i is R or B.
  • 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