問題文

自己ループと二重辺を含まない NN 頂点 MM 辺の無向連結グラフがあります。 ii 番目の辺 (1iM)(1 \leq i \leq M) は頂点 aia_i と頂点 bib_i を結んでいます。

アリスさんはこのグラフの上で種まきをします。頂点 uu から頂点 vv に移動するときその 22 つの頂点を結ぶ辺に種をまき、頂点 vv に到着した時点で花が咲きます。種まきは任意の頂点から始めることができます。

ただし、花を踏んでしまう可能性があるので、アリスさんは一度通った辺の上は歩かないことにしました。

アリスさんは全ての辺に花を咲かせることができるでしょうか。

制約

  • 2N2×1062 \leq N \leq 2 \times 10^6
  • N1Mmin(N(N1)/2, 2×106)N-1 \leq M \leq \min{ \left( N(N-1)/2,\ 2 \times 10^6 \right) }
  • 1ai<biN1 \leq a_i < b_i \leq N
  • 与えられるグラフは自己ループと二重辺を含まず、連結である
  • 入力中の値はすべて整数である

入力

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

N  MN\ \ M\\ a1  b1a_1\ \ b_1\\ \vdots\\ aM  bMa_M\ \ b_M

出力

アリスさんが全ての辺に全ての辺に花を咲かせることができる場合 Yes 、そうでなければ No を出力しなさい。

入力例1

3 3
1 2
1 3
2 3

出力例1

Yes

以下の順に種をまくことで全ての辺に花を咲かせることができます。

  • 始点に頂点 11 を選ぶ
  • 頂点 11 から 頂点 22 に移動する
  • 頂点 22 から 頂点 33 に移動する
  • 頂点 33 から 頂点 11 に移動する

入力例2

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

出力例2

No

どの始点からスタートしても、全ての辺に種をまくには必ず一度通った辺を再び通る必要があります。

入力例3

2 1
1 2

出力例3

Yes

Submit


Go (1.21)