// search.java - mjd@cs.auckland.ac.nz

import java.io.*;
import graphADT.*;
import graphAlgs.*;

public class search {

	public static void main(String argv[]){
		try {
//			BufferedReader input = new BufferedReader(new FileReader(argv[0]));
			BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

			while(true){
     
			   Graph G = new GraphAdjLists(input);
			   int n=G.order(); if ( n == 0 ) break;
		
			   System.out.print(G);
		
			   int preOrder[] = new int[n];
			   int postOrder[] = new int[n];
		
			   GraphAlgs.BFS(G,0,preOrder);
		
			   System.out.print("BFS (levelorder): ");
			   for (int i=0; i<n; i++) System.out.print(preOrder[i] + " ");
			   System.out.print("\n");
		
			   GraphAlgs.DFS(G,0,preOrder,postOrder);
		
			   System.out.print("DFS (preorder):   ");
			   for (int i=0; i<n; i++) System.out.print(preOrder[i] + " ");
			   System.out.print("\n");
		
			   System.out.print("DFS (postorder):  ");
			   for (int i=0; i<n; i++) System.out.print(postOrder[i] + " ");
			   System.out.print("\n");
			}

		} catch ( Exception e ) { System.err.println("Exception: "+e); }

	} // main

} // class search