可达性询问 2

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条有向边的图。顶点编号为 $1$ 到 $N$，第 $i$ 条边从顶点 $X_i$ 指向顶点 $Y_i$。初始时，所有顶点均为白色。

请依次处理 $Q$ 个操作：

• 1 v：将顶点 $v$ 染成黑色。已经为黑色的顶点仍保持黑色。
• 2 v：判断能否从顶点 $v$ 出发，沿零条或多条有向边到达某个黑色顶点。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行包含两个整数 $X_i,Y_i$，表示一条从 $X_i$ 指向 $Y_i$ 的有向边。

下一行包含一个整数 $Q$。

接下来 $Q$ 行，每行包含两个整数，格式为 1 v 或 2 v，含义如题目描述所示。

输出格式

对于每个 2 v 操作输出一行。如果存在所述路径，输出 Yes；否则输出 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

数据范围

• $1\le N\le 3\times 10^5$；
• $0\le M\le 3\times 10^5$；
• $1\le Q\le 3\times 10^5$；
• $1\le X_i,Y_i\le N$，且 $X_i\ne Y_i$；
• 图中不存在重边；
• 操作中的 $v$ 均满足 $1\le v\le N$；
• 所有输入均为整数。

样例解释

第一次操作将顶点 $3$ 染黑，因此顶点 $1$ 可以沿路径到达黑色顶点 $3$。此时顶点 $4$ 不能到达任何黑色顶点。将顶点 $5$ 染黑后，顶点 $4$ 可以直接到达顶点 $5$。