relax

問題

$N$ 頂点 $M$ 辺からなる連結な無向グラフが与えられます。頂点には $1$ から $N$ の番号が、辺には $1$ から $M$ の番号がついていて、辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を結んでいます。

あなたはこのグラフに対して以下の操作 A 及び操作 B を任意の順番で任意の回数行えます。適切に操作を行うことで、与えられたグラフを $2$ 頂点 $1$ 辺からなる連結な無向グラフにできるか判定してください。

操作 A

異なる $2$ 辺が存在し、それらの結ぶ頂点の組が同じであるとき、どちらか一方の辺を削除する。

操作 B

次数 $2$ の頂点 $i$ が存在し、頂点 $i$ が $2$ つの異なる頂点 $j, k$ と辺で結ばれているとき、頂点 $i$ 及び頂点 $i$ に接続する $2$ 本の辺を削除し、頂点 $j$ と頂点 $k$ を結ぶ辺を追加する。

制約

• $2 \leq N \leq 5000$
• $N - 1 \leq M \leq 5000$
• $1 \leq u_i \leq N \hspace{0.5em} (\mathrm{for} \hspace{0.5em} 1 \leq i \leq M)$
• $1 \leq v_i \leq N \hspace{0.5em} (\mathrm{for} \hspace{0.5em} 1 \leq i \leq M)$
• $u_i \neq v_i \hspace{0.5em} (\mathrm{for} \hspace{0.5em} 1 \leq i \leq M)$
• 与えられるグラフは連結
• 入力は全て整数

入力

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

出力

与えられたグラフを $2$ 頂点 $1$ 辺の連結なグラフにすることができるとき Yes を、そうでないとき No を標準出力に出力してください。

入出力例

例 1

5 5
1 2
2 3
3 4
4 5
5 1

Yes

例 2

4 6
1 2
2 3
3 1
1 4
2 4
3 4

No