package prog3;

import java.io.FileNotFoundException;
import java.util.Scanner;

class Node {
    public int data;
    public Node next;

    // class can't be compiled without constructor, empty constructor
    Node() {
    }

    // Function to set value
    void set(int x) {
        data = x;
    }
}

class List {
    public Node first, last;
    public List next;

    List() {
    }

    void add(int data) {
        if (first != null) {
            Node search;
            search = first;
            while (search.next != null) {
                search = search.next;
            }
            last = new Node();
            last.set(data);
            last.next = null;
            search.next = last;
        } else {
            first = new Node();
            first.set(data);
            first.next = null;
        }
    }

    void afisare() {
        Node parcurgere = first;
        while (parcurgere.next != null) {
            System.out.print(parcurgere.data + " ");
            parcurgere = parcurgere.next;
        }
        System.out.print(parcurgere.data + " ");
    }
}

class Que {
    List coada;

    Que() {
        coada = new List();
        coada.first = new Node();
        coada.first = null;
        coada.last = new Node();
        coada.last = null;
    }

    void add(int x) {
        Node dummy;
        if (coada.first == null) {
            coada.first = new Node();
            coada.first.set(x);
            coada.first.next = null;
            coada.last = coada.first;
        } else {
            dummy = new Node();
            dummy.set(x);
            dummy.next = null;
            coada.last.next = dummy;
            coada.last = dummy;
        }
    }

    int remove() {
        Node dummy;
        dummy = coada.first;
        while (dummy.next != coada.last) {
            dummy = dummy.next;
        }
        dummy.next = null;
        int val = coada.last.data;
        System.out.print("!");
        coada.last = dummy;
        return val;
    }

    boolean isEmpty() {
        if (coada.first == null)
            return true;
        else
            return false;
    }
}

class Graf {
    List lfirst, llast;
    int varf;
    int vec[];
    Que queue;

    Graf(int n) {
        varf = n - 1;
        List dummy;
        lfirst = null;
        vec = new int[n - 1];
        int i = 0;
        while (i < n) {
            if (lfirst == null) {
                lfirst = new List();
                lfirst.next = null;
                lfirst.add(i);
                llast = lfirst;
                i++;
            } else {
                dummy = new List();
                dummy.add(i);
                llast.next = dummy;
                llast = dummy;
                llast.next = null;
                i++;
            }
        }
        for (i = 0; i < n - 1; i++) {
            vec[i] = 0;
        }
    }

    int conected(int a, int b) {
        List dummy;
        Node finder;
        dummy = lfirst;
        while (dummy != null) {
            if (dummy.first.data == a) {
                finder = dummy.first;
                while (finder != null) {
                    if (finder.data == b) {
                        return 1;
                    }
                    finder = finder.next;
                }
            }
            dummy = dummy.next;
        }
        return 0;
    }

    void parcurgere() {
        queue = new Que();
        int tag = 0;
        vec[tag] = 1;
        queue.add(0);
        List dummy;
        Node caller;
        while (!queue.isEmpty()) {
            tag = queue.remove();
            System.out.print(">" + tag + " ");
            dummy = this.lfirst;
            while (tag != dummy.first.data) {
                dummy = dummy.next;
                if (dummy.next == null)
                    return;
            }
            caller = dummy.first;
            while (caller != null) {
                if (vec[caller.data] == 0) {
                    queue.add(caller.data);
                    vec[caller.data] = 1;
                }
                caller = caller.next;
            }
        }
    }

    void add(int a, int b) {
        List carry;
        carry = lfirst;
        while (carry.first.data != a) {
            carry = carry.next;
        }
        carry.add(b);
    }

    void afisare() {
        List carry;
        carry = lfirst;
        while (carry.next != null) {
            System.out.println();
            carry.afisare();
            carry = carry.next;
        }
    }
}

public class Lab3 {

    public static void main(String e[]) {
        Graf listaGraf;
        Scanner reader = null;
        // try to read file if file isn't created throws exception
        try {
            reader = new Scanner(new java.io.File("input.txt"));
            int n = reader.nextInt();
            listaGraf = new Graf(n);
            while (reader.hasNextInt()) {
                int a = reader.nextInt();
                int b = reader.nextInt();
                listaGraf.add(a, b);
                listaGraf.add(b, a);
            }
            listaGraf.afisare();
            System.out.println();
            listaGraf.parcurgere();
            System.out.println();
        } catch (FileNotFoundException exception) {
            System.out.print("Nu exista fisierul");
        }
        // try over, exception or not
    }
}