30063 - Red and Blue Spanning Tree

有一个包含 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

a1 b1 c1

...

aM bM cM

s1 s2 ... sN

如果不存在满足条件的 G 的生成树，输出 No。 否则输出以下形式：

Yes

t1 t2 ... t_{N-1}

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

限制条件

• 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 条边满足此条件。