Problem Statement

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

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

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

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

Input

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

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（青）である。
• グラフは連結である。

Output

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