← 返回题目列表

AtCoder · typical90_bg

059. 大量图查询(★7)

中文机器翻译题面 查看原题

配点: 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