#4608. 121. 「离线可过」动态图连通性

121. 「离线可过」动态图连通性

【模板】动态图完全连通性

题目背景

这是 LOJ #122 的一个非官方、不维护的镜像,原始出题人是 EtaoinWu ,在本站的原始上传者未知。这个镜像题的数据不保证是最新的,因此推荐到 LOJ 进行练习。

题目描述

这是一道模板题。

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

0.0.:加入一条边。保证它不存在。 1.1.:删除一条边。保证它存在。 2.2.:查询两个点是否联通。

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

假设你维护了一个变量 last\text{last},初始值为 00

对于每个读入的节点 xx,实际上询问、修改的节点编号是 x xor lastx \text{ xor } \text{last},其中 xor\text{xor} 是二进制异或操作。

对于每次解码之后查询 u,vu,v,如果它们联通,那么 last\text{last} 会被更新为 uu;否则会被更新为 vv

输入格式

输入的第一行是两个数 n,mn,m

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

N
Y
N

样例 #2

样例输入 #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

提示

由于hack数据的加入,数据分布并非如下文所述。下面的仅供参考。

对于数据点 11n200,m200n \leq 200,m \leq 200

对于数据点 22n=5,m30n=5,m \leq 30

对于数据点 33n=10,m1000n=10,m \leq 1000,其中查询的次数 900\geq 900 次。

对于数据点 44n=300,m50000n=300,m \leq 50000

对于数据点 55n=5000,m200000n=5000,m \leq 200000,没有操作 11,其中约 70%70 \% 是操作 22

对于数据点 66n=5000,m200000n=5000,m \leq 200000,没有操作 11,其中约 70%70 \% 是操作 00

对于数据点 7788n=100,m500000n=100,m \leq 500000

对于数据点 99n=5000,m500000n=5000,m \leq 500000,图是一棵树,其直径 30\leq 30

对于数据点 1010n=5000,m500000n=5000,m \leq 500000,图是一棵树,其每个点度数 10\leq 10

还有一些保证 n5000,m500000n \leq 5000,m \leq 500000 的附加数据。