D - 辺彩色 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 個の頂点と M 本の辺からなる無向グラフが与えられる。 グラフは連結で、自己ループや多重辺を含まない。 辺は 1 から M まで番号が振られている。

はじめ、辺には色が塗られていない。 高橋君は i (1≦i≦M) 番目の辺に色 c_i が塗られているようにしたい。 ただし、c_i は r（赤）または b（青）である。 高橋君は次のようにして辺に色を塗る。

  • まず、好きな頂点を始点に選ぶ。以降、「隣接する頂点へ移動する」というステップを好きなだけ繰り返す。
  • 各ステップごとに使われた辺に色を塗る。このとき、奇数回目のステップでは赤を塗り、偶数回目のステップでは青を塗る。
  • 既に色が塗られている辺に色を塗ると、新しい色で上書きされる。

すべての辺に目標の色が塗られているようにできるか判定せよ。

入力

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

N M
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M
  • 1 行目には、頂点の個数 N (2≦N≦2,000) と辺の本数 M (1≦M≦2,000) が空白区切りで与えられる。
  • 2 行目からの M 行には、辺の情報が与えられる。このうち i 行目には、整数 a_i，b_i (1≦a_i<b_i≦N) と色 c_i が空白区切りで与えられる。これは次のことを表す。
    • i 番目の辺が頂点 a_i と頂点 b_i を結んでいる。ただし、i≠j ならば a_i≠a_j または b_i≠b_j を満たす。
    • i 番目の辺に色 c_i が塗られているようにしたい。ただし、c_i は r（赤）または b（青）である。
  • グラフは連結である。

出力

すべての辺に目標の色が塗られているようにできるならば Yes を、できないならば No を 1 行に出力せよ。 出力の末尾に改行を入れること。

入力例1

6 5
1 2 r
2 3 b
3 4 r
4 5 b
5 6 r

出力例1

Yes

例えば、頂点 1 を始点に選び、図のようにして辺に色を塗ればよい。

入力例2

4 3
1 2 r
1 3 r
1 4 r

出力例2

Yes

例えば、頂点 2 を始点に選び、図のようにして辺に色を塗ればよい。上書きされる色は破線で示している。

入力例3

3 3
1 2 b
1 3 b
2 3 b

出力例3

No