// This code is from "Algorithms in Java, Third Edition,"
// by Robert Sedgewick, Addison-Wesley, 2003.
class GraphDFS
{ private Graph G;
  private int depth, cnt, cntP;
  private int[] pre, post; 
  private void show(String s, Edge e)
    { 
      for (int k = 0; k < depth; k++) 
        System.out.print("  ");
      System.out.println(e.v + "-" + e.w + " " + s); 
    }
  private void dfsR(Edge e)
    { int w = e.w; show("tree", e); 
      pre[w] = cnt++; depth++;
      AdjList A = G.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        { Edge x = new Edge(w, t);
          if (pre[t] == -1) dfsR(x);
          else if (post[t] == -1) show("back", x);
          else if (pre[t] > pre[w]) show("down", x);
          else show("cross", x);
        }
      post[w] = cntP++; depth--;
    }
  GraphDFS(Graph G, int v)  
    { this.G = G; depth = 0; cnt = 0; cntP = 0;
      pre = new int[G.V()]; post = new int[G.V()];
      for (int t = 0; t < G.V(); t++)
        { pre[t] = -1; post[t] = -1; }
      for (int t = 0; t < G.V(); t++)
        if (pre[t] == -1) dfsR(new Edge(t, t)); 
    }
}