分数: 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.
