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

题目背景

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

题目描述

这是一道模板题。

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

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

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

假设你维护了一个变量 $\text{last}$，初始值为 $0$ 。

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

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

输入格式

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

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

输出格式

对于每一个$op=2$ 的询问，输出一行 Y 或 N ，表示两个节点是否连通。

样例 #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数据的加入，数据分布并非如下文所述。下面的仅供参考。

对于数据点 $1$，$n \leq 200,m \leq 200$

对于数据点 $2$，$n=5,m \leq 30$

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

对于数据点 $4$，$n=300,m \leq 50000$

对于数据点 $5$，$n=5000,m \leq 200000$，没有操作 $1$，其中约 $70 \%$ 是操作 $2$。

对于数据点 $6$，$n=5000,m \leq 200000$，没有操作 $1$，其中约 $70 \%$ 是操作 $0$。

对于数据点 $7$、$8$，$n=100,m \leq 500000$

对于数据点 $9$，$n=5000,m \leq 500000$，图是一棵树，其直径 $\leq 30$ 。

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

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