← 返回题目列表

AtCoder · nupc2024_p

P. 偶数肯肯

中文机器翻译题面 查看原题

配点 : 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