問題文

2N 頂点 M 辺の単純無向グラフ G が与えられます。頂点 i \; (i=1,2,\dots,2N) には整数 \lfloor (i+1)/2 \rfloor が書き込まれています。また、j\;(j=1,2,\dots,M) 番目の辺は頂点 u_j と頂点 v_j を双方向に結びます。

G の頂点からなる列 P=(v_1,v_2,\dots,v_K) が 回文パス であるとは、P が以下の 3 条件を満たすことと定義します。

• K\geq 2
• P は 単純パス である。すなわち、各 k=1,2\dots,K-1 について、頂点 v_k と頂点 v_{k+1} を結ぶ辺が存在し、かつ 1 \leq k < \ell \leq K について、 v_k \neq v_\ell である。
• P の頂点に書かれている整数を順に並べた列は 回文 である。すなわち、各 k=1,2,\dots,\lfloor K/2 \rfloor について、\lfloor (v_k+1)/2 \rfloor = \lfloor (v_{K-k+1}+1)/2 \rfloor である。

各 x=1,2,\dots,N について、x が書き込まれている頂点から始まる回文パスが存在するかどうか判定してください。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 4 \times 10^5
• 1 \leq u_j < v_j \leq 2N
• 与えられるグラフは単純
• 入力はすべて整数

入力例 1

4 9
1 3
2 5
2 7
3 5
4 6
4 8
5 6
6 7
6 8

出力例 1

No
Yes
Yes
Yes

x=2,3,4 について、 x が書き込まれている頂点から始まる回文パスの 1 つは以下のとおりです。

• x=2: (3, 5, 6, 4)
• x=3: (5, 6)
• x=4: (7, 6, 8)

入力例 2

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

出力例 2

No
Yes
Yes