#P18331. Palindromic Path

Palindromic Path

Palindromic Path

给定一个有 2N2N 个顶点、MM 条边的简单无向图 GG。顶点编号为 1,2,…,2N1,2,\ldots,2N,顶点 ii 的标签为

⌊i+12⌋.\left\lfloor\frac{i+1}{2}\right\rfloor.

也就是说,标签 xx 恰好出现在顶点 2x−12x-1 和 2x2x 上。第 jj 条边连接顶点 uj,vju_j,v_j。

称顶点序列 P=(v1,v2,…,vK)P=(v_1,v_2,\ldots,v_K) 是一条回文路径,当且仅当:

  1. K≥2K\ge2;
  2. 它是一条简单路径:相邻顶点之间存在边,且任何顶点都不能重复出现;
  3. 路径上的标签序列是回文,即对所有 1≤k≤⌊K/2⌋1\le k\le\lfloor K/2\rfloor,都有
$$\left\lfloor\frac{v_k+1}{2}\right\rfloor = \left\lfloor\frac{v_{K-k+1}+1}{2}\right\rfloor.$$

对于每个 x=1,2,…,Nx=1,2,\ldots,N,判断是否存在一条从标签为 xx 的顶点出发的回文路径。

输入格式

第一行包含两个整数 N,MN,M。

接下来 MM 行,每行包含两个整数 uj,vju_j,v_j,表示一条无向边。

输出格式

输出 NN 行。第 xx 行中,若存在从标签为 xx 的顶点出发的回文路径,输出 Yes;否则输出 No。

数据范围

  • 1≤N≤2×1051\le N\le2\times10^5;
  • 1≤M≤4×1051\le M\le4\times10^5;
  • 1≤uj<vj≤2N1\le u_j<v_j\le2N;
  • 不存在重边,即 i≠ji\ne j 时 (ui,vi)≠(uj,vj)(u_i,v_i)\ne(u_j,v_j);
  • 所有输入值均为整数。

图不保证连通。只有一个顶点的路径不满足要求。

样例输入 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,42,3,4 出发的回文路径,这里写出的是实际顶点编号:

  • 标签 22:(3,5,6,4)(3,5,6,4),标签序列为 (2,3,3,2)(2,3,3,2);
  • 标签 33:(5,6)(5,6),标签序列为 (3,3)(3,3);
  • 标签 44:(7,6,8)(7,6,8),标签序列为 (4,3,4)(4,3,4)。