← 返回题目列表

AtCoder · abc435_d

G. 可达性查询2

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

分数: 425 点

问题陈述

给你一个有向图 N 顶点和 M 边缘。
顶点编号为 1 to N,以及 i-th 边是从顶点开始的有向边 X_i 到顶点 Y_i.
最初,所有顶点都是白色的。

流程 Q 按顺序查询。每个查询属于以下两种类型之一:

  • 1 v:颜色顶点 v 黑色。
  • 2 v: 判断是否可以通过从顶点追踪边到达黑色顶点 v.

约束

  • 1\leq N \leq 3\times 10^5
  • 0\leq M \leq 3\times 10^5
  • 1\leq Q \leq 3\times 10^5
  • 1\leq X_i,Y_i \leq N
  • 没有自环,即 X_i \neq Y_i.
  • 没有多重边,即 (X_i,Y_i) 是不同的。
  • 在查询中, 1 \leq v \leq N.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
X_1 Y_1
\vdots
X_M Y_M
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

\mathrm{query}_i 代表 i-第一个查询,并以下列格式之一给出:

1 v
2 v

输出

让 q 是第二类查询的数量。输出 q 行。

的 i- 第行应包含 Yes 如果在 i第二类型的第一个查询,以及 No 否则。


示例输入 1

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

示例输出 1

Yes
No
Yes
  • 最初,给定的图表如下最左图所示。
  • 通过第一个查询,顶点 3 变为黑色,如中图所示。
  • 在第二个查询中,有可能到达黑色顶点 3 从顶点 1.
  • 在第三个查询中,不可能从顶点到达黑色顶点 4.
  • 由第四个查询,顶点 5 变为黑色,如最右图所示。
  • 在第五次查询中,有可能到达黑色顶点 5 从顶点 4.

Figure