#122. 「强制在线」动态图连通性

内存限制:1024 MiB 时间限制:1024 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EtaoinWu

题目描述

这是一道模板题。

你要维护一张无向简单图(即没有自环,没有重边的无向图)。你被要求加入删除一条边及查询两个点是否连通。

  • 0:加入一条边。保证它不存在。
  • 1:删除一条边。保证它存在。
  • 2:查询两个点是否联通。

为了保证做法的在线性,本题采用了特殊方式的读入。

假设你维护了一个变量 lastans,初始值为 000

对于每个读入的节点 x,实际上询问、修改的节点编号是 x ^ lastans,其中 ^ 操作是二进制异或操作。

对于每次解码之后查询 u v,如果它们联通,那么 lastans 会被更新为 u;否则会被更新为 v

输入格式

输入的第一行是两个数 N MN\ MN MN≤5000,M≤500000N \leq 5000,M \leq 500000N5000,M500000

接下来 MMM 行,每一行三个数 op x y\text{op} \ x \ yop x yop\text{op}op 表示操作编号。

输出格式

对于每一个 op=2\text{op}=2op=2 的询问,输出一行 YN ,表示两个节点是否连通。

样例

样例输入 1

200 5
2 123 127
0 4 0
2 4 0
1 4 0
2 0 4

样例输出 1

N
Y
N

样例输入 2

4 10
0 1 2
0 2 3
0 3 1
2 1 4
0 0 7
2 5 0
1 3 2
2 0 5
1 0 2
2 0 5

样例输出 2

N
Y
Y
N

样例解释 2

实际解码输入:

4 10
0 1 2
0 2 3
0 3 1
2 1 4
0 4 3
2 1 4
1 2 3
2 1 4
1 1 3
2 1 4

数据范围与提示

对于数据点 1,N≤200,M≤200N \leq 200,M \leq 200N200,M200

对于数据点 2,N=5,M≤30N=5,M \leq 30N=5,M30

对于数据点 3,N=10,M≤1000N=10,M \leq 1000N=10,M1000,其中查询的次数 ≥900\geq 900900 次。

对于数据点 4,N=300,M≤50000N=300,M \leq 50000N=300,M50000

对于数据点 5,N=5000,M≤200000N=5000,M \leq 200000N=5000,M200000,没有操作 1,其中约 70%70 \%70% 是操作 2。

对于数据点 6,N=5000,M≤200000N=5000,M \leq 200000N=5000,M200000,没有操作 1,其中约 70%70 \%70% 是操作 0。

对于数据点 7、8,N=100,M≤500000N=100,M \leq 500000N=100,M500000

对于数据点 9,N=5000,M≤500000N=5000,M \leq 500000N=5000,M500000,图是一棵树,其直径 ≤30 \leq 3030

对于数据点 10, N=5000,M≤500000N=5000,M \leq 500000N=5000,M500000,图是一棵树,其每个点度数 ≤10 \leq 1010

P.S. 其实 9 是菊花,10 是单链,而没有放随机树的点...