import java.io.*;

class Liste {
    int som;
    Liste suiv;

    Liste (int s, Liste l) {
        som = s;
        suiv = l;
    }
}

class Graphe {
    int nb_som;
    Liste succs[];

    Graphe (int n){
        nb_som = n;
        succs = new Liste[n];
        for (int i=0; i<n; i++) 
            succs[i] = null;
    }
}

public class Corrige10 {

    static String Lire () {
        BufferedReader in = 
            new BufferedReader(new InputStreamReader(System.in));
        String s;
        try { s = in.readLine(); }
        catch (IOException e) { s = "echec"; }
        return(s);
    }

    static Graphe saisit () {
        System.out.println("nombre de sommets :"); 
        Graphe a = new Graphe(Integer.parseInt(Lire()));
        for (int i=0; i<a.nb_som; i++) {
            System.out.println("succs de " + i + ": "); 
            int tmp = Integer.parseInt(Lire());
            while (tmp != -1) {
                Liste l = new Liste(tmp, a.succs[i]);
                a.succs[i] = l;
                System.out.println("succs de " + i + ": "); 
                tmp = Integer.parseInt(Lire());
            }
        }
        return(a);
    }

    static void affiche (Graphe a) {
        for (int i=0; i<a.nb_som; i++) {
            System.out.print("succs de " + i + ": "); 
            Liste l = a.succs[i];
            while (l != null) {
                System.out.print(l.som); 
                l = l.suiv;
                if (l != null) 
                    System.out.print(", ");
            }
            System.out.println(); 
        }
    }

    static Liste copie (Liste l) {
        if (l == null) 
            return(null);
        else
            return(new Liste(l.som, copie(l.suiv)));
    }

    static Liste concat (Liste l, Liste m) { // l et m non copiees
        if (l == null) 
            return(m);
        else {
            l.suiv = concat(l.suiv, m);
            return(l);
        }
    }

    static Graphe calculArbo(Graphe A, int rac) {
        Graphe B = new Graphe(A.nb_som);
        boolean[] visites = new boolean[A.nb_som];
        Liste Y = new Liste(rac, null);
        visites[rac] = true;

        while (Y != null) {
            int i = Y.som;
            Y = Y.suiv;

            Liste succsNV = null; // les successeurs non deja visites
            Liste tmp = A.succs[i];
            while (tmp != null) {
	        if (!visites[tmp.som]) {
                    succsNV = new Liste(tmp.som, succsNV);
                    visites[tmp.som] = true;
                }
                tmp = tmp.suiv;
            }
            Y = concat(Y, succsNV);
            B.succs[i] = copie(succsNV);
        }
        return(B);
    }

    public static void main (String[] args) {
        Graphe g = saisit();
        affiche(g); 
        System.out.println("racine ? ");
        affiche(calculArbo(g, Integer.parseInt(Lire())));
    }
}