AT_tupc2024_n.Palindromic Path

给定一个有 $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$ 满足以下三个条件：

• $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$ 的顶点出发的回文路径。

输入以如下格式给出：

$N$　$M$　$u_1$　$v_1$　$u_2$　$v_2$　$\vdots$　$u_M$　$v_M$

输出 $N$ 行。第 $x$ 行若存在从写有 $x$ 的顶点出发的回文路径，则输出 Yes，否则输出 No。

样例解释 1

对于 $x=2, 3, 4$，能从写有 $x$ 的顶点出发的回文路径示例如下：

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

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 4 \times 10^5$
• $1 \leq u_j < v_j \leq 2N$
• 给定图为简单图
• 所有输入均为整数。

由 ChatGPT 5 翻译