2067. [BZOJ 3674] 可持久化并查集加强版

【题目描述】

有 n 个集合，m 个操作，操作分为三种：

1 a b ——合并 a,b 所在集合;

2 k ——回到输入的第 k 次操作之后的状态;

3 a b ——询问 a,b 是否属于同一集合，是则输出 1 否则输出 0。

【输入格式】

第一行为 n，m。

接下来 m 行描述了每个操作，按照题目描述中所述的格式。

每个操作强制在线，需要对输入的 a,b,k 进行运算得到真实的 a,b,k 后再执行操作，运算方法为 x=x xor lastans，lastans 表示上一个询问的答案，其初始值为 0。

【输出格式】

对于每个询问操作，输出一个结果，每个结果占一行。

【输入样例】

5 6
1 1 2
3 1 2
2 1
3 0 3
2 1
3 1 2

【输出样例】

1
0
1

【数据范围】

$0<n,m\leq 2\times 10^5$