rt，WA 15pts，AC #6 #7 #12。

保证复杂度用的是启发式合并。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, ans[N], bel[N], op[N];
vector<int> e[N], vec[N];
pair<int, int> p[N];
void dfs(int u) {
  int x = p[u].first, y = p[u].second, cnt;
  if (op[u] == 1 && x != y) {
    if (vec[x].size() > vec[y].size()) swap(x, y);
    for (auto ele : vec[x]) bel[ele] = y, vec[y].push_back(ele);
    cnt = vec[x].size(), vec[x].clear();
  }
  if (op[u] == 3) ans[u] = (bel[x] == bel[y]);
  for (auto v : e[u]) dfs(v);
  if (op[u] == 1 && x != y)
    while (cnt--) {
      int ele = vec[y].back();
      bel[ele] = x, vec[x].push_back(ele), vec[y].pop_back();
    }
}
signed main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) bel[i] = i, vec[i].push_back(i);
  for (int i = 1, lst; i <= m; ++i) {
    int u, v; cin >> op[i] >> u; lst = i - 1;
    if (op[i] == 2) lst = u;
    else cin >> v, p[i] = {u, v};
    e[lst].push_back(i);
  }
  dfs(0);
  for (int i = 1; i <= m; ++i)
    if (op[i] == 3) cout << ans[i] << '\n'; 
  return 0;
}