問題文

$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