题目描述

有一个包含 $N$ 个顶点、$M$ 条边的连通无向图 $G$。对于 $i=1,2,\ldots,M$，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，如果 $c_i=$ R，则该边为红色；如果 $c_i=$ B，则该边为蓝色。

请判断是否存在满足以下条件的 $G$ 的一棵生成树。如果存在，请给出其中一棵。

• 对于所有 $i=1,2,\ldots,N$，
  • 如果 $s_i=$ R，则顶点 $i$ 至少有一条红色的边作为端点。
  • 如果 $s_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}$

其中 $t_i$ 表示生成树中第 $i$ 条边在 $G$ 中的编号。
如果存在多种满足条件的生成树，输出其中任意一种均可。

样例 1

输入

3 3
1 2 R
1 3 B
2 3 B
RRB

输出

Yes
2 1

样例 2

输入

3 4
1 2 R
1 2 B
1 3 B
2 3 B
RRR

输出

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

输出

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

输出

No

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $N-1 \leq M \leq 2 \times 10^5$
• $1 \leq a_i < b_i \leq N$
• $c_i$ 为 R 或 B
• 若 $i \neq j$，则 $(a_i, b_i, c_i) \neq (a_j, b_j, c_j)$
• 给定的图是连通的
• $s_i$ 为 R 或 B
• $N, M, a_i, b_i$ 均为整数

样例解释 1

由 $G$ 的第 1、2 条边组成的生成树满足条件，具体如下：

• $s_1=$ R，因此对于 $i=1$，要求顶点 1 至少有一条红色的边作为端点。第 1 条边满足此条件。
• $s_2=$ R，因此对于 $i=2$，要求顶点 2 至少有一条红色的边作为端点。第 1 条边满足此条件。
• $s_3=$ B，因此对于 $i=3$，要求顶点 3 至少有一条蓝色的边作为端点。第 2 条边满足此条件。

由 ChatGPT 4.1 翻译