B - Red and Blue Spanning Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点 M 辺の連結無向グラフ G があります。i=1,2,\ldots,M に対し i 番目の辺は頂点 a_i, b_i を結んでいて、c_i= R ならば赤で、c_i= B ならば青で塗られています。

次の条件を満たす G の全域木が存在するかどうかを判定し、存在する場合は 1 つ示してください。

  • i=1,2,\ldots,N すべてに対し、
    • s_i = R ならば、頂点 i を端点とする赤の辺が 1 本以上存在する
    • s_i = B ならば、頂点 i を端点とする青の辺が 1 本以上存在する

制約

  • 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 は 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 は整数

入力

入力は以下の形式で標準入力から与えられる。

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 における何番目の辺かを表す。
なお、問題文中の条件を満たす G の全域木が複数存在する場合、その中のどれを出力しても正解となる。

入力例 1

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

出力例 1

Yes
2 1

G における 1,2 番目の辺からなる全域木が条件を満たすことを以下に示します。

  • s_1 = R なので、i=1 に対する条件は頂点 1 を端点とする赤の辺が 1 本以上存在することです。これは G における 1 番目の辺が該当します。
  • s_2 = R なので、i=2 に対する条件は頂点 2 を端点とする赤の辺が 1 本以上存在することです。これは G における 1 番目の辺が該当します。
  • s_3 = B なので、i=3 に対する条件は頂点 3 を端点とする青の辺が 1 本以上存在することです。これは G における 2 番目の辺が該当します。

入力例 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

Score : 600 points

Problem Statement

You are given a connected undirected graph G with N vertices and M edges. For each i=1,2,\ldots,M, the i-th edge connects vertices a_i and b_i, and is colored red if c_i= R and blue if c_i= B.

Determine if there is a spanning tree of G that satisfies the following condition, and if so, display such a tree.

  • For every i=1,2,\ldots,N,
    • if s_i = R, at least one red edge has vertex i as its endpoint;
    • if s_i = B, at least one blue edge has vertex i as its endpoint.

Constraints

  • 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.
  • The given graph is connected.
  • s_i is R or B.
  • N,M,a_i,b_i are integers.

Input

The input is given from Standard Input in the following format:

N M
a_1 b_1 c_1
\vdots
a_M b_M c_M
s_1 s_2 \ldots s_N

Output

If no spanning tree of G satisfies the condition, print No.

No

Otherwise, print such a tree in the following format:

Yes
t_1 t_2 \ldots t_{N-1}

This means that the i-th edge of the spanning tree is the t_i-th edge of G.
If multiple spanning trees of G satisfy the condition, any one of them is accepted.

Sample Input 1

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

Sample Output 1

Yes
2 1

Here we show that the spanning tree formed by the first and second edges of G satisfies the condition.

  • s_1 = R, so for i=1, at least one red edge must have vertex 1 as its endpoint. The first edge of G is such an edge.
  • s_2 = R, so for i=2, at least one red edge must have vertex 2 as its endpoint. The first edge of G is such an edge.
  • s_3 = B, so for i=3, at least one blue edge must have vertex 3 as its endpoint. The second edge of G is such an edge.

Sample Input 2

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

Sample Output 2

No

Sample Input 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

Sample Output 3

Yes
1 2 4 9 11 13 16

Sample Input 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

Sample Output 4

No