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

import java.io.*;
import graphs.*;

public class topsort {

 public static void printSort(String label, int[] sort)
 {
   int n = sort.length;
   int actual[] = new int[n];
  
   System.out.print(label);
   for (int i=0; i<n; i++) actual[sort[i]-1] = i;
   for (int i=0; i<n; i++) System.out.print(actual[i]+" ");
   System.out.println();
 }

 public static void main(String argv[]) 
 {
   try {

   BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

   while(true)
   {
     Graph G = new Graph(input);
     int n=G.order(); if ( n == 0 ) break;

     System.out.print(G.toStringAdjLists());

     printSort("sort1: ", GraphAlgs.topSort1(G,0) );
     printSort("sort2: ", GraphAlgs.topSort2(G) );
   } 

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

 } // main

} // class search