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 翻译