← 返回题目列表

AtCoder · tupc2024_n

N. 回文路径

中文机器翻译题面 查看原题

配点 : 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