class QuickUF {
private:
  vector<int> ids;
  vector<size_t> sizes;
  int count; //# of connected components.

public:
  QuickUF(int n) {
    ids.resize(n);
    sizes.resize(n);
    count = 0;
    for (int i = 0; i < n; i++) {
      ids[i] = i;
      sizes[i] = 1;
      count++;
    }
  }

  int find(int i) { // path compression
    return root(i);
  }

  int getCount() {
      return count;
  }
  int root(int a) {
    while (a != ids[a]) {
      ids[a] = ids[ids[a]]; // path compression
      a = ids[a];
    }

    return a;
  }
  void union_nodes(int a, int b) {
    int ra = root(a);
    int rb = root(b);
    if(ra != rb) {
        count--;
        if (sizes[ra] >= sizes[rb]) {
            // put in b tree
            ids[ra] = rb;
            sizes[rb] += sizes[ra];
        } else {
            ids[rb] = ra;
            sizes[ra] += sizes[rb];
        }
    }
  }
  bool connected(int a, int b) {
    int ra = root(a);
    int rb = root(b);
    return ra == rb;
  }
};