配点 : 100 点
問題文
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
- 给定的图很简单
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
N 行。x 行中,x 的顶点开始的回文路径,则 Yes 如果不存在
从写入 No 。
入力例 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