AT_abc420_e.[ABC420E] Reachability Query

给定一个有 $N$ 个顶点且没有边的无向图。
顶点编号为 $1,2,\dots,N$，初始时所有顶点均为白色。
你需要处理共 $Q$ 个如下三种类型的操作：

• 类型 $1$：在顶点 $u$ 和 $v$ 之间添加一条无向边。
• 类型 $2$：如果顶点 $v$ 是白色，则将其变为黑色；如果是黑色，则将其变为白色。
• 类型 $3$：判断从顶点 $v$ 出发，经过若干条边（可以为零条）是否能够到达某个黑色顶点；如果可以，输出 Yes，否则输出 No。

输入由标准输入给出，格式如下：

$N$ $Q$
$\rm{Query}_1$
$\rm{Query}_2$
$\vdots$
$\rm{Query}_Q$

其中 $\rm{Query}_i$ 表示第 $i$ 个操作。

类型 $1$ 操作格式如下：

1 $u$ $v$

类型 $2$ 操作格式如下：

2 $v$

类型 $3$ 操作格式如下：

3 $v$

对于每个类型 $3$ 的操作，输出如下结果：

• 如果从顶点 $v$ 出发经过若干条边（可以为零条）能够到达某个黑色顶点，输出 Yes；
• 否则输出 No。

样例解释 1

在本输入中，图初始有五个顶点且没有边。
本输入包含 $12$ 个操作。

• 第 1 个操作为 3 2。
  • 此时无法从顶点 $2$ 出发到达任何黑色顶点，因此输出 No。
• 第 2 个操作为 2 2。
  • 顶点 $2$ 是白色，将其变为黑色。
• 第 3 个操作为 3 2。
  • 此时可以从顶点 $2$ 出发到达黑色顶点 $2$，因此输出 Yes。
• 第 4 个操作为 1 2 5。
  • 在顶点 $2$ 和 $5$ 之间添加一条边。
• 第 5 个操作为 1 3 4。
  • 在顶点 $3$ 和 $4$ 之间添加一条边。
• 第 6 个操作为 3 4。
  • 此时无法从顶点 $4$ 出发到达任何黑色顶点，因此输出 No。
• 第 7 个操作为 3 5。
  • 此时可以从顶点 $5$ 出发到达黑色顶点 $2$，因此输出 Yes。
• 第 8 个操作为 1 4 5。
  • 在顶点 $4$ 和 $5$ 之间添加一条边。
• 第 9 个操作为 1 1 3。
  • 在顶点 $1$ 和 $3$ 之间添加一条边。
• 第 10 个操作为 3 1。
  • 此时可以从顶点 $1$ 出发到达黑色顶点 $2$，因此输出 Yes。
• 第 11 个操作为 2 2。
  • 顶点 $2$ 是黑色，将其变为白色。
• 第 12 个操作为 3 1。
  • 此时无法从顶点 $1$ 出发到达任何黑色顶点，因此输出 No。

数据范围

• 所有输入均为整数。
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 6 \times 10^5$
• 类型 $1$ 操作满足以下条件：
  • $1 \le u < v \le N$
  • 对于每个操作，$u$ 和 $v$ 之间的边此前未被添加过。
• 类型 $2,3$ 操作满足以下条件：
  • $1 \le v \le N$

由 ChatGPT 4.1 翻译