Migrated from Lutece 2555 土豆的集合

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

每次题面编不太下去的时候，就让土豆成为故事的男主，题面就会变得有趣起来……

土豆定义了土豆集合，他最开始有 $n$ 个土豆集合，第 $i$ 号土豆集合里面只含有 $i$ 这一个整数。

土豆接下来会进行 $m$ 次集合运算，土豆定义了土豆集合的三种运算：

• $\texttt{1 i j}$ ：将 $i$ 和 $j$ 两个整数所在的土豆集合进行合并。
• $\texttt{2 t}$：回退到第 $t$ 次运算后的状态。
• $\texttt{3 i j}$：判断整数 $i$ 和 $j$ 是否在同一个土豆集合里面。

特别的，土豆把初始状态看作第 $0$ 次运算后的结果。

Input

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

接下来有 $m$ 行，每行先输入一个整数 $q$。如果 $q=2$，余下再输入一个整数 $t$；否则，余下再输入两个整数 $i,j$。每一行的第一个数 $q$ 表示进行土豆对当时手里的土豆集合进行 $q$ 号运算，数字 $q$ 后面的数为运算所需要的参数。

Output

对于每次 $q=3$，如果答案是肯定的，输出 $1$，否则输出 $0$。

Samples

6 7
3 2 3
1 2 3
3 2 4
1 3 4
3 2 4
2 3 
3 2 4

0
0
1
0

Constraints

$1\leq m \leq 10^6$ $1\leq n \leq 3\times 10^5$ $1\leq q \leq 3$ $1\leq i,j \leq n$

Resources

2021 UESTC ICPC Training for Data Structures