AT_agc064_b [AGC064B] Red and Blue Spanning Tree

[problemUrl]: https://atcoder.jp/contests/agc064/tasks/agc064_b $ 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 $ 本以上存在する

入力は以下の形式で標準入力から与えられる。 > $ 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 $ の全域木が複数存在する場合、その中のどれを出力しても正解となる。

### 制約 - $ 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 $ は整数 ### Sample Explanation 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 $ 番目の辺が該当します。