【模板】可持久化并查集

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

初始有 $n$ 个互不相交的集合，第 $i$ 个集合只包含元素 $i$。依次执行 $m$ 个操作：

• 1 a b：合并元素 $a,b$ 所在的集合；
• 2 k：令当前状态回到第 $k$ 次操作完成后的状态。特别地，$k=0$ 表示初始状态；
• 3 a b：询问元素 $a,b$ 当前是否属于同一集合。若是输出 $1$，否则输出 $0$。

任意一种操作都占用一个操作编号。回退操作保证 $0\le k<i$，其中 $i$ 是当前操作编号。

输入格式

第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行描述一个操作。操作 2 后有一个整数 $k$，其余操作后有两个整数 $a,b$。

输出格式

对于每个操作 3，输出一行一个整数表示答案。

样例输入

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

样例输出

1
0
1

数据范围

对于全部数据，$1\le n\le10^5$，$1\le m\le2\times10^5$，$1\le a,b\le n$，回退操作满足 $0\le k<i$。

所有测试点均独立计分且分值相同。