好图

题目描述

给你一个具有 $N$ 个顶点和 $M$ 条边的无向图 $G$。 对于 $i = 1, 2, \ldots, M$,第 $i$ 条边是连接顶点 $u_i$ 和 $v_i$ 的无向边。

一个具有 $N$ 个顶点的图被称为「好图」,当且仅当对所有的 $i = 1, 2, \ldots, K$,下列条件成立:

在 $G$ 中不存在连接顶点 $x_i$ 和 $y_i$ 的路径。

给定的图 $G$ 是「好图」。

给你 $Q$ 个相互独立的问题。请回答全部问题。 对于 $i = 1, 2, \ldots, Q$,第 $i$ 个问题如下。

在给定的图 $G$ 中加入一条连接顶点 $p_i$ 和 $q_i$ 的无向边后得到的图 $G^{(i)}$ 是否仍是「好图」?

输入格式

输入按以下格式从标准输入给出:

N M
u_1 v_1
u_2 v_2
⋮
u_M v_M
K
x_1 y_1
x_2 y_2
⋮
x_K y_K
Q
p_1 q_1
p_2 q_2
⋮
p_Q q_Q

输出格式

输出 $Q$ 行。 对于 $i = 1, 2, \ldots, Q$,第 $i$ 行输出第 $i$ 个问题的答案:如果图 $G^{(i)}$ 是「好图」则输出 Yes,否则输出 No。

样例

6 6
1 2
2 3
2 3
3 1
5 4
5 5
3
1 5
2 6
4 3
4
2 5
2 6
5 6
5 4

No
No
Yes
Yes

对于第一个问题,图 $G^{(1)}$ 中存在连接顶点 $x_1 = 1$ 和 $y_1 = 5$ 的路径 $1 \rightarrow 2 \rightarrow 5$,因此不是「好图」。所以输出 No。

对于第二个问题,图 $G^{(2)}$ 中存在连接顶点 $x_2 = 2$ 和 $y_2 = 6$ 的路径 $2 \rightarrow 6$,因此不是「好图」。所以输出 No。

对于第三个问题,图 $G^{(3)}$ 是「好图」。所以输出 Yes。

对于第四个问题,图 $G^{(4)}$ 是「好图」。所以输出 Yes。

如该样例输入所示,注意给定的图 $G$ 可能含有自环或重边。

数据范围

• $2 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le u_i, v_i \le N$
• $1 \le K \le 2 \times 10^5$
• $1 \le x_i, y_i \le N$
• $x_i \neq y_i$
• 当 $i \neq j$ 时,$\lbrace x_i, y_i \rbrace \neq \lbrace x_j, y_j \rbrace$
• 对所有的 $i = 1, 2, \ldots, K$,在 $G$ 中不存在连接顶点 $x_i$ 和 $y_i$ 的路径。
• $1 \le Q \le 2 \times 10^5$
• $1 \le p_i, q_i \le N$
• $p_i \neq q_i$
• 所有输入值均为整数。