分数: 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 可能具有自循环或多边。