問題文を変更しました。
2行目以降$M$行に渡って$A$と$B$が空白区切りで与えられる。
最後の改行を忘れずに。
ストーリー
四色定理というものがあります。
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$ ≤ 105
- 1 ≤ $M$ ≤ $min$(105 , $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各国は隣接していないので自由に色を塗れます。海とかはありません。