E - Good Graph Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 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 を結ぶ無向辺を 1 本追加して得られるグラフ G^{(i)} は良いグラフですか？

という質問です。

制約

  • 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 \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 番目の質問に対する答えを出力せよ。 具体的には、グラフ G^{(i)} が良いグラフである場合は Yes を、良いグラフでない場合は 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
  • 1 番目の質問に関して、グラフ G^{(1)} は良いグラフではありません。なぜなら、頂点 x_1 = 1 と頂点 y_1 = 5 を結ぶパス 1 \rightarrow 2 \rightarrow 5 を持つからです。よって、No と出力します。
  • 2 番目の質問に関して、グラフ G^{(2)} は良いグラフではありません。なぜなら、頂点 x_2 = 2 と頂点 y_2 = 6 を結ぶパス 2 \rightarrow 6 を持つからです。よって、No と出力します。
  • 3 番目の質問に関して、グラフ G^{(3)} は良いグラフです。よって、Yes と出力します。
  • 4 番目の質問に関して、グラフ G^{(4)} は良いグラフです。よって、Yes と出力します。

この入力例のように、与えられるグラフ G が自己ループや多重辺を持つ場合があることに注意してください。

Score : 475 points

Problem Statement

You are given an undirected graph G with N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge is an undirected edge connecting vertices u_i and v_i.

A graph with N vertices is called good if the following condition holds for all i = 1, 2, \ldots, K:

  • there is no path connecting vertices x_i and y_i in G.

The given graph G is good.

You are given Q independent questions. Answer all of them. For i = 1, 2, \ldots, Q, the i-th question is as follows.

  • Is the graph G^{(i)} obtained by adding an undirected edge connecting vertices p_i and q_i to the given graph G good?

Constraints

  • 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
  • For all i = 1, 2, \ldots, K, there is no path connecting vertices x_i and y_i.
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq p_i, q_i \leq N
  • p_i \neq q_i
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print Q lines. For i = 1, 2, \ldots, Q, the i-th line should contain the answer to the i-th question: Yes if the graph G^{(i)} is good, and No otherwise.

Sample Input 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

Sample Output 1

No
No
Yes
Yes
  • For the first question, the graph G^{(1)} is not good because it has a path 1 \rightarrow 2 \rightarrow 5 connecting vertices x_1 = 1 and y_1 = 5. Therefore, print No.
  • For the second question, the graph G^{(2)} is not good because it has a path 2 \rightarrow 6 connecting vertices x_2 = 2 and y_2 = 6. Therefore, print No.
  • For the third question, the graph G^{(3)} is good. Therefore, print Yes.
  • For the fourth question, the graph G^{(4)} is good. Therefore, print Yes.

As seen in this sample input, note that the given graph G may have self-loops or multi-edges.