003 - 二色問題

問題文を変更しました。

ストーリー

四色定理というものがあります。
Wikipediaを参考にすると、「平面上のいかなる地図も、隣接する領域が異なる色になるように塗り分けるには4色あれば十分だ」ということらしいです。
なので、現実の世界地図を赤、青、黄、緑の四色で境界を区別できるようですね。

この定理は「四色で十分」ということなので、勿論五色六色あれば塗り分けられます。しかし、一色から三色では塗り分けられない場合もある、ということになります。

問題です。
ここに、$N$ヶ国の国が描かれた地図があります。
この地図は我々が生きている世界の物理法則から逸脱しており、物理的にありえない見た目をしています。
国々が隣接している部分は$M$箇所あり、国$A$_iと国$B$_iが隣接していることを表します。 このとき、この地図は二色以内で塗り分けられるか判定しなさい。
なお、$N$ヶ国の国以外の部分は無視できるものとします。

入力

1行目に、$N$と$M$が空白区切りで与えられる。
2行目以降$M$行に渡って$A$と$B$が空白区切りで与えられる。

N M
A1 B1
A2 B2
...
AM BM

出力

二色で塗り分けられれば"Yes"、塗り分けられなければ"No"を出力する。
最後の改行を忘れずに。

制約

• 1 ≤ $N$ ≤ 10⁵
• 1 ≤ $M$ ≤ $min$(10⁵ , $N$($N$-1)/2)
• 1 ≤ $A$_i , $B$_i ≤ $N$
• $A$_i ≠ $B$_i
• 入力は全て整数である

入出力例

例1

入力

6 7
1 2
2 3
1 4
4 3
1 5
6 4
3 5

出力

Yes

例2

入力

3 3
1 2
2 3
3 1

出力

No

二色で塗り分けるのは不可能です。

例3

入力

5 0

出力

Yes

各国は隣接していないので自由に色を塗れます。海とかはありません。