// This code is from "Algorithms in Java, Third Edition,"
// by Robert Sedgewick, Addison-Wesley, 2003.
class Graph // sparse multigraph implementation
{ 
  private class AdjLinkedList implements AdjList
  { 
    private int v;
    private Node t;
    public AdjLinkedList(int v)
      { this.v = v; t = null; }
    public int beg()
      { t = adj[v]; 
        return t == null ? -1 : t.v; }
    public int nxt()
      { if (t != null) t = t.next; 
        return t == null ? -1 : t.v; }
    public boolean end()
      { return t == null; }
  }

  private int Vcnt, Ecnt;
  private boolean digraph;
  private class Node
    { int v; Node next;
      Node(int x, Node t) { v = x; next = t; }
    }
  private Node adj[];
  Graph(int V, boolean flag)
    {
      Vcnt = V; Ecnt = 0; digraph = flag;
      adj = new Node[V];
    }
  int V() { return Vcnt; }
  int E() { return Ecnt; }
  boolean directed() { return digraph; }
  void insert(Edge e)
    { int v = e.v, w = e.w;
      adj[v] = new Node(w, adj[v]);
      if (!digraph) adj[w] = new Node(v, adj[w]); 
      Ecnt++;
    } 
  AdjList getAdjList(int v)
    // Program 17.10
    { return new AdjLinkedList(v); }
}