1 #include <bits/stdc++.h>

 2 using namespace std;

 3 const int N = 3e5 + 10;

 4 int n, m, rt[N * 30];

 5 struct node {

 6     int ls, rs, dep, fa;//fa的值都是在1~n范围中的

 7 }t[N * 30];

 8 namespace SegmentTree {

 9     #define mid ((l + r) >> 1)

10     #define lson t[i].ls, l, mid

11     #define rson t[i].rs, mid + 1, r

12     int cnt;

13     void build(int &i, int l, int r) {

14         i = ++ cnt;

15         if (l == r) {t[i].fa = l; return ;}//初始时节点父亲就是自己

16         build(lson), build(rson);

17     }

18     void merge(int j, int &i, int l, int r, int pos1, int pos2) {

19         //pos1是深度较小的节点的fa，找到pos1的位置，将该位置的fa改为pos2，也就是合并操作

20         i = ++ cnt;

21         t[i] = t[j];//复制

22         if (l == r) {

23             t[i].fa = pos2;

24             return ;

25         }

26         if (pos1 <= mid) merge(t[j].ls, lson, pos1, pos2);

27         else merge(t[j].rs, rson, pos1, pos2);

28     }

29     void update(int i, int l, int r, int pos) {

30         if (l == r) {t[i].dep ++; return ;}

31         if (pos <= mid) update(lson, pos);

32         else update(rson, pos);

33     }

34     int query(int i, int l, int r, int pos) {//返回节点pos的编号

35         if (l == r) return i;

36         if (pos <= mid) return query(lson, pos);

37         else return query(rson, pos);

38     }

39     int find(int i, int pos) {//类似并查集找祖先操作

40         int now = query(i, 1, n, pos);

41         if (t[now].fa == pos) return now;//也是返回节点编号

42         return find(i, t[now].fa);

43     }

44     #undef mid

45     #undef lson

46     #undef rson

47 }

48 using namespace SegmentTree;

49 int main() {

50     scanf("%d %d", &n, &m);

51     build(rt[0], 1, n);

52     for (int i = 1; i <= m; i ++) {

53         int opt, x, y;

54         scanf("%d %d", &opt, &x);

55         if(opt == 1) {//合并x, y所在集合

56             scanf("%d", &y);

57             int posx, posy;

58             rt[i] = rt[i - 1];//复制新版本

59             posx = find(rt[i], x), posy = find(rt[i], y);

60             if (t[posx].fa != t[posy].fa) {//按秩合并

61                 if (t[posx].dep > t[posy].dep) swap(posx, posy);

62                 merge(rt[i - 1], rt[i], 1, n, t[posx].fa, t[posy].fa);

63                 if (t[posx].dep == t[posy].dep) update(rt[i], 1, n, t[posy].fa);

64                 //避免深度相同

65             }

66         }

67         else if(opt == 2) rt[i] = rt[x];

68         else if(opt == 3) {

69             scanf("%d", &y);

70             rt[i] = rt[i - 1];

71             int posx, posy;

72             posx = find(rt[i], x), posy = find(rt[i], y);

73             if (t[posx].fa == t[posy].fa) puts("1");

74             else puts("0");

75         }

76     }

77     return 0;

78 }