道路设计(Road Design)

题目描述

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

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

输入格式

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

接下来 $m$ 行，每行表示一个操作。对于每一行：

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

输出格式

对于每个操作 $3$ 输出 Yes 或 No，其中 Yes 表示连通，No 表示不连通。

样例输入 #1

2 5
3 1 2
1 1 2
3 1 2
2
3 1 2

样例输出 #1

No
Yes
No

样例输入 #2

3 8
1 1 2
1 1 3
1 2 3
2
3 2 3
2
3 1 2
3 2 3

样例输出 #2

Yes
Yes
No

数据范围

评测用例规模与约定

• 对于 $50\%$ 的评测用例，$n, m \leq 3000$。
• 对于所有评测用例，$1 \leq n, m \leq 300000$，$1 \leq x_i, y_i \leq n$，$x_i \neq y_i$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接