如题。

#include <cstdio>
//#pragma GCC optimize(3)
const int MAXN = 200005;
int n;
inline void swap(int &x, int &y) {
	static int t = x;
	x = y;
	y = t;
}
namespace PUFS {
	int fa[MAXN * 40], dep[MAXN * 40], ls[MAXN * 40], rs[MAXN * 40];
	int cnt;
	void Build(int &rt, int l, int r) {//1
		rt = ++cnt;
		if (l == r) {
			fa[rt] = l, dep[rt] = 1;
			return;
		}
		int mid = l + r >> 1;
		Build(ls[rt], l, mid);
		Build(rs[rt], mid + 1, r);
	}
	void Change(int rt, int &newrt, int l, int r, int pos, int x) {//2
		newrt = ++cnt;
		ls[newrt] = ls[rt];
		rs[newrt] = rs[rt];
		if (l == r) {
			dep[newrt] = dep[rt];
			fa[newrt] = x;
			return;
		}
		int mid = l + r >> 1;
		if (pos <= mid) Change(ls[rt], ls[newrt], l, mid, pos, x);
		else Change(rs[rt], rs[newrt], mid + 1, r, pos, x);
	}
	void Add(int rt, int &newrt, int l, int r, int pos) {
		newrt = ++cnt;
		ls[newrt] = ls[rt];
		rs[newrt] = rs[rt];
		if (l == r) {
			dep[newrt] = dep[rt] + 1;
			fa[newrt] = fa[rt];
			return;
		}
		int mid = l + r >> 1;
		if (pos <= mid) Add(ls[rt], ls[newrt], l, mid, pos);
		else Add(rs[rt], rs[newrt], mid + 1, r, pos);
	}//3
	int Query(int rt, int l, int r, int pos) {//4
		if (l == r) {
			return rt;
		}
		int mid = l + r >> 1;
		if (pos <= mid) return Query(ls[rt], l, mid, pos);
		else return Query(rs[rt], mid + 1, r, pos);
	} 
	int Find(int rt, int a) {//5
		int f = Query(rt, 1, n, a);
		return fa[f] == a ? f : Find(rt, fa[f]);
	}
	void Merge(int rt, int &newrt, int u, int v) {
		u = Find(rt, u);
		v = Find(rt, v);
		if (fa[u] != fa[v]) {
			int tmprt;
			if (dep[u] > dep[v]) swap(u, v);
			Change(rt, tmprt, 1, n, fa[u], fa[v]);
			if (dep[u] == dep[v]) Add(tmprt, newrt, 1, n, fa[v]);
			else newrt = tmprt;
		}
		else {
			newrt = rt;
		}
	}
	bool Check(int rt, int &newrt, int u, int v) {
//		//\
//		Sans - 1 Attack 1 Defense \
//		The easiest enemy in the world \
//		Can only take 1 Damage
		newrt = rt;
		u = Find(rt, u);
		v = Find(rt, v);
		return fa[u] == fa[v];
	}
	void RollBack(int rt, int &newrt) {
		newrt = rt;
	}
}
int root[MAXN];
int main() {
//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	int m;
	scanf("%d %d", &n, &m);
	PUFS::Build(root[0], 1, n);
	int lastans = 0;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		scanf("%d %d", &a, &b);
//		b ^= lastans;
		if (a == 1) {
			scanf("%d", &c);
//			c ^= lastans;
			PUFS::Merge(root[i - 1], root[i], b, c);
		}
		if (a == 2) {
			PUFS::RollBack(root[b], root[i]);
		}
		if (a == 3) {
			scanf("%d", &c);
//			c ^= lastans;
			printf("%d\n", lastans = PUFS::Check(root[i - 1], root[i], b, c));
		}
	}
	return 0;
}