题目描述

有$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≤2×10^5$

来源

• BZOJ3674
• 算法竞赛进阶指南