配点 : 100 点
問題
边 1 累积的上限数 N 无向图 G 。 Q 给出若干查询,请依次处理。
查询如下 2属于以下两种之一。
1 u v: 頂点 u 和顶点 连接的边和顶点 v 在…之间连边。2 u v: 頂点 u 的顶点 长度拉伸到 v 是否存在偶数长度的游走,并输出结果。
游走是什么?
古拉夫 G 的边 s, t 对于顶点的序列 (v_1,v_2,\ldots,v_k) 并且是 v_1 = s, v_k = t 不同的 1\le i\le k-1 , v_i, v_{i+1} 由边连接的顶点 s 减去 t 到游走称为。此外,在此情况下,请注意,步行的长度 小于或等于是 k-1 。 可以多次经过相同的顶点。制約
- 2\le N \le 2\times 10^5
- 1\le Q \le 2\times 10^5
- 在任何查询中, 1\le u \lt v \le N
- 1 在种类查询中,相同的 (u, v) 是 2 不会再次出现
- 输入全部为整数
入力
输入将以以下格式从标准输入给出。
N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
每个查询有以下 2 两种形式之一。
1 u v
2 u v
出力
2 对于种类查询,如果存在偶数长度的步行,则 Yes 如果不存在 No 请分别每 1 行输出。
入力例 1
4 8 2 1 4 1 1 2 2 1 4 1 2 4 2 1 4 2 2 4 1 1 4 2 2 4
出力例 1
No No Yes No Yes
1 种类的查询会使图表如图1~图4般变化。起初,图表为图1的状态。
- 1 第 1 和顶点
连接的边和顶点 4 个查询之间由于不存在长度为偶数的游走,
No。 - 2 第 1 和顶点 连接的边和顶点 2 之间添加了边,图表变为图2的状态。
- 3 第 1 和顶点
连接的边和顶点 4 个查询之间由于不存在长度为偶数的游走,
No。 - 4 第 2 和顶点 连接的边和顶点 4 之间添加了边,图形变成了图3的状态。
- 5 第 1 和顶点
连接的边和顶点 4 之间存在长度为 2 的步行,
由于
Yes。 - 6 第 2 和顶点
连接的边和顶点 4 之间只存在奇数长度的步行,
No。 - 7 第 1 和顶点 连接的边和顶点 4 之间添加了边,图形变成了图4的状态。 为了装饰
- 8 第 2 和顶点
连接的边和顶点 4 之间存在长度为 2 的步行,
由于
Yes。
入力例 2
10 20 1 1 3 1 1 4 2 5 8 2 3 4 1 3 7 2 3 7 2 1 7 1 5 9 2 5 7 2 4 7 1 5 8 2 8 9 2 6 10 1 1 8 2 1 5 2 4 8 2 3 5 1 3 9 2 3 8 2 3 7
出力例 2
No Yes No Yes No No Yes No Yes Yes No Yes Yes