#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <nmmintrin.h>
#include <chrono>
#include <list>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589
#ifdef _MSC_VER
#define __builtin_popcount _mm_popcnt_u32
#define __builtin_popcountll _mm_popcnt_u64
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

class UFNode;
class LNode;


class LNode {
public:
	UFNode *Myval;
	LNode *Prev, *Next;
	LNode() :Prev(NULL), Next(NULL), Myval(NULL) {}
	LNode(LNode *pr, LNode *nx, UFNode *val) :Prev(pr), Next(nx), Myval(val) {}
	void Isolate() {
		if (this->Prev) {
			this->Prev->Next = this->Next;
			this->Next->Prev = this->Prev;
		}

		this->Prev = NULL;
		this->Next = new LNode;
	}
	static void Isolate(LNode* st, LNode* en) {
		if (st->Prev) {
			st->Prev->Next = en->Next;
			en->Next->Prev = st->Prev;
		}

		st->Prev = NULL;
		en->Next = new LNode;
	}
	static void Insert(LNode* lis, LNode* nod) {
		nod->Isolate();
		delete nod->Next;

		nod->Prev = lis->Prev;
		nod->Next = lis;
		if (lis->Prev)
			lis->Prev->Next = nod;
		lis->Prev = nod;
	}
	static void Splice(LNode* pl, LNode* st, LNode* en) {
		Isolate(st, en);
		delete en->Next;
		en->Next = pl;
		st->Prev = pl->Prev;
		if (pl->Prev)
			pl->Prev->Next = st;
		pl->Prev = en;
	}
};

class UFNode {
public:
	UFNode* p;
	int rank = 0, elem, NLcou = 0, Ccou = 0;;
	LNode *NLnode, *DFSnode, *Cnode;
	LNode* Child, *Chlast, *NLlast;
	LNode *DFSlast;

	UFNode(int element, UFNode* par) :elem(element), p(par) {
		DFSlast = new LNode;
		DFSnode = new LNode(NULL, new LNode, this);
		NLnode = new LNode(NULL, new LNode, this);
		Cnode = new LNode(NULL, new LNode, this);

		NLlast = NULL;
		Chlast = new LNode;
		Child = Chlast;
	}


};

class UnionFind_Deletion {
public:
	int n, setcou = 0;
	vector<UFNode*> element;

	UnionFind_Deletion(int size) : n(size), element(n, NULL) {
		REP(i, n) {
			element[i] = new UFNode(i, NULL);
			element[i]->p = element[i];
		}
	}
	bool isReduced(UFNode* root) {
		return root->Ccou < 4 && !root->NLcou;
	}
	bool isRoot(UFNode* node) {
		return node->p == node;
	}

	void Unite(int a, int b) {
		UFNode *ap = Find(a),
			*bp = Find(b);
		if (ap == bp)return;
		if (ap->rank < bp->rank) swap(ap, bp);
		else if (ap->rank == bp->rank && ap->Ccou < bp->Ccou) swap(ap, bp);

		if (isReduced(bp) && bp->Ccou < 3) {

			while (bp->Child->Myval != NULL) {
				bp->Child->Myval->p = ap;
				bp->Child->Myval->rank = 0;
				ap->Ccou++;
				LNode* buf = bp->Child->Next;
				LNode::Insert(ap->Child, bp->Child);
				ap->Child = bp->Child;
				LNode::Insert(ap->DFSnode->Next, bp->Child->Myval->DFSnode);
				bp->Child = buf;
			}

			bp->p = ap;
			bp->rank = 0;
			ap->Ccou++;
			LNode::Insert(ap->Child, bp->Cnode);
			ap->Child = bp->Cnode;
			LNode::Insert(ap->DFSnode->Next, bp->DFSnode);
			ap->rank = max(ap->rank, 1);
		}
		else {
			bp->p = ap;
			if (ap->rank == bp->rank)
				ap->rank++;
			ap->Ccou++;
			LNode::Insert(ap->Child, bp->Cnode);
			ap->Child = bp->Cnode;

			LNode::Insert(ap->NLnode, bp->NLnode);
			LNode::Splice(bp->DFSnode->Next, bp->DFSnode, bp->DFSlast);
		}
	}

	UFNode* Relink(UFNode* a) {
		if (isRoot(a->p)) return a;
		if (a->p->Chlast->Myval != a) {
			LNode::Insert(a->p->p->Cnode->Next, a->Cnode);
			LNode::Splice(a->p->DFSnode, a->DFSnode, a->p->DFSnode->Prev);
		}
		else {
			LNode::Insert(a->p->p->Chlast, a->Cnode);
			LNode::Insert(a->p->p->DFSlast, a->DFSnode);
		}

		a->Cnode->Isolate();

		if (a->p->Ccou) {
			a->p->rank = 0;
			if (isRoot(a->p->p)) {
				a->p->NLnode->Isolate();
				if (a->p->p->NLcou)
					a->p->p->rank = 1;
			}

		}
		if (a->p->Ccou == 2)
			for (auto itr = a->p->Cnode; itr->Myval != NULL; itr = itr->Next)
				Relink(itr->Myval);
		return a;
	}

	UFNode* Find(int a) {
		UFNode* x = element[a];
		while (!isRoot(x->p)) {
			UFNode* t = x->p;
			Relink(x);
			x = t;
		}
		return x->p;
	}

	void Delete(int a) {
		UFNode* x = element[a], *rt = Find(a);

		if (!x->Ccou) {
			x->p->Ccou--;
			x->Cnode->Isolate();
			x->DFSnode->Isolate();
		}
		else {
			if (isReduced(rt)) {
				UFNode* nrt = x->Cnode->Myval;
				for (auto itr = x->Cnode; itr->Myval != NULL; itr = itr->Next) {
					itr->Myval->p = nrt;
					LNode::Insert(nrt->DFSlast, itr);
					if (itr->Myval != nrt)
						LNode::Insert(nrt->Chlast, itr);
				}
				delete x;
			}
			else {
				UFNode *leaf, *par;
				if (isRoot(x->p))
					leaf = x->DFSlast->Prev->Myval;
				else {
					if (x->Cnode->Next)
						leaf = x->Cnode->Next->Myval->DFSnode->Prev->Myval;
					else
						leaf = x->DFSnode->Prev->Myval;
				}
				swap(x->elem, leaf->elem);


				par = leaf->p;

				leaf->p->Ccou--;
				leaf->Cnode->Isolate();
				leaf->DFSnode->Isolate();


				if (!isReduced(par)) {
					if (isRoot(par)) {
						UFNode* nl = par->NLnode->Myval;

						Relink(nl->Child->Next->Next->Myval);
						Relink(nl->Child->Next->Myval);
						Relink(nl->Child->Myval);
					}
					else {
						Relink(par->Child->Next->Myval);
						Relink(par->Child->Myval);
					}
				}
			}
		}
	}

};

signed main() {

	int n, q;

	scanf("%d %d", &n, &q);
	UnionFind_Deletion ufd(n);
	REP(i, q) {
		int mode;
		int a, b;
		scanf("%d", &mode);

		switch (mode) {
		case 0://Unite
			scanf("%d %d", &a, &b);
			ufd.Unite(a, b);
			break;
		case 1://Find
			scanf("%d %d", &a, &b);
			printf(ufd.Find(a) == ufd.Find(b) ? "1\n" : "0\n");
			break;
		case 2://Delete
			scanf("%d", &a);
			ufd.Delete(a);
			break;
		}
	}


	return 0;
}

Measured memory_bytes: 13804