分数: 450 点
问题陈述
给你一个无向图 N 顶点和零边。
顶点已编号 1,2,\dots,N,最初所有顶点都是白色的。
进程总共 Q 以下三种类型的查询:
- 类型 1 :添加连接顶点的无向边 u 和 v.
- 类型 2 :如果顶点 v 为白色,将其改为黑色;如果是黑色,请将其更改为白色。
- 类型 3 :判断从顶点是否可以到达黑色顶点 v 通过遍历零个或多个边;报告
Yes如果可以到达,并且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
输入
输入由标准输入按以下格式给出:
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 查询,输出答案如下:
Yes如果从顶点可以到达黑色顶点 v 通过遍历零个或多个边;No如果从顶点无法到达黑色顶点 v 通过遍历零个或多个边。
示例输入 1
5 12 3 2 2 2 3 2 1 2 5 1 3 4 3 4 3 5 1 4 5 1 1 3 3 1 2 2 3 1
示例输出 1
No Yes No Yes Yes No
在此输入中,图最初有五个顶点和零个边。
该输入包含 12 查询。
- 第一个查询是
3 2.- 此时从顶点无法到达黑色顶点 2 通过遍历零个或多个边,因此报告
No.
- 此时从顶点无法到达黑色顶点 2 通过遍历零个或多个边,因此报告
- 第二个查询是
2 2.- 顶点 2 是白色的,所以将其更改为黑色。
- 第三个查询是
3 2.- 此时黑色顶点 2 可以从顶点到达 2 通过遍历零个或多个边。因此,报告
Yes.
- 此时黑色顶点 2 可以从顶点到达 2 通过遍历零个或多个边。因此,报告
- 第四个查询是
1 2 5.- 添加连接顶点的边 2,5.
- 第 5 个查询是
1 3 4.- 添加连接顶点的边 3,4.
- 第 6 个查询是
3 4.- 此时从顶点无法到达黑色顶点 4 通过遍历零个或多个边,因此报告
No.
- 此时从顶点无法到达黑色顶点 4 通过遍历零个或多个边,因此报告
- 第 7 个查询是
3 5.- 此时黑色顶点 2 可以从顶点到达 5 通过遍历零个或多个边。因此,报告
Yes.
- 此时黑色顶点 2 可以从顶点到达 5 通过遍历零个或多个边。因此,报告
- 第 8 个查询是
1 4 5.- 添加连接顶点的边 4,5.
- 第 9 个查询是
1 1 3.- 添加连接顶点的边 1,3.
- 第 10 个查询是
3 1.- 此时黑色顶点 2 可以从顶点到达 1 通过遍历零个或多个边。因此,报告
Yes.
- 此时黑色顶点 2 可以从顶点到达 1 通过遍历零个或多个边。因此,报告
- 第 11 个查询是
2 2.- 顶点 2 是黑色的,所以将其更改为白色。
- 第 12 个查询是
3 1.- 此时从顶点无法到达黑色顶点 1 通过遍历零个或多个边,因此报告
No.
- 此时从顶点无法到达黑色顶点 1 通过遍历零个或多个边,因此报告