#include <iostream>

#define mid (l + r >> 1)

using namespace std;

const int N = 3e5 + 1;

struct E {
  int l, r, f, d;
} t[N * 30];

int n, m, rt[N * 30], tot, op, x, y;

void Build(int &i, int l, int r) {
  i = ++tot;
  if (l == r) {
    t[i].f = l;
    return;
  }
  Build(t[i].l, l, mid), Build(t[i].r, mid + 1, r);
}

void Merge(int _i, int &i, int l, int r, int x, int fa) {
  i = ++tot;
  t[i].l = t[_i].l, t[i].r = t[_i].r;
  if (l == r) {
    t[i].f = fa;
    t[i].d = t[_i].d;
    return;
  }
  if (x <= mid) {
    Merge(t[_i].l, t[i].l, l, mid, x, fa);
  } else {
    Merge(t[_i].r, t[i].r, mid + 1, r, x, fa);
  }
}

void Update(int i, int l, int r, int x) {
  if (l == r) {
    t[i].d++;
    return;
  }
  if (x <= mid) {
    Update(t[i].l, l, mid, x);
  } else {
    Update(t[i].r, mid + 1, r, x);
  }
}

int Query(int i, int l, int r, int x) {
  if (l == r) {
    return i;
  }
  if (x <= mid) {
    return Query(t[i].l, l, mid, x);
  } else {
    return Query(t[i].r, mid + 1, r, x);
  }
}

int Find(int i, int x) {
  int now = Query(i, 1, n, x);
  if (t[now].f == x) {
    return now;
  }
  return Find(i, t[now].f);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  Build(rt[0], 1, n);
  for (int i = 1; i <= m; ++i) {
    cin >> op >> x;
    if (op == 1) {
      cin >> y;
      rt[i] = rt[i - 1];
      int fx = Find(rt[i], x), fy = Find(rt[i], y);
      if (t[fx].f != t[fy].f) {
        if (t[fx].d > t[fy].d) {
          swap(fx, fy);
        }
        Merge(rt[i - 1], rt[i], 1, n, t[fx].f, t[fy].f);
      }
      if (t[fx].d == t[fy].d) {
        Update(rt[i], 1, n, t[fy].f);
      }
    } else if (op == 2) {
      rt[i] = rt[x];
    } else {
      cin >> y;
      rt[i] = rt[i - 1];
      int fx = Find(rt[i], x), fy = Find(rt[i], y);
      cout << (t[fx].f == t[fy].f) << '\n';
    }
  }
  return 0;
}