Story

🌳

whiteさんは嬉しそうに、matcharate君と一緒に雪玉を転がしています。

一方その頃、ラ亭では…

「お待たせしました〜ラ帝特製の “グリーンラテのホッと一息チョコレートパンケーキ” になりま〜す！」

greenrate君はかなり忙しそうです。そりゃそうです。1人で店回せたら、そりゃたまったもんじゃありません。

しかし順調に行ってるようです。
また常連さんであるnum021さんは、今回も新たなおもちゃを開発したようです。それは、グラフの形をしたような可愛いおもちゃでした。

「このおもちゃに付いてる玉にはな、数字が書けるスペースがあるんだが、そこに数字を書いて"回文グラフ"を作るのが目標なんだ。greenrateもやってみるか？」

グラフの回文…とはなんでしょうか？

問題

$N$ 頂点 $M$ 辺の無向グラフが与えられます。$m\ (1\le m\le M)$ 本目の辺は頂点 $A_m$ と頂点 $B_m$ をつないでいます。
このグラフが回文グラフであるかどうか判定してください。すなわち以下を満たすグラフであるか判定してください。

• $1$ 以上 $N$ 以下のすべての整数の組 $(i,j)\ (i\lt j)$ に対し、以下のいずれかを満たすグラフとなる。
  • $2$ 頂点 $i,j$ が辺をたどってたどりつけるなら、$2$ 頂点 $N-i+1,N-j+1$ も辺をたどってたどりつける
  • $2$ 頂点 $i,j$ が辺をたどってたどりつけないなら、$2$ 頂点 $N-i+1,N-j+1$ も辺をたどってたどりつけない

入力

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

制約

• $2\le N\le 2000$
• $0\le M\le \min(2000,\cfrac{N(N-1)}{2})$
• $1\le A_i\lt B_i\le N$
• $x\ne y\Rightarrow (A_x,B_x)\ne (A_y,B_y)$
• 入力はすべて整数

出力

回文グラフであるなら Yes 、でないなら No を出力せよ。

入出力例

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

Yes

6 4
1 2
2 3
2 6
4 5

No

もともとでは頂点 $1,2$ が隣接していましたが、番号を $6,5$ に変えると元のグラフでは頂点 $6,5$ は隣接していません。したがって条件を満たしません。

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

Yes

6 0

Yes

辺が一つも存在しないときもあります。