// This code implements the Depth First Search of a graph represented by
// its adjacency list. The file name should be taken as the first
// command line parameter.
//
// 1. Save this file as DFS.java
// 2. Compile it with javac DFS.java
// 3. Run with java DFS < dfs.dat (or your own file name) 

import java.util.*;
import java.io.*;

public class DFS
{
  // this inner class describes a graph vertex 
  private static class Vertex
  {
    String label;              // vertex label
    int color;                 // 0=white 1=gray 2=black
    int pred;                  // link to pred. in DFS forest
    int d;                     // discovery time
    int f;                     // finalizing time
    public Vertex(String label) // constructor
    {
      this.label = label;      // set up the vertex label
      pred = -1;
    }
  }
  private static Vertex[] vertices;  // array of graph vertices
  private static int[][] adjList;    // storage for adjacency list
  private static int time;           // global var needed for implementation

  public static void main(String[] args) throws IOException
  {
    readGraph(args);      // read graph encoding

    // control output of the graph encoding
    System.out.println("Graph vertex indices and labels");
    for (int i=0; i<vertices.length; i++)
      System.out.println(i + ": " + vertices[i].label);

    // control output of the adjacency list
    System.out.println("\nAdjacency list:");
    for (int i=0; i<adjList.length; i++)
    {
      System.out.print(i + ":");
      for (int j=0; j<adjList[i].length; j++)
        System.out.print(" " + adjList[i][j]);
      System.out.println();
    }

    DFS();                // compute vertex labels and predecessors
  
    // output of the vertex attributes 
    System.out.println("\nDFS forest:");
    for (int i=0; i<vertices.length; i++)
    {
      String s = (vertices[i].pred<0)? "nil" : vertices[vertices[i].pred].label;
      System.out.println(vertices[i].label + ": d=" + vertices[i].d + " f=" + 
         vertices[i].f + " pred=" + s);
    }
  }

  public static void DFS()   // main DFS method
  {
    time = 0;
    // color initialization (white) and vertex predecessors (nil) are
    // provided by the vertex object constructor
    for (int i=0; i<vertices.length; i++)
      if (vertices[i].color == 0)   // if color=white, explore the vertex
        DFS_Visit(i); 
  }

  public static void DFS_Visit(int i)
  {
    vertices[i].color = 1;                     // color v_i gray
    vertices[i].d = ++time;                    // discovery time
    
    for (int j=0; j<adjList[i].length; j++)    // check all neighbours of v_i
    {
      int ind = adjList[i][j];                 // neighbour index
      if (vertices[ind].color == 0)            // if color(v_ind)=white
      {
        vertices[ind].pred = i;                // set up v_i=pred(v_ind)
        DFS_Visit(ind);                        // explore v_ind
      }
    }
    // at this point all neighbours of v_i are explored
    vertices[i].color = 2;                     // color v_i black   
    vertices[i].f = ++time;                    // finalizing time
  }

  // this method reads graph encoding from file
  public static void readGraph(String[] args) throws IOException
  {
    Scanner inFile = new Scanner(System.in);

    HashMap<String, Integer> nodeMap = 
           new HashMap<String, Integer>();     // storage for vertex labels
    ArrayList<Vertex> nodeList = 
           new ArrayList<Vertex>();    // storage for vertex objects
    String input = "";                 // storage for the entire file data
    int index = 0;
    while (inFile.hasNextLine())       // read all file records 
    {
      String s = inFile.nextLine();    // read a text line from file
      if (s.length() > 0 && s.charAt(0) != '#') // ignore comments
      {
        StringTokenizer sTk = new StringTokenizer(s);
        String label = sTk.nextToken(); // vertex label
        if (! nodeMap.containsKey(label)) // check for a new vertex in hash
        {
          Vertex v = new Vertex(label);   // create the vertex object
          nodeMap.put(label, new Integer(index)); // assign to it an index
          nodeList.add(v);                        // put it into node list
          index++;
          input = input + "#" + s;     // append the input line 
        }
        else                           // this vertex is already processed
        {
          System.out.println("Multiple declaration of vertex " + label);
          System.exit(0);
        }
      }
    }

    // converting list into array
    vertices = (Vertex[]) nodeList.toArray(new Vertex[nodeList.size()]);

    // computing the adjacency list
    adjList = new int[vertices.length][];  // we already know # of vertices
    StringTokenizer sTk = new StringTokenizer(input, "#");
    for (int i=0; i<vertices.length; i++)
    {
      StringTokenizer sTk1 = new StringTokenizer(sTk.nextToken());
      adjList[i] = new int[sTk1.countTokens()-1];
      String s = sTk1.nextToken();
      for (int j=0; j<adjList[i].length; j++)
      {
        s = sTk1.nextToken();
        if (nodeMap.containsKey(s))
        { 
          int ind = (nodeMap.get(s)).intValue();
          adjList[i][j] = ind;
        }
        else
        {
          System.out.println("Undeclared vertex: " + s);
          System.exit(0);
        }
      }
    }
  }
}