先 MLE，之后把 ll 去掉就变成 WA 了。

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)

using namespace std;

const int inf = 0x3f3f3f3f,mod = 1e9 + 7;
const int maxn = 1.5e5 + 7, maxm = 1e6 + 7;

int n, m;
int tot, ls[maxn << 5], rs[maxn << 5], fa[maxn << 5], siz[maxn << 5], root[maxm];

inline void Build(int l, int r, int &p) {
	p = ++tot;
	if(l == r) { fa[p] = l, siz[p] = 1; return; }
	int mid = (l + r) >> 1;
	Build(l, mid, ls[p]), Build(mid + 1, r, rs[p]);
}

inline void ModifyFa(int pre, int &p, int l, int r, int k, int v) {
	p = ++tot, ls[p] = ls[pre], rs[p] = rs[pre], fa[p] = fa[pre], siz[p] = siz[pre];
	if(l == r) { fa[p] = v; return; }
	int mid = (l + r) >> 1;
	if(k <= mid) ModifyFa(ls[pre], ls[p], l, mid, k, v);
	else ModifyFa(rs[pre], rs[p], mid + 1, r, k, v);
}

inline void ModifySize(int pre, int &p, int l, int r, int k, int v) {
	p = ++tot, ls[p] = ls[pre], rs[p] = rs[pre], fa[p] = fa[pre], siz[p] = siz[pre];
	if(l == r) { siz[p] = v; return; }
	int mid = (l + r) >> 1;
	if(k <= mid) ModifySize(ls[pre], ls[p], l, mid, k, v);
	else ModifySize(rs[pre], rs[p], mid + 1, r, k, v);
}

inline int QueryFa(int p, int l, int r, int k) {
	if(l == r) return fa[p];
	int mid = (l + r) >> 1;
	if(k <= mid) return QueryFa(ls[p], l, mid, k);
	else return QueryFa(rs[p], mid + 1, r, k);
}

inline int QuerySize(int p, int l, int r, int k) {
	if(l == r) return siz[p];
	int mid = (l + r) >> 1;
	if(k <= mid) return QuerySize(ls[p], l, mid, k);
	else return QuerySize(rs[p], mid + 1, r, k);
}

inline int Find(int x, int id) {
	int fa = QueryFa(root[id], 1, n, x);
	return x == fa ? x : Find(fa, id);
}

inline void Merge(int x, int y, int id) {
	x = Find(x, id), y = Find(y, id);
	if(x == y) { root[id + 1] = root[id]; return; }
	int sizx = QuerySize(root[id], 1, n, x), sizy = QuerySize(root[id], 1, n, y);
	if(sizx < sizy) swap(x, y), swap(sizx, sizy);
	ModifyFa(root[id], root[id + 1], 1, n, y, x); ModifySize(root[id + 1], root[id + 1], 1, n, x, sizx + sizy);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m; Build(1, n, root[0]);
	F(i, 1, m) {
		int op, a, b; cin >> op >> a;
		if(op == 2) root[i] = root[a];
		else if(op == 1) {
			cin >> b;
			Merge(a, b, i - 1);
			
		} else {
			cin >> b;
			root[i] = root[i - 1];
			cout << (Find(a, i) == Find(b, i)) << '\n'; 
		}
	}

	return 0;
}