#320. 「可持久化并查集」 可持久化并查集加强版

「可持久化并查集」 可持久化并查集加强版

可持久化并查集

题目描述

给定 nn 个集合,第 ii 个集合内初始状态下只有一个数,为 ii

mm 次操作。操作分为 33 种:

  • 1 a b 合并 a,ba,b 所在集合;
  • 2 k 回到第 kk 次操作(执行三种操作中的任意一种都记为一次操作)之后的状态;
  • 3 a b 询问 a,ba,b 是否属于同一集合,如果是则输出 11,否则输出 00

输入格式

第一行两个整数,n,mn,m

接下来 mm 行,每行先输入一个数 optopt。若 opt=2opt=2 则再输入一个整数 kk,否则再输入两个整数 a,ba,b,描述一次操作。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

1
0
1

提示

对于 100%100\% 的数据,1n1051\le n\le 10^51m2×1051\le m\le 2\times 10^51a,bn1 \le a, b \le n