【模板】可持久化并查集

题目描述

n个集合 m个操作 操作: - `1 a b` 合并a,b所在集合 - `2 k` 回到第k次操作之后的状态(查询算作操作) - `3 a b` 询问a,b是否属于同一集合,是则输出1否则输出0

输入输出格式

输入格式


输出格式


输入输出样例

输入样例 #1

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

输出样例 #1

1
0
1

说明

$1 \le n \le 10^5, 1 \le m \le 2 \times 10^5$ By zky 出题人大神犇