普及-⏱ 1000ms💾 256MB#P3200🏷️ 并查集数据结构

题目描述

校友会掌握 $n$ 名毕业生的名册(编号 $1 \sim n$)与 $m$ 条"同届"关系: 同届关系可以传递——若 $a$ 与 $b$ 同届、$b$ 与 $c$ 同届,则 $a$ 与 $c$ 也算同届。

对每条询问"两人是否同届",快速给出答案:同届输出 Yes,否则输出 No。

输入格式

输入分两部分。 第一部分第一行为 $N, M$(人数与关系数);以下 $M$ 行,每行两个数 $a, b$,表示 $a$ 与 $b$ 同届。 第二部分第一行为 $Q$(询问数);以下 $Q$ 行,每行两个数 $c, d$,为一次询问。

输出格式

每个询问一行:同届输出 Yes,否则输出 No。

数据范围

$$N \le 20000,\ M \le 1000000,\ Q \le 1000000$$

样例输入 #1
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
1 5
2 3
样例输出 #1
Yes
No
Yes
样例输入 #2
1 0
1
1 1
样例输出 #2
Yes