059 - Many Graph Queries(★7) Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 7

問題文

N 頂点 M 辺の有向グラフが与えられます。このグラフにおいて、辺 i は頂点 X_i から Y_i に向かいます。

Q 個の、次の形式のクエリに答えてください。

  • クエリ j: 頂点 A_j から B_j まで、辺を向きのとおりに通って移動することは可能か?

制約

  • 2\leq N\leq 10^5
  • 1\leq M\leq 10^5
  • 1\leq Q\leq 10^5
  • 1\leq X_i < Y_i\leq N
  • 1\leq A_j < B_j\leq N
  • 入力はすべて整数

小課題

  1. (2 点): N,M,Q\leq 2000
  2. (5 点): 追加の制約はない。

入力

入力は、以下の形式で与えられます。

N M Q
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M
A_1 B_1
A_2 B_2
\vdots
A_Q B_Q

出力

j 行目には、頂点 A_j から B_j まで移動可能なら Yes を、そうでなければ No を 出力してください。


入力例 1

6 6 3
1 3
2 4
1 4
4 6
5 6
1 5
2 6
1 5
3 6

出力例 1

Yes
Yes
No

1,2 番目のクエリでは、2\rightarrow4\rightarrow6, 1\rightarrow5 と移動できます。 3 番目のクエリでは、移動不可能です。


入力例 2

3 2 2
1 2
1 2
1 2
2 3

出力例 2

Yes
No

グラフは単純とは限りません。


入力例 3

2 1 1
1 2
1 2

出力例 3

Yes

Source Name

「競プロ典型90問」59日目