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
- 入力はすべて整数
小課題
- (2 点): N,M,Q\leq 2000
- (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