import java.util.*;

/**

 * An undirected graph with a fixed number of vertices implemented using

 * adjacency lists. Space complexity is O(V + E) where V is the number

 * of vertices and E the number of edges.

 * 

 * @author Josef Nilsen

 * @version 2006-03-21

 */

public class ListGraph implements UndirectedGraph

{    

    private int numVertices; // Number of vertices in the graph

    private int numEdges; // Number of edges in the graph
    private final static int NO_COST = -1; // an edge with no cost

       

    // All vertices adjacent to v are stored in adjacentVertices[v].

    // No set is allocated if there are no adjacent vertices.

    private Set<Integer>[] adjacentVertices; // HashSet<Integer>[]

    

    // Edge costs are stored in a hash map. The key is an

    // Edge(v, w)-object and the cost is an Integer object.

    private Map<Edge, Integer> edgeCosts; // HashMap<Edge, Integer>
    
    public ListGraph(int size) {
    	if(size > 0) {
    		numVertices = size;
    		adjacentVertices = new HashSet[size];
        	edgeCosts = new HashMap<Edge, Integer>();
        	for(int i=0; i<size; i++) {
        		adjacentVertices[i] = new HashSet();
        	}
    	}
    }


    private static class Edge

    {

        private int v;

        private int w;

        

        Edge(int v, int w) {

            if (v <= w) {

                this.v = v;

                this.w = w;

            } else {

                this.v = w;

                this.w = v;

            }

        }

        

        public boolean equals(Object o) {

            if (o == null)

                return false;

            Edge e = (Edge) o;

            return (v == e.v && w == e.w);

        }

        

        public int hashCode() {

            return v<<16 + w;

        }

    }



    /**

     * Returns the number of vertices in this graph.

     * Time complexity: O(1).

     * 

     * @return the number of vertices in this graph.

     */

    public int numVertices() {

        return numVertices;

    }

    

    /**

     * Returns the number of edges in this graph.

     * Time complexity: O(1).

     * 

     * @return the number of edges in this graph.

     */

    public int numEdges() {

        return numEdges;

    }



    /**

     * Returns the degree of vertex v.

     * Time complexity: O(1).

     * 

     * @param  v vertex.

     * @return the degree of vertex v.

     * @throws IllegalArgumentException if v is out of range.

     */

    public int degree(int v) throws IllegalArgumentException {

        if (v < 0 || v >= numVertices) {
            throw new IllegalArgumentException(
                "Out of range: v = " + v + ".");

        }

        return adjacentVertices[v].size();

    }

    

    /**

     * Returns an iterator of vertices adjacent to v.

     * Time complexity for iterating over all vertices: O(n),

     * where n is the number of adjacent vertices.

     * 

     * @param  v vertex.

     * @return an iterator of vertices adjacent to v.

     * @throws IllegalArgumentException if v is out of range.

     */

    public VertexIterator adjacentVertices(int v) throws IllegalArgumentException {
        if (v < 0 || v >= numVertices) {
            throw new IllegalArgumentException(
                "Out of range: v = " + v);

        }


        return new AdjacentVerticesIterator(v);
    }

    

    private class AdjacentVerticesIterator implements VertexIterator {

        private Iterator<Integer> setIterator;

        

        public AdjacentVerticesIterator(int v) {

        	setIterator = adjacentVertices[v].iterator();

        }

        public boolean hasNext() { 

        	return setIterator.hasNext();

        }

        public int next() throws NoSuchElementException {

        	return setIterator.next();

        }

    }

    

    /**

     * Returns true if v is adjacent to w.

     * Time complexity: O(1).

     * 

     * @param  v vertex.

     * @param  w vertex.

     * @return true iff v is adjacent to w.

     * @throws IllegalArgumentException if v or w are out of range.

     */

    public boolean areAdjacent(int v, int w) throws IllegalArgumentException {
        if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) {
            throw new IllegalArgumentException(
                "Out of range: v = " + v + ", w = " + w + ".");

        }

        boolean adjacent = false;
        if (adjacentVertices[v].contains(w) || adjacentVertices[w].contains(v)) {
            adjacent = true;
        }

        return adjacent;

    }

    

    /**

     * Returns the edge cost if v is adjacent to w and an edge cost

     * has been assigned, -1 otherwise. Time complexity: O(1).

     * 

     * @param  v vertex.

     * @param  w vertex.

     * @return the edge cost (I'm assuming the boolean return-type was for the previous method).

     * @throws IllegalArgumentException if v or w are out of range.

     */

    public int edgeCost(int v, int w) throws IllegalArgumentException {
        if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) {
            throw new IllegalArgumentException(
                "Out of range: v = " + v + ", w = " + w + ".");

        }

        int edgeCost = -1;
        if (adjacentVertices[v].contains(w) || adjacentVertices[w].contains(v)) {
            if(edgeCosts.get(new Edge(v,w)) != null) {
                edgeCost = edgeCosts.get(new Edge(v,w));
            }
        }

        return edgeCost;

    }



    /**

     * Inserts an undirected edge between vertex positions v and w.

     * (No edge cost is assigned.) Time complexity: O(1).

     * 

     * @param  v    vertex position.

     * @param  w    vertex position.

     * @throws IllegalArgumentException if v or w are out of range.

     */

    public void addEdge(int v, int w) throws IllegalArgumentException {
        if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) {
            throw new IllegalArgumentException(
                "Out of range: v = " + v + ", w = " + w + ".");

        }

        if (!adjacentVertices[v].contains(w) || !adjacentVertices[w].contains(v)) {

            adjacentVertices[v].add(w);

            adjacentVertices[w].add(v);

            edgeCosts.put(new Edge(v,w),NO_COST);
            numEdges++;
		}

    }

    

    /**

     * Inserts an undirected edge with edge cost c between v and w.

     * Time complexity: O(1).

     * 

     * @param  c edge cost, c >= 0.

     * @param  v vertex.

     * @param  w vertex.

     * @throws IllegalArgumentException if v or w are out of range.

     * @throws IllegalArgumentException if c < 0.

     */

    public void addEdge(int v, int w, int c) throws IllegalArgumentException {
        if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) {
            throw new IllegalArgumentException(
                "Out of range: v = " + v + ", w = " + w + ".");

        }

        if (!adjacentVertices[v].contains(w) || !adjacentVertices[w].contains(v)) {

            adjacentVertices[v].add(w);

            adjacentVertices[w].add(v);

            edgeCosts.put(new Edge(v,w),c);
            numEdges++;
		}

    }

        

    /**

     * Removes the edge between v and w.

     * Time complexity: O(1).

     * 

     * @param  v vertex.

     * @param  w vertex.

     * @throws IllegalArgumentException if v or w are out of range.

     */

    public void removeEdge(int v, int w) throws IllegalArgumentException {
        if (v < 0 || v >= numVertices || w < 0 || w >= numVertices) {
            throw new IllegalArgumentException(
                "Out of range: v = " + v + ", w = " + w + ".");

        }

	    if (adjacentVertices[v].contains(w) || adjacentVertices[w].contains(v)) {

            adjacentVertices[v].remove(w);

            adjacentVertices[w].remove(v);

            edgeCosts.remove(new Edge(v,w));
            numEdges--;
	    }

    }

    

    /**

     * Returns a string representation of this graph.

     * 

     * @return a String representation of this graph.

     */

    public String toString() {

        StringBuilder sb = new StringBuilder();

        sb.append("Vertices: " + numVertices + " " + "Edges: {");

        Iterator<Integer> it = null;

        

        for (int i = 0; i < numVertices; i++) {

            it = adjacentVertices[i].iterator();

            while (it.hasNext()) {

                int w = it.next();

                int c = -2;
                if (edgeCosts.get(new Edge(w,i)) != null) {

                	c = edgeCosts.get(new Edge(w,i));

                } else {

                	c = NO_COST;
                }
                if (sb.lastIndexOf("(" + w + "," + i + "), ") == -1 && c == NO_COST) {

                	sb.append("(" + i + "," + w + "), ");

                } else if (sb.lastIndexOf("(" + w + "," + i + "," + c + "), ") == -1 && c >= 0) {

                	sb.append("(" + i + "," + w + "," + c + "), ");

                }

            }

        }

    	if (numEdges > 0) {

    		sb.setLength(sb.length() - 2);

    	}

    	sb.append("}");

        return sb.toString();

    }

}