/* Resolução do problema da conexidade com o quick-find com a heurística dos tamanhos. */

#include <stdio.h>
#define N 100000

main() {
  int i, j, p, q, t, id[N], tam[N];

  /* Inicialmente cada elemento forma um conjunto unitário. */
  for (i=0; i < N; i++) { 
    id[i] = i;
    tam[i] = 1; 
  }

  while (scanf("%d %d", &p, &q) == 2) { 
     /* determina o representante de i */
    for (i=p; id[i]!=i; i=id[i]); 
    /* determina o representante de j */
    for (j=q; id[j]!=j; j=id[j]);
    /* se os elementos do par estão em conjuntos diferentes, 
       imprime o par e faz a união dos dois conjuntos. */
    if (i != j) { 
      /* faz a união dos conjuntos contendo p e q com a heurística dos tamanhos */ 
      if (tam[i] > tam[j]) {
	id[j] = i;
	tam[i] += tam[j];
      }
      else {
	id[i] = j;
	tam[j] += tam[i];
      }
      printf("      %d %d\n", p, q);
    }
  }
}