Story

🌳

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

一方その頃、ラ亭では…

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

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

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

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

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

問題

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

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

入力

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

NN MM
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
AMA_M BMB_M

制約

  • 2≤N≤20002\le N\le 2000
  • 0≤M≤min⁡(2000,N(N−1)2)0\le M\le \min(2000,\cfrac{N(N-1)}{2})
  • 1≤Ai<Bi≤N1\le A_i\lt B_i\le N
  • x≠y⇒(Ax,Bx)≠(Ay,By)x\ne y\Rightarrow (A_x,B_x)\ne (A_y,B_y)
  • 入力はすべて整数

出力

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

入出力例

入力例1
5 5
1 2
1 3
2 5
3 4
4 5
出力例1
Yes
入力例2
6 4
1 2
2 3
2 6
4 5
出力例2
No

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

入力例3
6 5
1 2
2 4
3 5
5 6
3 6
出力例3
Yes
入力例4
6 0
出力例4
Yes

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

Submit


Go (1.21)