/* Revised weighted quick union from P17 as your template for connect.c */
#include <stdio.h>
#define N       10000
main() {
        int i, j, p, q, id[N], sz[N];
        /* initialize the sets and number of set elements */
        for(i = 0; i < N; i++) {
                id[i] = i;
                sz[i] = 1;
        }
        /* as long as we are getting good numbers, then process them */
        while(scanf("%d %d", &p, &q) == 2) {
                if(p < 0 || q < 0 || p >= N || q >= N) {
                        fprintf(stderr, "data out of range\n");
                        break;
                }
                /* find the set id's for p and q */
                for(i = p; i != id[i]; i = id[i])
                        ;
                for(j = q; j != id[j]; j = id[j])
                        ;
                /* if the sets are the same then just get new data */
                if(i == j)
                        continue;
                /* link the smaller tree to the larger one */
                if(sz[i] < sz[j]) {
                        id[i] = j;
                        sz[j] += sz[i];
                } else {
                        id[j] = i;
                        sz[i] += sz[j];
                }
                /* output to indicate the new connection */
                printf("  %d %d\n", p, q);
        }
}