Description

Given $n$ sets, the $i$-th set initially contains only the element $i$.

There are $m$ operations, of three types:

• 1 a b Merge the sets containing $a$ and $b$;
• 2 k Revert to the state right after the $k$-th operation (any of the three types counts as one operation). It is guaranteed that at least $k$ operations have already been performed (not counting this one). In particular, if $k=0$, revert to the initial state;
• 3 a b Query whether $a$ and $b$ belong to the same set; if yes, output $1$, otherwise output $0$.

Input Format

The first line contains two integers $n$ and $m$.

Then follow $m$ lines. On each line, first read an integer $opt$. If $opt=2$ then read an integer $k$; otherwise read two integers $a, b$, describing one operation.

Output Format

For each operation of type $3$, output one line with one integer indicating the answer.

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

1
0
1

Hint

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 2 \times 10^5$, $1 \le a, b \le n$.

Translated by ChatGPT 5