Good Graph

题目描述

你被给定了一个无向图 $G$，它有 $N$ 个顶点和 $M$ 条边。 对于 $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$ $\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

提示

$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$，在图中不存在连接顶点 $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$ 所有输入值均为整数。对于第一个问题，图 $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$ 可能包含自环或多重边。

标签: AtCoder|abc304E

来源

AtCoder|abc304E