/*quick weighted union with path compression*/
#include <stdio.h>
#include <iostream>
#define N 10
int get_root(int id[], int element){
while(id[element] != element){
element = id[element];
}
return element;
}
int main(){
int id[N];
int size[N];
for (int i = 0; i < N; i++){
id[i] = i;
size[i] = 1;
}
int p;
int q;
while(std::cin >> p >> q){
int pRoot = get_root(id, p);
int qRoot = get_root(id, q);
if (qRoot == pRoot) {
continue;
}
if (size[pRoot] > size[qRoot]){
id[qRoot] = id[q] = pRoot;
size[pRoot] += size[qRoot];
}
else {
id[pRoot]= id[p] = qRoot;
size[qRoot] += size[pRoot];
}
printf("%d %d\n", p, q);
}
for(int i =0; i < N; i++){
printf("%d \t", id[i]);
}
printf("\n");
for(int i =0; i < N; i++){
printf("%d \t", size[i]);
}
printf("\n");
return 0;
}
//---------------------------------
/*quick weighted union with max path length */
#include <stdio.h>
#include <iostream>
#define N 10
int get_root(int id[], int element){
while(id[element] != element){
element = id[element];
}
return element;
}
int main(){
int id[N];
int size[N];
for (int i = 0; i < N; i++){
id[i] = i;
size[i] = 1;
}
int p;
int q;
while(std::cin >> p >> q){
int pRoot = get_root(id, p);
int qRoot = get_root(id, q);
if (qRoot == pRoot) {
continue;
}
if (size[pRoot] >= size[qRoot]){
id[qRoot] = pRoot;
if (size[pRoot] == size[qRoot]){
size[pRoot] += 1;
}
}
else {
id[pRoot] = qRoot;
}
printf("%d %d\n", p, q);
}
for(int i =0; i < N; i++){
printf("%d \t", id[i]);
}
printf("\n");
for(int i =0; i < N; i++){
printf("%d \t", size[i]);
}
printf("\n");
return 0;
}
