// This code is from "Algorithms in Java, Third Edition,"
// by Robert Sedgewick, Addison-Wesley, 2003.
class GraphBFSedge
{
  // Program 18.7
  private Graph G;
  private int cnt;
  private int[] ord, st; 
  private void show(String s, Edge e)
  { 
    System.out.format("%s %d->%d\n",s,e.v,e.w);
  }

  private void searchC(Edge e)
  // Program 18.8
  {
    EdgeQueue Q = new EdgeQueue(G.V());
    Q.put(e);
    ord[e.w] = cnt++; 
    while (!Q.empty())
    {
      e = Q.get();
      int v = e.v, w = e.w;
      st[w] = v;        
      AdjList A = G.getAdjList(w);
      for (int t = A.beg(); !A.end(); t = A.nxt()) 
        if (ord[t] == -1) 
        {
          Q.put(new Edge(w, t));
          ord[t] = cnt++;
        }
    }
  }

  GraphBFSedge(Graph G, int v)  
  {
    this.G = G;
    cnt = 0;
    ord = new int[G.V()];
    st = new int[G.V()];
    for (int t = 0; t < G.V(); t++)
    {
      ord[t] = -1;
      st[t] = -1;
    }
    for (int t = 0; t < G.V(); t++)
      if (ord[t] == -1)
        searchC(new Edge(t, t)); 
  }
  int order(int v) { return ord[v]; }
  int ST(int v) { return st[v]; }

}