import java.util.*;

/**
 *
 * @author Colin Lee
 */
public class Trees {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        HashMap graph = new HashMap();

        ArrayList v0 = new ArrayList();

        ArrayList v1 = new ArrayList();
        ArrayList v2 = new ArrayList();
        ArrayList v3 = new ArrayList();
        ArrayList v4 = new ArrayList();
        v0.add(1);
        v0.add(3);
        v1.add(0);
        v1.add(4);
        v1.add(2);
        v2.add(1);
        v4.add(1);
        v3.add(0);
        graph.put(0,v0);
        graph.put(1,v1);
        graph.put(2,v2);
        graph.put(3,v3);
        graph.put(4,v4);
        HashMap visited = new HashMap();
        Stack T = new Stack();
        int count;

        T.push(graph.get(0)); //l(v)  = 0 for all v
        count = 1; //count = 1
        for(int i = 0; i < graph.size(); i++) //(Lv0) = count
            visited.put(i, 0);
        visited.put(0, count);
        while(!T.empty()) { //while T =/= null
            ArrayList v = new ArrayList();
            v = (ArrayList) T.peek(); //v as top of stack
            boolean adjacent = false;
            for(int j = 0; j<graph.size(); j++)
                if(v.contains(j)&&visited.get(j)==0){
                    count++; //count = count +1
                    visited.put(j, count); //l(w) = count
                    T.push(graph.get(j)); //put w into the stack
                    adjacent=true;
                    break;
                }
            if (!adjacent)
                T.pop();


        }
        for(int i = 0; i < visited.size(); i++)
            System.out.println(i + " " + visited.get(i));




        // TODO code application logic here
    }
}