可持久化并查集

题目描述

给定 $n$ 个集合,第 $i$ 个集合内初始状态下只有一个数,为 $i$。 有 $m$ 次操作。操作分为 $3$ 种: - `1 a b` 合并 $a,b$ 所在集合; - `2 k` 回到第 $k$ 次操作(执行三种操作中的任意一种都记为一次操作)之后的状态; - `3 a b` 询问 $a,b$ 是否属于同一集合,如果是则输出 $1$,否则输出 $0$。

输入输出格式

输入格式


第一行两个整数,$n,m$。 接下来 $m$ 行,每行先输入一个数 $opt$。若 $opt=2$ 则再输入一个整数 $k$,否则再输入两个整数 $a,b$,描述一次操作。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

1
0
1

说明

对于 $100\%$ 的数据,$1\le n\le 10^5$,$1\le m\le 2\times 10^5$,$1 \le a, b \le n$。