#P12274. [蓝桥杯 2024 国 Python B] 设计

[蓝桥杯 2024 国 Python B] 设计

题目描述

小蓝是 H 市的市长,她正在用设计软件规划 H 市的道路建设。

小蓝可以选定两个地区,用一条双向道路将这两个地区连接。由于预算等因素的动态变化,小蓝经常需要拆除一些已经建设好的道路,同时,她希望知道对于当前的两个地区,是否存在一条由多条道路组成的路径能够连接这两个地区。

输入格式

输入的第一行包含两个正整数 n,mn, m,用一个空格分隔,其中 nn 表示地区个数,mm 表示操作次数。

接下来 mm 行,每行表示一个操作。对于每一行:

  • 11 xix_i yiy_i 表示小蓝修建了一条连接地区 xix_i 与地区 yiy_i 的双向道路。
  • 22 表示小蓝拆除了当前 H 市中还未被拆除的最后修建的一条道路,如果当前城市中已经不存在道路,则小蓝不会进行任何操作。
  • 33 xix_i yiy_i 表示小蓝希望知道地区 xix_i 与地区 yiy_i 是否连通,即是否存在一条由多条道路组成的路径能够连接这两个地区。

输出格式

对于每个操作 33 输出 YesNo,其中 Yes 表示连通,No 表示不连通。

2 5
3 1 2
1 1 2
3 1 2
2
3 1 2
No
Yes
No
3 8
1 1 2
1 1 3
1 2 3
2
3 2 3
2
3 1 2
3 2 3
Yes
Yes
No

提示

评测用例规模与约定

  • 对于 50%50\% 的评测用例,n,m3000n, m \leq 3000
  • 对于所有评测用例,1n,m3000001 \leq n, m \leq 3000001xi,yin1 \leq x_i, y_i \leq nxiyix_i \neq y_i