AT_arc041_d [ARC041D] 辺彩色

[problemUrl]: https://atcoder.jp/contests/arc041/tasks/arc041_d $ 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\

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

### Sample Explanation 1 例えば、頂点 $ 1 $ を始点に選び、図のようにして辺に色を塗ればよい。 !\[\](https://arc041.contest.atcoder.jp/img/arc/041/qawsedrftgyhujikolp/graph\_1.png) ### Sample Explanation 2 例えば、頂点 $ 2 $ を始点に選び、図のようにして辺に色を塗ればよい。上書きされる色は破線で示している。 !\[\](https://arc041.contest.atcoder.jp/img/arc/041/qawsedrftgyhujikolp/graph\_2.png)