1594_「强制在线」动态图连通性

这是一道模板题。

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

0：加入一条边。保证它不存在。

1：删除一条边。保证它存在。

2：查询两个点是否联通。

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

假设你维护了一个变量 lastans，初始值为 0 。

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

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

输入的第一行是两个数 N M。N ≤ 5000 , M ≤ 500000 。

接下来 M 行，每一行三个数 op x y 。op 表示操作编号。

对于数据点 1，N ≤ 200 , M ≤ 200

对于数据点 2，N = 5 , M ≤ 30

对于数据点 3，N = 10 , M ≤ 1000，其中查询的次数 ≥ 900 次。

对于数据点 4，N = 300 , M ≤ 50000

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

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

对于数据点 7、8，N = 100 , M ≤ 500000

对于数据点 9，N = 5000 , M ≤ 500000，图是一棵树，其直径 ≤ 30 。

对于数据点 10， N = 5000 , M ≤ 500000，图是一棵树，其每个点度数 ≤ 10 。

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

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

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

Sample #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

Sample #1
N
Y
N

Sample #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