当前没有测试数据。

E - 好图

分数：475 分

题目描述

给定一个有 $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)}$ 是否是好图？

约束

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times10^5$
• $1 \leq u_i, v_i \leq N$
• $1 \leq K \leq 2 \times 10^5$
• $1 \leq x_i, y_i \leq N$
• $x_i \neq y_i$
• $i \neq j \implies \lbrace x_i, y_i \rbrace \neq \lbrace x_j, y_j \rbrace$
• 对于所有的 $i = 1, 2, \ldots, K$，图 $G$ 中没有连接顶点 $x_i$ 和 $y_i$ 的路径。
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq p_i, q_i \leq N$
• $p_i \neq q_i$
• 所有输入值皆为整数。

---

输入

从标准输入中以以下格式给出：

$N$ $M$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

$K$

$x_1$ $y_1$

$x_2$ $y_2$

$\vdots$

$x_K$ $y_K$

$Q$

$p_1$ $q_1$

$p_2$ $q_2$

$\vdots$

$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$ 可能具有自环或重边。