public static void main(String[] args) {
    long start = System.currentTimeMillis();
    int n = StdIn.readInt();
    UF2 uf = new UF2(n);
    while(!StdIn.isEmpty()) {
      int p =  StdIn.readInt();
      int q =  StdIn.readInt();
      if (!uf.connected(p, q)) {
        uf.union(p, q);
        StdOut.println(p + ":" + q);
      }
    }
    long end = System.currentTimeMillis();
    StdOut.println("cost time:" + (end -  start));

    for (int i = 0; i < uf.id.length; i ++) {
      StdOut.println(uf.id[i]);
    }
  }