rt

#include <iostream>
#include <cstring>
#include <algorithm>
#include <ctype.h>

const int N = 2 * 1e5 + 5;

inline int read()
{
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 3) + (s << 1) + (c ^ 48);
	return s * w;
}

struct Node {
    int l, r, father, dep;
}tr[N * 4 + N * 19];

int root[N], res, n, m, idx;

inline int build(int l, int r) {
    int q = ++ idx;
    
    if (l == r) {
        tr[q].father = l;
        tr[q].dep = 1;
        return q;
    }
    
    int mid = l + r >> 1;
    tr[q].l = build(l, mid), tr[q].r = build(mid + 1, r);
    
    return q;
}

inline int insert(int p, int l, int r, int a, int b) {
    int q = ++ idx;
    
    if (l == r) {
        tr[q].father = b;
        tr[q].dep = tr[p].dep;
        return q;
    }
    
    tr[q].l = tr[p].l;
    tr[q].r = tr[p].r;
    
    int mid = l + r >> 1;
    if (a <= mid) tr[q].l = insert(tr[p].l, l, mid, a, b);
    else tr[q].r = insert(tr[p].r, mid + 1, r, a, b);
    
    return q;
}

inline int add(int p, int l, int r, int x)
{
	int q = ++ idx;
	tr[q] = tr[p];
	if (l == r)
	{
		tr[q].dep ++ ;
		return q;
	}
	
	int mid = l + r >> 1;
	if (x <= mid) tr[q].l = add(tr[p].l, l, mid, x);
	else tr[q].r = add(tr[p].r, mid + 1, r, x);
	return q;
}

inline int query(int q, int l, int r, int x) {
    if (l == r) return q;
    
    int mid = l + r >> 1;
    if (x <= mid) return query(tr[q].l, l, mid, x);
    else return query(tr[q].r, mid + 1, r, x);
}

inline int find(int p, int x) {
    int k = query(p, 1, n, x);
    
    if (tr[k].father != x) return find(p, tr[k].father);
    return k;
}

int main() {
    n = read(), m = read();
    root[0] = build(1, n);
    int op, a, b, k;
    for (int i = 1; i <= m; i ++ ) {
       	op = read();
        
        root[i] = root[i - 1];
        
        if (op == 1) {
            a = read(), b = read();
            
            int pa = find(root[i], a), pb = find(root[i], b);
            
            if (tr[pa].father == tr[pb].father) continue;
            if (tr[pa].dep > tr[pb].dep) std::swap(pa, pb);
            root[i] = insert(root[i], 1, n, tr[pa].father, tr[pb].father);
			if (tr[pa].dep == tr[pb].dep) add(root[i], 1, n, tr[pb].father);
        }
        if (op == 2) {
            k = read();
            
            root[i] = root[k];
        }
        if (op == 3) {
            a = read(), b = read();
            
            int pa = find(root[i], a), pb = find(root[i], b);
            
            res = pa == pb;
            printf("%d\n", res);
        }
    }
    
    return 0;
}