class DSU {
private:
  int n;
  int *p;
  int *sz;
  vector<vector<int> *> elem;

public:
  DSU(int n) : n(n) {
    p = new int[n];
    sz = new int[n];
    elem.resize(n);
    for (int i = 0; i < n; i++)
      elem[i] = new vector<int>(1, i);
    fill_n(sz, n, 1);
    for (int i = 0; i < n; i++)
      p[i] = i;
  }

  ~DSU() {
    delete[] p;
    delete[] sz;
  }

  int get(int v) {
    if (v == p[v])
      return v;
    return p[v] = get(p[v]);
  }

  inline void merge(int a, int b) {
    a = get(a);
    b = get(b);
    if (a == b)
      return;
    if (sz[a] > sz[b])
      swap(a, b);
    sz[b] += sz[a];
    p[a] = b;
    for (int i = 0; i < sz[a]; i++)
      elem[b]->pb((*elem[a])[i]);
    delete elem[a];
  }

  inline int size(int a) {
    return sz[get(a)];
  }

  inline vector<int> *getElem(int a) {
    return elem[get(a)];
  }

  inline bool equal(int a, int b) {
    return get(a) == get(b);
  }
};