← 返回题目列表

AtCoder · abc304_e

H. 好图

中文机器翻译题面 查看原题

分数: 475 点

问题陈述

给你一个无向图 G 与 N 顶点和 M 边缘。 对于 i = 1, 2, \ldots, M, i-th 边是连接顶点的无向边 u_i 和 v_i.

图表 N 顶点被称为 好 如果以下条件适用于所有 i = 1, 2, \ldots, K:

  • 没有连接顶点的路径 x_i 和 y_i in G.

给定的图表 G 很好。

你被给予 Q 独立问题。全部回答。 对于 i = 1, 2, \ldots, Q, i第一个问题如下。

  • 是图表 G^{(i)} 通过添加连接顶点的无向边获得 p_i 和 q_i 到给定的图表 G 好不好?

约束

  • 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
  • 所有输入值均为整数。

输入

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

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第一个问题: Yes 如果图表 G^{(i)} 很好,并且 No 否则。


示例输入 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
  • 对于第一个问题,该图 G^{(1)} 不好,因为它有路径 1 \rightarrow 2 \rightarrow 5 连接顶点 x_1 = 1 和 y_1 = 5。因此,打印 No.
  • 对于第二个问题,该图 G^{(2)} 不好,因为它有路径 2 \rightarrow 6 连接顶点 x_2 = 2 和 y_2 = 6。因此,打印 No.
  • 对于第三个问题,图表 G^{(3)} 很好。因此,打印 Yes.
  • 对于第四个问题,该图 G^{(4)} 很好。因此,打印 Yes.

如本示例输入所示,请注意给定的图表 G 可能具有自循环或多边。