stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <string>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <algorithm>



using namespace std;



#define rep(i,j) REP((i), 0, (j))

#define REP(i,j,k) for(int i=(j);(i)<(k);++i)

#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))

#define ALL(v) (v).begin(), (v).end()

#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))

#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)

#define SQ(x) ((x)*(x))

#define Mod(x, mod) (((x)+(mod)%(mod))

#define MP make_pair

#define PB push_back

#define F first

#define S second

#define INF 1 << 30

#define EPS 1e-10

#define MOD 1000000007



typedef pair<int, int> pi;

typedef pair<int, pi> pii;

typedef vector<int> vi;

typedef queue<int> qi;

typedef long long ll;



struct UF{

  int par[10001];

  int rank[10001];



  UF(int n){ init(n); }

  void init(int n){

    for(int i=0;i<n;i++){

      par[i] = i;

      rank[i] = 0;

    }

  }



  int find(int x){

    if(par[x] == x) return x;

    else return par[x] = find(par[x]);

  }



  void unite(int x, int y){

    x = find(x);

    y = find(y);

    if(x == y) return;

    if(rank[x] < rank[y]){

      par[x] = y;

    }else{

      par[y] = x;

      if(rank[x] == rank[y]) rank[x]++;

    }

  }



  int same(int x,int y){

    return find(x) == find(y);

  }

};



int main(){

  int n ,q;

  scanf("%d%d", &n, &q);

  UF uf(n);



  rep(i, q){

    int com, x, y;

    scanf("%d%d%d", &com, &x, &y);

    if(com){

      printf("%d\n", uf.same(x, y)?1:0);

    }else{

      uf.unite(x, y);

    }

  }

  

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.881976389365412x):
#include <cstdio>

#include <cstring>

#include <algorithm>



using namespace std;



struct UnionFind{

  int par[10005];

  int rank[10005];

  UnionFind(int n){ init(n);}

  void init(int n){

    for(int i=0;i<n;i++){

      par[i] = i;

      rank[i] = 0;

    }

  }

  int find(int x){

    if(x == par[x]) return x;

    return par[x] = find(par[x]);

  }

  int same(int x, int y){

    return find(x) == find(y);

  }

  void unite(int x, int y){

    x = find(x); y = find(y);

    if(x==y) return;

    if(rank[x] < rank[y]){

      par[x] = y;

    }else{

      par[y] = x;

      if(rank[x] == rank[y]) rank[x]++;

    }

  }

};



int main(){

  int n,q;

  scanf("%d%d",&n,&q);

  UnionFind uf(n);

  while(q--){

    int com, x,y;

    scanf("%d%d%d",&com,&x,&y);

    if(com) printf("%d\n", uf.same(x,y));

    else uf.unite(x,y);

  }

  return 0;

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[x].size() > f[y].size()) {

				for(int j = f[y].size() - 1; j >= 0; j--) {

					group[f[y][j]] = group[x];

					f[x].push_back(f[y][j]);

					f[y].pop_back();

				}

			}

			else {

				for(int j = f[x].size() - 1; j >= 0; j--) {

					group[f[x][j]] = group[y];

					f[y].push_back(f[x][j]);

					f[x].pop_back();

				}

			}

		}

		else {

			printf("%d\n", (group[x] == group[y] ? 1 : 0));

		}

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2255437890380687x):
#include <vector>

#include <iostream>

using namespace std;

class UnionFind {

private:

	int size_; vector<int> g; vector<vector<int> > v;

public:

	UnionFind() : size_(0), g(vector<int>()), v(vector<vector<int> >()) {};

	UnionFind(int size__) : size_(size__) {

		g.resize(size__); v.resize(size__);

		for (int i = 0; i < size__; i++) g[i] = i, v[i] = { i };

	};

	int size() { return size_; }

	int root(int x) { return g[x]; }

	int size(int x) { return v[x].size(); }

	bool same(int x, int y) { return g[x] == g[y]; }

	void unite(int x, int y) {

		x = g[x], y = g[y];

		if (x == y) return;

		if (v[x].size() < v[y].size()) swap(x, y);

		v[x].insert(v[x].end(), v[y].begin(), v[y].end());

		for(auto &e : v[y]) g[e] = x;

		v[y].clear();

	}

	bool operator==(const UnionFind& u) { return g == u.g; }

	bool operator!=(const UnionFind& u) { return g != u.g; }

	int operator[](int x) { return g[x]; }

};

int n, q, c, x, y;

int main() {

	cin >> n >> q;

	UnionFind u(n);

	for(int i = 0; i < q; i++) {

		cin >> c >> x >> y;

		if(c) cout << (u.same(x, y) ? 1 : 0) << endl;

		else u.unite(x, y);

	}

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[y].size() > f[x].size()) swap(x, y);

			for(int j = f[y].size() - 1; j >= 0; j--) {

				group[f[y][j]] = group[x];

				f[x].push_back(f[y][j]);

				f[y].pop_back();

			}

		}

		else printf("%d\n", (group[x] == group[y] ? 1 : 0));

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2256759879641617x):
#include <vector>

#include <iostream>

using namespace std;

class UnionFind {

private:

	int size_; vector<int> g; vector<vector<int> > v;

public:

	UnionFind() : size_(0), g(vector<int>()), v(vector<vector<int> >()) {};

	UnionFind(int size__) : size_(size__) {

		g.resize(size__); v.resize(size__);

		for (int i = 0; i < size__; i++) g[i] = i, v[i] = { i };

	};

	int size() { return size_; }

	int root(int x) { return g[x]; }

	int size(int x) { return v[x].size(); }

	bool same(int x, int y) { return g[x] == g[y]; }

	void unite(int x, int y) {

		x = g[x], y = g[y];

		if (x == y) return;

		if (v[x].size() < v[y].size()) swap(x, y);

		v[x].insert(v[x].end(), v[y].begin(), v[y].end());

		for(auto &e : v[y]) g[e] = x;

		v[y].clear();

	}

	bool operator==(const UnionFind& u) { return g == u.g; }

	bool operator!=(const UnionFind& u) { return g != u.g; }

	int operator[](int x) { return g[x]; }

};

int n, q, c, x, y;

int main() {

	cin >> n >> q;

	UnionFind u(n);

	for(int i = 0; i < q; i++) {

		cin >> c >> x >> y;

		if(c) cout << (u.same(x, y) ? 1 : 0) << endl;

		else u.unite(x, y);

	}

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[x].size() > f[y].size()) {

				for(int j = f[y].size() - 1; j >= 0; j--) {

					group[f[y][j]] = group[x];

					f[x].push_back(f[y][j]);

					f[y].pop_back();

				}

			}

			else {

				for(int j = f[x].size() - 1; j >= 0; j--) {

					group[f[x][j]] = group[y];

					f[y].push_back(f[x][j]);

					f[x].pop_back();

				}

			}

		}

		else {

			printf("%d\n", (group[x] == group[y] ? 1 : 0));

		}

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.231440875414819x):
#include <vector>

#include <iostream>

using namespace std;

class UnionFind {

private:

	int size_; vector<int> g; vector<vector<int> > v;

public:

	UnionFind() : size_(0), g(vector<int>()), v(vector<vector<int> >()) {};

	UnionFind(int size__) : size_(size__) {

		g.resize(size__); v.resize(size__);

		for (int i = 0; i < size__; i++) g[i] = i, v[i] = { i };

	};

	int size() { return size_; }

	int root(int x) { return g[x]; }

	int size(int x) { return v[x].size(); }

	bool same(int x, int y) { return g[x] == g[y]; }

	void unite(int x, int y) {

		x = g[x], y = g[y];

		if (x == y) return;

		if (v[x].size() < v[y].size()) swap(x, y);

		v[x].insert(v[x].end(), v[y].begin(), v[y].end());

		for(auto &e : v[y]) g[e] = x;

		v[y].clear();

	}

	bool operator==(const UnionFind& u) { return g == u.g; }

	bool operator!=(const UnionFind& u) { return g != u.g; }

	int operator[](int x) { return g[x]; }

};

int n, q, c, x, y;

int main() {

	scanf("%d%d", &n, &q);

	UnionFind u(n);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &c, &x, &y);

		if(c) cout << (u.same(x, y) ? 1 : 0) << endl;

		else u.unite(x, y);

	}

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[y].size() > f[x].size()) swap(x, y);

			for(int j = f[y].size() - 1; j >= 0; j--) {

				group[f[y][j]] = group[x];

				f[x].push_back(f[y][j]);

				f[y].pop_back();

			}

		}

		else printf("%d\n", (group[x] == group[y] ? 1 : 0));

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.231573710457298x):
#include <vector>

#include <iostream>

using namespace std;

class UnionFind {

private:

	int size_; vector<int> g; vector<vector<int> > v;

public:

	UnionFind() : size_(0), g(vector<int>()), v(vector<vector<int> >()) {};

	UnionFind(int size__) : size_(size__) {

		g.resize(size__); v.resize(size__);

		for (int i = 0; i < size__; i++) g[i] = i, v[i] = { i };

	};

	int size() { return size_; }

	int root(int x) { return g[x]; }

	int size(int x) { return v[x].size(); }

	bool same(int x, int y) { return g[x] == g[y]; }

	void unite(int x, int y) {

		x = g[x], y = g[y];

		if (x == y) return;

		if (v[x].size() < v[y].size()) swap(x, y);

		v[x].insert(v[x].end(), v[y].begin(), v[y].end());

		for(auto &e : v[y]) g[e] = x;

		v[y].clear();

	}

	bool operator==(const UnionFind& u) { return g == u.g; }

	bool operator!=(const UnionFind& u) { return g != u.g; }

	int operator[](int x) { return g[x]; }

};

int n, q, c, x, y;

int main() {

	scanf("%d%d", &n, &q);

	UnionFind u(n);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &c, &x, &y);

		if(c) cout << (u.same(x, y) ? 1 : 0) << endl;

		else u.unite(x, y);

	}

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[x].size() > f[y].size()) {

				for(int j = f[y].size() - 1; j >= 0; j--) {

					group[f[y][j]] = group[x];

					f[x].push_back(f[y][j]);

					f[y].pop_back();

				}

			}

			else {

				for(int j = f[x].size() - 1; j >= 0; j--) {

					group[f[x][j]] = group[y];

					f[y].push_back(f[x][j]);

					f[x].pop_back();

				}

			}

		}

		else {

			printf("%d\n", (group[x] == group[y] ? 1 : 0));

		}

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2442391496875422x):
#include <vector>

#include <iostream>

using namespace std;

class UnionFind {

private:

	int size_; vector<int> g; vector<vector<int> > v;

public:

	UnionFind() : size_(0), g(vector<int>()), v(vector<vector<int> >()) {};

	UnionFind(int size__) : size_(size__) {

		g.resize(size__); v.resize(size__);

		for (int i = 0; i < size__; i++) g[i] = i, v[i] = { i };

	};

	int size() { return size_; }

	int root(int x) { return g[x]; }

	int size(int x) { return v[x].size(); }

	bool same(int x, int y) { return g[x] == g[y]; }

	void unite(int x, int y) {

		x = g[x], y = g[y];

		if (x == y) return;

		if (v[x].size() < v[y].size()) swap(x, y);

		v[x].insert(v[x].end(), v[y].begin(), v[y].end());

		for(auto &e : v[y]) g[e] = x;

		v[y].clear();

	}

	bool operator==(const UnionFind& u) { return g == u.g; }

	bool operator!=(const UnionFind& u) { return g != u.g; }

	int operator[](int x) { return g[x]; }

};

int n, q, c, x, y;

int main() {

	scanf("%d%d", &n, &q);

	UnionFind u(n);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &c, &x, &y);

		if(c) printf("%d\n", u.same(x, y) ? 1 : 0);

		else u.unite(x, y);

	}

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[y].size() > f[x].size()) swap(x, y);

			for(int j = f[y].size() - 1; j >= 0; j--) {

				group[f[y][j]] = group[x];

				f[x].push_back(f[y][j]);

				f[y].pop_back();

			}

		}

		else printf("%d\n", (group[x] == group[y] ? 1 : 0));

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.244373365274829x):
#include <vector>

#include <iostream>

using namespace std;

class UnionFind {

private:

	int size_; vector<int> g; vector<vector<int> > v;

public:

	UnionFind() : size_(0), g(vector<int>()), v(vector<vector<int> >()) {};

	UnionFind(int size__) : size_(size__) {

		g.resize(size__); v.resize(size__);

		for (int i = 0; i < size__; i++) g[i] = i, v[i] = { i };

	};

	int size() { return size_; }

	int root(int x) { return g[x]; }

	int size(int x) { return v[x].size(); }

	bool same(int x, int y) { return g[x] == g[y]; }

	void unite(int x, int y) {

		x = g[x], y = g[y];

		if (x == y) return;

		if (v[x].size() < v[y].size()) swap(x, y);

		v[x].insert(v[x].end(), v[y].begin(), v[y].end());

		for(auto &e : v[y]) g[e] = x;

		v[y].clear();

	}

	bool operator==(const UnionFind& u) { return g == u.g; }

	bool operator!=(const UnionFind& u) { return g != u.g; }

	int operator[](int x) { return g[x]; }

};

int n, q, c, x, y;

int main() {

	scanf("%d%d", &n, &q);

	UnionFind u(n);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &c, &x, &y);

		if(c) printf("%d\n", u.same(x, y) ? 1 : 0);

		else u.unite(x, y);

	}

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[x].size() > f[y].size()) {

				for(int j = f[y].size() - 1; j >= 0; j--) {

					group[f[y][j]] = group[x];

					f[x].push_back(f[y][j]);

					f[y].pop_back();

				}

			}

			else {

				for(int j = f[x].size() - 1; j >= 0; j--) {

					group[f[x][j]] = group[y];

					f[y].push_back(f[x][j]);

					f[x].pop_back();

				}

			}

		}

		else {

			printf("%d\n", (group[x] == group[y] ? 1 : 0));

		}

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3403672169347878x):
#include <vector>

#include <numeric>



class UnionFind {

private:

	int size_;

	std::vector<int> parent;

	std::vector<int> rank;

public:

	UnionFind() : size_(0), parent(std::vector<int>()), rank(std::vector<int>()) {};

	UnionFind(int size__) : size_(size__) {

		parent = std::vector<int>(size_);

		rank = std::vector<int>(size_, 0);

		std::iota(parent.begin(), parent.end(), 0);

	}

	int size() { return size_; }

	int root(int x) {

		if (parent[x] == x) return x;

		std::vector<int> path;

		while (x != parent[x]) {

			path.push_back(x);

			x = parent[x];

		}

		for (int i : path) parent[i] = x;

		return x;

	}

	bool same(int x, int y) {

		return root(x) == root(y);

	}

	void unite(int x, int y) {

		x = root(x);

		y = root(y);

		if (x == y) return;

		if (rank[x] < rank[y]) parent[x] = y;

		else if (rank[x] > rank[y]) parent[y] = x;

		else parent[y] = x, rank[x]++;

	}

};



#include <cstdio>

int n, q, tp, x, y;

int main() {

	scanf("%d%d", &n, &q);

	UnionFind uf(n);

	while(q--) {

		scanf("%d%d%d", &tp, &x, &y);

		if(tp == 0) uf.unite(x, y);

		else printf("%d\n", uf.same(x, y));

	}

	return 0;

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[y].size() > f[x].size()) swap(x, y);

			for(int j = f[y].size() - 1; j >= 0; j--) {

				group[f[y][j]] = group[x];

				f[x].push_back(f[y][j]);

				f[y].pop_back();

			}

		}

		else printf("%d\n", (group[x] == group[y] ? 1 : 0));

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.340511801818848x):
#include <vector>

#include <numeric>



class UnionFind {

private:

	int size_;

	std::vector<int> parent;

	std::vector<int> rank;

public:

	UnionFind() : size_(0), parent(std::vector<int>()), rank(std::vector<int>()) {};

	UnionFind(int size__) : size_(size__) {

		parent = std::vector<int>(size_);

		rank = std::vector<int>(size_, 0);

		std::iota(parent.begin(), parent.end(), 0);

	}

	int size() { return size_; }

	int root(int x) {

		if (parent[x] == x) return x;

		std::vector<int> path;

		while (x != parent[x]) {

			path.push_back(x);

			x = parent[x];

		}

		for (int i : path) parent[i] = x;

		return x;

	}

	bool same(int x, int y) {

		return root(x) == root(y);

	}

	void unite(int x, int y) {

		x = root(x);

		y = root(y);

		if (x == y) return;

		if (rank[x] < rank[y]) parent[x] = y;

		else if (rank[x] > rank[y]) parent[y] = x;

		else parent[y] = x, rank[x]++;

	}

};



#include <cstdio>

int n, q, tp, x, y;

int main() {

	scanf("%d%d", &n, &q);

	UnionFind uf(n);

	while(q--) {

		scanf("%d%d%d", &tp, &x, &y);

		if(tp == 0) uf.unite(x, y);

		else printf("%d\n", uf.same(x, y));

	}

	return 0;

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[x].size() > f[y].size()) {

				for(int j = f[y].size() - 1; j >= 0; j--) {

					group[f[y][j]] = group[x];

					f[x].push_back(f[y][j]);

					f[y].pop_back();

				}

			}

			else {

				for(int j = f[x].size() - 1; j >= 0; j--) {

					group[f[x][j]] = group[y];

					f[y].push_back(f[x][j]);

					f[x].pop_back();

				}

			}

		}

		else {

			printf("%d\n", (group[x] == group[y] ? 1 : 0));

		}

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3423970506710596x):
#include <vector>

#include <numeric>

#include <algorithm>



class unionfind {

private:

	int size_;

	std::vector<int> parent;

	std::vector<int> rank;

public:

	unionfind() : size_(0), parent(std::vector<int>()), rank(std::vector<int>()) {};

	unionfind(int size__) : size_(size__), parent(std::vector<int>(size_)), rank(std::vector<int>(size_, 0)) {

		std::iota(parent.begin(), parent.end(), 0);

	}

	int size() { return size_; }

	int root(int x) {

		if (parent[x] == x) return x;

		return parent[x] = root(parent[x]);

	}

	bool same(int x, int y) {

		return root(x) == root(y);

	}

	void unite(int x, int y) {

		x = root(x); y = root(y);

		if (x == y) return;

		if (rank[x] < rank[y]) parent[x] = y;

		else if (rank[x] > rank[y]) parent[y] = x;

		else parent[y] = x, rank[x]++;

	}

};



#include <cstdio>

int N, Q, tp, x, y;

int main() {

	scanf("%d%d", &N, &Q);

	unionfind uf(N);

	while (Q--) {

		scanf("%d%d%d", &tp, &x, &y);

		if (tp == 0) uf.unite(x, y);

		else printf("%d\n", uf.same(x, y));

	}

	return 0;

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[y].size() > f[x].size()) swap(x, y);

			for(int j = f[y].size() - 1; j >= 0; j--) {

				group[f[y][j]] = group[x];

				f[x].push_back(f[y][j]);

				f[y].pop_back();

			}

		}

		else printf("%d\n", (group[x] == group[y] ? 1 : 0));

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3425418545124859x):
#include <vector>

#include <numeric>

#include <algorithm>



class unionfind {

private:

	int size_;

	std::vector<int> parent;

	std::vector<int> rank;

public:

	unionfind() : size_(0), parent(std::vector<int>()), rank(std::vector<int>()) {};

	unionfind(int size__) : size_(size__), parent(std::vector<int>(size_)), rank(std::vector<int>(size_, 0)) {

		std::iota(parent.begin(), parent.end(), 0);

	}

	int size() { return size_; }

	int root(int x) {

		if (parent[x] == x) return x;

		return parent[x] = root(parent[x]);

	}

	bool same(int x, int y) {

		return root(x) == root(y);

	}

	void unite(int x, int y) {

		x = root(x); y = root(y);

		if (x == y) return;

		if (rank[x] < rank[y]) parent[x] = y;

		else if (rank[x] > rank[y]) parent[y] = x;

		else parent[y] = x, rank[x]++;

	}

};



#include <cstdio>

int N, Q, tp, x, y;

int main() {

	scanf("%d%d", &N, &Q);

	unionfind uf(N);

	while (Q--) {

		scanf("%d%d%d", &tp, &x, &y);

		if (tp == 0) uf.unite(x, y);

		else printf("%d\n", uf.same(x, y));

	}

	return 0;

}
// Slower C++ solution:
#include <vector>

#include <iostream>

using namespace std;

int n, q, com, x, y; int group[10000]; vector<int> f[10000];

int main() {

	scanf("%d%d", &n, &q);

	for(int i = 0; i < n; i++) group[i] = i, f[i].push_back(i);

	for(int i = 0; i < q; i++) {

		scanf("%d%d%d", &com, &x, &y);

		if(com == 0) {

			if(group[x] == group[y]) continue;

			x = group[x], y = group[y];

			if(f[x].size() > f[y].size()) {

				for(int j = f[y].size() - 1; j >= 0; j--) {

					group[f[y][j]] = group[x];

					f[x].push_back(f[y][j]);

					f[y].pop_back();

				}

			}

			else {

				for(int j = f[x].size() - 1; j >= 0; j--) {

					group[f[x][j]] = group[y];

					f[y].push_back(f[x][j]);

					f[x].pop_back();

				}

			}

		}

		else {

			printf("%d\n", (group[x] == group[y] ? 1 : 0));

		}

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2543208971365962x):
#include <bits/stdc++.h>

using namespace std;

int par[10009];

int root(int x) {

    if(par[x]== x) return x;

    return par[x] = root(par[x]);

}

void unite(int x, int y) {

    x = root(x); y = root(y);

    if(x == y) return;

    par[x] = y;

}

bool same(int x, int y) {

    int rx = root(x);

    int ry = root(y);

    return rx == ry;

}

int n, q, tp, x, y;

int main() {

    scanf("%d%d", &n, &q);

    for(int i = 0; i < n; i++) par[i] = i;

    while(q--) {

        scanf("%d%d%d", &tp, &x, &y);

        if(tp == 0) unite(x, y);

        else {

            bool ret = same(x, y);

            puts(ret ? "1" : "0");

        }

    }

    return 0;

}