#include<stdio.h>
#define N 100009
#define M 200009

static int tree[N + M * 64], ls[N + M * 64], rs[N + M * 64], rt[M];

int n, m, tot;

void build(register int& tmp, register int l, register int r)
{
	tmp = ++ tot;
	if (l == r)
	{
		tree[tmp] = l;
		return;
	}
	register int mid = (l + r) >> 1;
	build(ls[tmp], l, mid);
	build(rs[tmp], mid + 1, r);
}

void updata(register int root, register int& tmp, register int x, register int l, register int r, register int k)
{
	tmp = ++ tot;
	tree[tmp] = tree[root], ls[tmp] = ls[root], rs[tmp] = rs[root];
	if (l == r)
		tree[tmp] = k;
	else
	{
		int mid = (l + r) >> 1;
		if (x <= mid)
			updata(ls[tmp], ls[tmp], x, l, mid, k);
		else
			updata(rs[tmp], rs[tmp], x, mid + 1, r, k);
	}
}

int query(register int root, register int l, register int r, register int x)
{
	if (l == r)
		return tree[root];
	int mid = (l + r) >> 1;
	if (x <= mid)
		return query(ls[root], l, mid, x);
	else
		return query(rs[root], mid + 1, r, x);
}

inline int find(register int root, register int x)
{
	while (x != query(root, 1, n, x))
		x = query(root, 1, n, query(root, 1, n, x));
	return x;
}

inline int read()
{
	register int ret = 0;
	register char ch = getchar();
	while (ch < '0' || ch > '9')
		ch = getchar();
	while (ch >= '0' && ch <= '9')
		ret = (ret << 1) + (ret << 3) + (ch ^ 48), ch = getchar();
	return ret;
}

int main()
{
	n = read(), m = read();
	build(rt[0], 1, n);
	int opt, u, v;
	for (int i = 1;i <= m;++ i)
	{
		opt = read(), u = read();
		if (opt == 2)
			rt[i] = rt[u];
		if (opt == 1)
			v = read(), updata(rt[i - 1], rt[i], find(rt[i - 1], u), 1, n, find(rt[i - 1], v));
		if (opt == 3)
		{
			v = read();
			if (find(rt[i - 1], u) != find(rt[i - 1], v))
				putchar('0'), putchar('\n');
			else
				putchar('1'), putchar('\n');
			rt[i] = rt[i - 1];
		}
	}
	
	return 0;
}

其他都是TLE