Palindromic Path
给定一个有 2N 个顶点、M 条边的简单无向图 G。顶点编号为 1,2,…,2N,顶点 i 的标签为
⌊2i+1⌋.
也就是说,标签 x 恰好出现在顶点 2x−1 和 2x 上。第 j 条边连接顶点 uj,vj。
称顶点序列 P=(v1,v2,…,vK) 是一条回文路径,当且仅当:
- K≥2;
- 它是一条简单路径:相邻顶点之间存在边,且任何顶点都不能重复出现;
- 路径上的标签序列是回文,即对所有 1≤k≤⌊K/2⌋,都有
$$\left\lfloor\frac{v_k+1}{2}\right\rfloor
=
\left\lfloor\frac{v_{K-k+1}+1}{2}\right\rfloor.$$
对于每个 x=1,2,…,N,判断是否存在一条从标签为 x 的顶点出发的回文路径。
输入格式
第一行包含两个整数 N,M。
接下来 M 行,每行包含两个整数 uj,vj,表示一条无向边。
输出格式
输出 N 行。第 x 行中,若存在从标签为 x 的顶点出发的回文路径,输出 Yes;否则输出 No。
数据范围
- 1≤N≤2×105;
- 1≤M≤4×105;
- 1≤uj<vj≤2N;
- 不存在重边,即 i=j 时 (ui,vi)=(uj,vj);
- 所有输入值均为整数。
图不保证连通。只有一个顶点的路径不满足要求。
样例输入 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
样例输入 2
3 6
1 3
3 5
2 4
4 6
1 5
1 6
样例输出 2
No
Yes
Yes
样例说明
第一个样例中,以下分别是从标签 2,3,4 出发的回文路径,这里写出的是实际顶点编号:
- 标签 2:(3,5,6,4),标签序列为 (2,3,3,2);
- 标签 3:(5,6),标签序列为 (3,3);
- 标签 4:(7,6,8),标签序列为 (4,3,4)。