import java.io.*;
import java.util.*;
public class Graaf2{
  static int[][] massiiv;
  static int s6lmedeArv;
  static int[] kaugused; //iga arv näitab kaugust (sammude arv) määratud alglinnast
  static int algSolm;
  static int[] puhver;
  static int[] tagasitee;
  static int uurimisalgus, uurimisots;
  
  static void looTyhiPuhver(){
    puhver=new int[s6lmedeArv];
    uurimisalgus=uurimisots=0;
  }
  
  static void lisaPuhvrisse(int solm){
     puhver[uurimisots]=solm;
     uurimisots++;
  }
  
  static int kysiPuhvrist(){
     return puhver[uurimisalgus++];
  }
  
  static boolean kasPuhvrisElemente(){
      return uurimisalgus<uurimisots;
  }
  
  static void leiaKaugused(int solmenr){
      kaugused=new int[s6lmedeArv];
      tagasitee=new int[s6lmedeArv];
      for(int i=0; i<s6lmedeArv; i++){
         kaugused[i]=-1; //võimatu väärtus
         tagasitee[i]=-1;
      }
      kaugused[solmenr]=0;
      int sammudearv=1;
      looTyhiPuhver();
      lisaPuhvrisse(solmenr);
      tagasitee[solmenr]=solmenr;
      while(kasPuhvrisElemente()){
        int solm=kysiPuhvrist();
        for(int i=0; i<s6lmedeArv; i++){
         if(massiiv[i][solm]==1 && kaugused[i]==-1){
            kaugused[i]=sammudearv;
            lisaPuhvrisse(i);
            tagasitee[i]=solm;
         }
        }
        sammudearv++;
      }
  }
  
  static void lisaSeos(int linn1, int linn2){
    massiiv[linn1][linn2]=1;
    massiiv[linn2][linn1]=1;          
  }

  static void trykiEkraanile(){
    for(int i=0; i<s6lmedeArv; i++){
       for(int j=0; j<s6lmedeArv; j++){
         System.out.print(massiiv[i][j]);
       }
       System.out.println();
    } 
  }


  static void loeFailist()throws IOException{
    BufferedReader sisse=new BufferedReader(
      new FileReader("s6lmed2.txt")
    );
    String rida=sisse.readLine();
    s6lmedeArv=Integer.parseInt(rida)+1;
    massiiv=new int[s6lmedeArv][s6lmedeArv];
    for(int i=0; i<s6lmedeArv; i++){
      for(int j=0; j<s6lmedeArv; j++){
        massiiv[i][j]=0;
      }
    }
    rida=sisse.readLine();
    while(rida!=null){
      StringTokenizer stk=new StringTokenizer(rida);
      int esimene=Integer.parseInt(stk.nextToken());
      int teine=Integer.parseInt(stk.nextToken());
      lisaSeos(esimene, teine);
      rida=sisse.readLine();
    }
    sisse.close();
  }

  public static void main(String argumendid[])throws IOException{
   loeFailist();
   trykiEkraanile();
   leiaKaugused(5);
   for(int i=0; i<kaugused.length; i++){
     System.out.println(kaugused[i]+ " " + tagasitee[i]);
   }
  }
}