DSU

class DSU {
  int[] parent;
  int[] weight;

  DSU(int n) {
    this.parent = new int[n];
    for(int idx = 0; idx < n; idx++) {
      parent[idx] = idx;
    }

    this.weight = new int[n];
    for(int idx = 0; idx < n; idx++) {
      weight[idx] = 1;
    }
  }

  // path compression
  int find(int idx) {
    if(parent[idx] == idx) return idx;
    return parent[idx] = find(parent[idx]);
  }

  // weight compression
  void union(int a, int b) {
    int pa = find(a);
    int pb = find(b);

    if(pa == pb) return;
    
    if(weight[pa] > weight[pb]) {
      parent[pb] = pa;
      weight[pa] += weight[pb];
    }
    else {
      parent[pa] = pb;
      weight[pb] += weight[pa];
    }
  }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}