P3402 【模板】可持久化并查集

给定 $n$ 个集合，第 $i$ 个集合内初始状态下只有一个数，为 $i$。 有 $m$ 次操作。操作分为 $3$ 种： - `1 a b` 合并 $a,b$ 所在集合； - `2 k` 回到第 $k$ 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态，保证已经进行过至少 $k$ 次操作（不算本次操作），特别的，若 $k=0$，则表示回到初始状态； - `3 a b` 询问 $a,b$ 是否属于同一集合，如果是则输出 $1$，否则输出 $0$。

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

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

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