AT_abc304_e [ABC304E] Good Graph

题目描述

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

如果对于所有 $i=1,2,\ldots,K$，都满足以下条件，则称 $N$ 个顶点的图是好图：

• 在 $G$ 上不存在一条路径连接顶点 $x_i$ 和顶点 $y_i$。

给定的图 $G$ 是好图。

现在有 $Q$ 个独立的问题，请你分别回答。对于 $i=1,2,\ldots,Q$，第 $i$ 个问题如下：

• 在输入给定的图 $G$ 上，添加一条连接顶点 $p_i$ 和顶点 $q_i$ 的无向边，得到新图 $G^{(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。

输入输出样例 #1

输入 #1

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

输出 #1

No
No
Yes
Yes

说明/提示

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^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 \{x_i, y_i\} \neq \{x_j, y_j\}$
• 对于所有 $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$
• 输入均为整数

样例解释 1

• 对于第 $1$ 个问题，图 $G^{(1)}$ 不是好图。因为存在一条路径 $1 \rightarrow 2 \rightarrow 5$ 连接顶点 $x_1=1$ 和 $y_1=5$。因此输出 No。
• 对于第 $2$ 个问题，图 $G^{(2)}$ 不是好图。因为存在一条路径 $2 \rightarrow 6$ 连接顶点 $x_2=2$ 和 $y_2=6$。因此输出 No。
• 对于第 $3$ 个问题，图 $G^{(3)}$ 是好图。因此输出 Yes。
• 对于第 $4$ 个问题，图 $G^{(4)}$ 是好图。因此输出 Yes。

请注意，如本输入样例所示，给定的图 $G$ 可能包含自环或重边。

由 ChatGPT 4.1 翻译