問題文

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 点): 追加の制約はない。

入力例 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