private int[] id; // id[i] = parent of i

private int[] sz; // sz[i] = number of objects in subtree rooted at i

private int count; // number of components

// Create an empty union find data structure with N isolated sets.

public WeightedQuickUnionUF(int N) {

count = N;

id = new int[N];

sz = new int[N];

for (int i = 0; i < N; i++) {

id[i] = i;

sz[i] = 1;

}

}

// Return the number of disjoint sets.

public int count() {

return count;

}

// Return component identifier for component containing p

public int find(int p) {

while (p != id[p])

p = id[p];

return p;

}

// Are objects p and q in the same set?

public boolean connected(int p, int q) {

return find(p) == find(q);

}

// Replace sets containing p and q with their union.

public void union(int p, int q) {

int i = find(p);

int j = find(q);

if (i == j) return;

// make smaller root point to larger one

if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }

else { id[j] = i; sz[i] += sz[j]; }

count--;

}

public static void main(String[] args) {

int N = StdIn.readInt();

WeightedQuickUnionUF uf = new WeightedQuickUnionUF(N);

// read in a sequence of pairs of integers (each in the range 0 to N-1),

// calling find() for each pair: If the members of the pair are not already

// call union() and print the pair.

while (!StdIn.isEmpty()) {

int p = StdIn.readInt();

int q = StdIn.readInt();

if (uf.connected(p, q)) continue;

uf.union(p, q);

StdOut.println(p + " " + q);

}

StdOut.println(uf.count() + " components");

}