import java.util.*;

/** An instance is a graph implemented as an adjacency list */
public class AdjacencyList {
    private LNode[] V;  // The adjacency list for the graph
    private int Esize;  // number of edges
    
    /** Constructor: a graph of n nodes, with e edges
        given by edge set E[0..e-1].
        Precondition: the edges are all different. */
    public AdjacencyList(int n, int e, Edge[] E) {
        V= new LNode[n];
        for (int k= 0; k != e; k= k+1) {
            int start= E[k].start;
            int end= E[k].end;
            int weight= E[k].weight;
            V[start]= new LNode(end, weight, V[start]);
            
            Esize= e;
        }
    }
    
    /** Print this graph */
    public void print() {
        System.out.println("nodes: " + V.length + ", edges: " + Esize);
        for (int w= 0; w != V.length; w= w + 1) {
            // Print out adjacency list for node w
            String res= "";
            Iterator it= adjacencyEnumerator(w);
            while (it.hasNext()) {
                Edge e= (Edge)it.next();
                res= res + e;
            }
            if (!res.equals(""))
                System.out.println(res);
        }
    }
    
    /** An AdjacencyList for first graph. This graph is the one
        in Weiss, section 14.3., where he does shortest paths */
    public static AdjacencyList G1() {
        Edge[] E= new Edge[12];
        int[] starts= {0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 6 };
        int[] wts=    {2, 1, 3,10, 4, 5, 2, 2, 8, 4, 6, 1 };
        int[] ends=   {1, 3, 3, 4, 0, 5, 2, 4, 5, 6, 6, 5 };
        for (int k= 0; k != E.length; k= k + 1) {
            E[k]= new Edge(starts[k], wts[k], ends[k]);
        }
             
        return new AdjacencyList(7, 12, E);
    }
    
    /** A graph with n nodes. There is an edge from each node i to i+1
        and an edge from each node i to 2*i+1. All weights are 1 */
    public static AdjacencyList G2(int n) {
        int p= 0; // number of edges created
        Edge[] E= new Edge[2*n];
        for (int k= 0; k < n; k= k+1) {
            if (k != 0 && k != n-1) {
                E[p]= new Edge(k, 1, k+1);
                p= p+1;
            }
            if (2*k + 1 < n) {
                E[p]= new Edge(k, 1, 2*k+1);
                p= p+1;
            }   
        }
        
        Edge[] E1= new Edge[p];
        for (int h= 0; h < p; h= h+1) {
            E1[h]= E[h];
        }
             
        return new AdjacencyList(n, p, E1);
    }
    
    /** = number of nodes in graph */
    public int Vsize() {
        return V.length;
    }
    
    /** = number of edges in graph */
    public int Esize() {
        return Esize;
    }
 
    
    /** An instance is a node of the linked list, say of edges from
        a node v */
    private class LNode {
        int w; // A vertex number
        int weight; // the weight of edge (v,w)
        LNode next; // rest of list
        
        /** A linked list consisting of node k wih weight we followed by items of L */
        public LNode(int k, int we, LNode L) {
            w= k;
            weight= we;
            next= L;
        }
    }
    
    /** = an enumerator over vertices adjacent to vertex w */
    public Iterator adjacencyEnumerator(int w) {
        return new LIterator(w);
    }
    
    /** An enumerator of linked list L */
    private class LIterator implements Iterator {
        private LNode rest; // rest of list to enumerate (null if none)
        private int v;      // Enumerating edges with start vertex v
        
        /** Constructor: an iterator the edges from node v */
        public LIterator (int v) {
            this.v= v;
            rest= V[v];
        }
        
        /** = there is another item to enumerate */
        public boolean hasNext() {
            return rest != null;
        }
        
        /** = next item to enumerate, as an Edge. If none to
              enumerate, throw NoSuchElementException */
        public Object next() {
            if (rest == null)
                throw new NoSuchElementException();
            LNode temp= rest;
            rest= rest.next;
            return new Edge(v, temp.weight, temp.w);
        }
        
        /** Not implemented */
        public void remove() {}
        
    }
    
}