import java.util.*;

public class Network<Vertex> implements Iterable<Vertex>
{
  	protected HashMap<Vertex, LinkedList<VertexWeightPair>> adjacencyMap;


  	/**
   	 *  Initialized this Network object to be empty.
   	 */
  	public Network()
  	{
    		adjacencyMap = new HashMap<Vertex,LinkedList<VertexWeightPair>>();
  	} // default constructor


  	/**
   	 *  Initializes this Network object to have a specified initial capacity.
   	 *
   	 *  @param capacity - the initial capacity of this Network object.
   	 *
   	 *  @throws IllegalArgumentException – if capacity is less than 0.
   	 *
   	 */
  	public Network (int capacity)
  	{
    		if (capacity <= 0)
          		throw new IllegalArgumentException ("number of vertices must be positive");
    		adjacencyMap = new HashMap<Vertex,LinkedList<VertexWeightPair>>(capacity, 1.0f);
  	} // constructor


  	/**
   	 *  Initializes this Network object to a shallow copy of a specified Network
   	 *  object.
   	 *  The averageTime(V, E) is O(V + E).
   	 *
   	 *  @param network - the Network object that this Network object is
	 *                                 initialized to a shallow copy of.
  	 *
  	 */
  	public Network (Network<Vertex> network)
  	{
    		adjacencyMap = new HashMap<Vertex,LinkedList<VertexWeightPair>>(network.adjacencyMap);
  	} // copy constructor


  	/**
 	 *  Determines if this Network object contains no vertices.
  	 *
  	 *  @return true - if this Network object contains no vertices.
  	 *
  	 */
  	public boolean isEmpty()
  	{
    		return adjacencyMap.isEmpty();
  	} // method isEmpty


  	/**
  	 *  Determines the number of vertices in this Network object.
  	 *
  	 *  @return the number of vertices in this Network object.
  	 *
  	 */
  	public int size()
  	{
    		return adjacencyMap.size();
  	} // method size


  	/**
  	 *  Returns the number of edges in this Network object.
  	 *  The averageTime (V, E) is O (V).
  	 *
  	 *  @return the number of edges in this Network object.
  	 *
  	 */
  	public int getEdgeCount()
  	{
        	int count = 0;

		for (Vertex vertex : adjacencyMap.keySet())
             		count += (adjacencyMap.get (vertex)).size();
        	return count;
  	} // method getEdgeCount


  	/**
  	 *  Determines the weight of an edge in this Network object.
  	 *  The averageTime (V, E) is O (E / V).
  	 *
  	 *  @param v1 - the beginning Vertex object of the edge whose weight is sought.
  	 *  @param v2 - the ending Vertex object of the edge whose weight is sought.
  	 *
  	 *  @return the weight of edge <v1, v2>, if <v1, v2> forms an edge; return –1.0 if
  	 *                <v1, v2> does not form an edge in this Network object.
  	 *
  	 */
  	public double getEdgeWeight (Vertex v1, Vertex v2)
  	{
    		if (! (adjacencyMap.containsKey (v1) && adjacencyMap.containsKey (v2)))
      			return -1.0;

    		LinkedList<VertexWeightPair> list = adjacencyMap.get (v1);
    		for (VertexWeightPair vertexWeightPair : list)
      			if (vertexWeightPair.getVertex().equals (v2))
        			return vertexWeightPair.getWeight();
    		return -1.0;  // there is no edge <v1, v2>
  	} // method getEdgeWeight


  	/**
  	 *  Determines if this Network object contains a specified Vertex object.
  	 *
  	 *  @param vertex - the Vertex object whose presence is sought.
  	 *
  	 *  @return true - if vertex is an element of this Network object.
  	 */
  	public boolean containsVertex (Vertex vertex)
  	{
    		return adjacencyMap.containsKey (vertex);
  	} // method containsVertex


  	/**
  	 *  Determines if this Network object contains an edge specified by two vertices.
  	 *  The averageTime (V, E) is O (E / V).
  	 *
  	 *  @param v1 - the beginning Vertex object of the edge sought.
  	 *  @param v2 - the ending Vertex object of the edge sought.
  	 *
  	 *  @return true - if this Network object contains the edge <v1, v2>.
  	 *
  	 */
  	public boolean containsEdge (Vertex v1, Vertex v2)
  	{
    		if (!(adjacencyMap.containsKey (v1) && adjacencyMap.containsKey (v2)))
      			return false;

    		for (VertexWeightPair vertexWeightPair : adjacencyMap.get(v1))
          		if (vertexWeightPair.getVertex().equals (v2))
          	   		return true;
    		return false;
  	} // method containsEdge


  	/**
  	 *  Ensures that a specified Vertex object is an element of this Network object.
  	 *
  	 *  @param vertex - the Vertex object whose presence is ensured.
  	 *
  	 *  @return true - if vertex was added to this Network object by this call; returns
  	 *               false if vertex was already an element of this Network object when
  	 *               this call was made.
  	 */
  	public boolean addVertex (Vertex vertex)
  	{     
        	if (adjacencyMap.containsKey (vertex))
            		return false;
        	adjacencyMap.put (vertex, new LinkedList<VertexWeightPair>());
        	return true;
  	} // method addVertex



  	/**
  	 *  Ensures that an edge is in this Network object.
  	 *
  	 *  @param v1 - the beginning Vertex object of the edge whose presence
  	 *                         is ensured.
  	 *  @param v2 - the ending Vertex object of the edge whose presence is
  	 *                        ensured.
  	 *  @param weight - the weight of the edge whose presence is ensured.
  	 *
  	 *  @return true - if the given edge (and weight) were added to this Network
  	 *                         object by this call; return false, if the given edge (and weight)
  	 *                         were already in this Network object when this call was made.
  	 *
  	 */
  	public boolean addEdge (Vertex v1, Vertex v2, double weight)
  	{
    		addVertex (v1);
    		addVertex (v2);
    		VertexWeightPair vertexWeightPair = new VertexWeightPair (v2, weight);
    		adjacencyMap.get(v1).add (vertexWeightPair);
    		return true;
  	} // method addEdge


  	/**
  	 *  Ensures that a specified Vertex object is not an element of this Network object.
  	 *  The averageTime (V, E) is O (V + E).
  	 *
  	 *  @param vertex - the Vertex object whose absence is ensured.
  	 *
  	 *  @return true - if vertex was removed from this Network object by this call;
  	 *                returns false if vertex was not an element of this Network object
  	 *                when this call was made.
         *   
	 */
  	public boolean removeVertex (Vertex vertex)
  	{
        	if (!adjacencyMap.containsKey (vertex))
            		return false;

        	for (Vertex v : adjacencyMap.keySet()) 
        	{
            		LinkedList<VertexWeightPair>list = adjacencyMap.get(v);

            		// If vertex is in a vertex-weight pair on list, remove that pair from list.
            		Iterator<VertexWeightPair> listItr = list.iterator();
            		while (listItr.hasNext())
                		if ((listItr.next()).getVertex().equals (vertex)) 
				{
                    			listItr.remove();
        	            		break;
                		} // vertex-weight pair found and removed from list 
        	} // for each vertex in the network
        	adjacencyMap.remove (vertex);
        	return true;
   	} // removeVertex



  	/**
   	 *  Ensures that an edge specified by two vertices is absent from this Network
   	 *  object.
   	 *  The averageTime (V, E) is O (E / V).
   	 *
   	 *  @param v1 - the beginning Vertex object of the edge whose absence is
   	 *                          ensured.
   	 *  @param v2 - the ending Vertex object of the edge whose absence is
   	 *                        ensured.
   	 *
   	 *  @return true - if the edge <v1, v2> was removed from this Network object
   	 *                          by this call; return false if the edge <v1, v2> was not in this
   	 *                          Network object when this call was made.
    	 *
   	 */
  	public boolean removeEdge (Vertex v1, Vertex v2)
  	{
    		if (!adjacencyMap.containsKey (v1) || !adjacencyMap.containsKey (v2))
	      		return false;

    		Iterator<VertexWeightPair> itr = adjacencyMap.get (v1).iterator();
    		while (itr.hasNext())
      			if (itr.next().getVertex().equals (v2))
    			{
      				itr.remove();
      				return true;
    			} // if
    		return false;
  	} // method removeEdge


  	/**
  	 *  Returns a LinkedList object of the neighbors of a specified Vertex object.
  	 *
  	 *  @param v - the Vertex object whose neighbors are returned.
  	 *
  	 *  @return a LinkedList of the vertices that are neighbors of v.
   	 */
  	public LinkedList<Vertex> neighbors (Vertex v)
  	{
    		LinkedList<Vertex> neighbors = new LinkedList<Vertex>();
    		for (VertexWeightPair vertexWeightPair : adjacencyMap.get(v))
        		neighbors.add (vertexWeightPair.getVertex());
    		return neighbors;
  	} // method neighbors


  	/**
  	 *  Returns an Iterator object over the vertices in this Network object.
  	 *
  	 *  @return an Iterator object over the vertices in this Network object.
  	 *
  	 */
  	public Iterator<Vertex> iterator()
  	{
        	return adjacencyMap.keySet().iterator();
  	} // method iterator



  	/**
  	 *  Returns a breadth-first Iterator object over all vertices reachable from
  	 *  a specified Vertex object.
  	 *  The averageTime(V, E) is O(V).
  	 *
  	 *  @param v - the start Vertex object for the Iterator object returned.
  	 *
  	 *  @return a  breadth-first Iterator object over all vertices reachable from v.
  	 *
  	 *  @throws IllegalArgumentException – if v is not an element of this Network
  	 *                 object.
  	 *
  	 */
  	public BreadthFirstIterator breadthFirstIterator (Vertex v)
  	{
    		if (!adjacencyMap.containsKey (v))
      			return null;
    		return new BreadthFirstIterator(v);
  	} // method breadthFirstIterator


  	/**
  	 *  Returns a depth-first Iterator object over all vertices reachable from
  	 *  a specified Vertex object.
  	 *  The averageTime(V, E) is O(V).
  	 *
  	 *  @param v - the start Vertex object for the Iterator object returned.
  	 *
  	 *  @return a  depth-first Iterator object over all vertices reachable from v.
  	 *
  	 *  @throws IllegalArgumentException – if v is not an element of this Network
  	 *                 object.
  	 *
  	 */
  	public DepthFirstIterator depthFirstIterator (Vertex v)
  	{
    		if (!adjacencyMap.containsKey (v))
      			return null;
    		return new DepthFirstIterator(v);
  	} // method depthFirstIterator


  	/**
  	 *  Determines if this (directed) Network object is connected.
  	 *  The averageTime(V, E) is O(VE + V * V).
  	 *
  	 *  @return true – if this (directed) Network object is connected.
  	 *
  	 */
  	public boolean isConnected()
  	{
    		for (Vertex v : adjacencyMap.keySet())
        	{
      			// Count the vertices reachable from v.
      			Iterator<Vertex> itr2 = new BreadthFirstIterator (v);
      			int count = 0;
      			while (itr2.hasNext())
      			{
        			itr2.next();
        			count++;
      			} // while
      			if (count < adjacencyMap.size())
        			return false;
    		} // for
    		return true;
  	} // method isConnected


  	/**
  	 *  Returns a minimum spanning tree for this connected Network object.
  	 *  The averageTime(V, E) is O(E log V).
  	 *
  	 *  @return a minimum spanning tree for this connected Network object.
  	 *
  	 *  @throws UnsupportedOperationException, if there is no path from the
  	 *                 chosen root to every other vertex in this Network object.
  	 *  
  	 */
  	public WeightedTree<Vertex> getMinimumSpanningTree()
  	{
        	WeightedTree<Vertex> tree = new WeightedTree<Vertex>();

        	PurePriorityQueue<EdgeTriple> pq = new Heap<EdgeTriple>();

        	EdgeTriple edgeTriple;

        	Vertex root,
               	       w,
                       x,
                       y,
                       z;

        	Iterator<Vertex> netItr;

        	Iterator<VertexWeightPair> listItr;

        	double weight;

        	if (isEmpty())
             		return tree;
        	netItr = adjacencyMap.keySet().iterator();
        	root = netItr.next();

        	tree.addVertex (root);

        	for (VertexWeightPair vertexWeightPair : adjacencyMap.get (root))
        	{
           		w = vertexWeightPair.getVertex();
            		weight = vertexWeightPair.getWeight();
            		edgeTriple = new EdgeTriple (root, w, weight);
            		pq.add (edgeTriple);
        	} // adding root's edgeTriples to pq

        	while (tree.size() < size())
        	{
			if (pq.isEmpty())
				throw new UnsupportedOperationException();
            		edgeTriple = pq.removeMin();
            		x = edgeTriple.getFromVertex();
            		y = edgeTriple.getToVertex();
            		weight = edgeTriple.getWeight();
            		if (!tree.containsVertex (y))
            		{
              			tree.addVertex (y);
                  		tree.addEdge (x, y, weight);

                  		for (VertexWeightPair vertexWeightPair : adjacencyMap.get(y))
                  		{
                   			z = vertexWeightPair.getVertex();
                        		if (!tree.containsVertex (z))
            				{
                           			weight = vertexWeightPair.getWeight();
                              			edgeTriple = new EdgeTriple (y, z, weight);
                              			pq.add (edgeTriple);
                        		} // z not already in tree
                  		} // iterating over y's neighbors
          		} // y not already in tree
        	} // tree has fewer vertices than this Network
        	return tree;
  	} // method getMinimumSpanningTree


  	/**
  	 *  Finds a shortest path between two specified vertices in this Network
  	 *  object.
  	 *  The averageTime(V, E) is O(E log V).
  	 *
  	 *  @param v1 - the beginning Vertex object.
  	 *  @param v2 - the ending Vertex object.
  	 *
  	 *  @return a LinkedList object containing the vertices in a shortest path
  	 *                from Vertex v1 to Vertex v2.
  	 *
  	 */
  	public LinkedList<Object> getShortestPath (Vertex v1, Vertex v2)
  	{
        	final double MAX_PATH_WEIGHT = Double.MAX_VALUE;

        	HashMap<Vertex,Double> weightSum = new HashMap<Vertex,Double>();

        	HashMap<Vertex,Vertex> predecessor = new HashMap<Vertex,Vertex>();

        	PurePriorityQueue<VertexWeightPair> pq = new Heap<VertexWeightPair>();

        	Iterator<VertexWeightPair> listItr;

        	Vertex vertex,
               	       to = null,
                       from;

        	VertexWeightPair vertexWeightPair;

        	double weight;
	
		if (! (adjacencyMap.containsKey (v1) && adjacencyMap.containsKey (v2)))
            		return new LinkedList<Object>();
		Iterator<Vertex> netItr = breadthFirstIterator(v1);
  		while (netItr.hasNext()) 
		{
            		vertex = netItr.next();
            		weightSum.put (vertex, MAX_PATH_WEIGHT);
            		predecessor.put (vertex, null);
		} // initializing weightSum and predecessor
		weightSum.put (v1, 0.0);
		predecessor.put (v1, v1);
		pq.add (new VertexWeightPair (v1, 0.0));

  		boolean pathFound = false;
		while (!pathFound && !pq.isEmpty()) 
		{
   			vertexWeightPair = pq.removeMin();
          		from = vertexWeightPair.getVertex();
          		if (from.equals (v2))
                		pathFound = true;
          		else if (vertexWeightPair.getWeight( ) <= weightSum.get(from)) 
			{                	 
				for (VertexWeightPair pair : adjacencyMap.get (from))
				{
                    			to = pair.getVertex();
                    			weight = pair.getWeight();
                    			if (weightSum.get (from) + weight < weightSum.get (to)) 
					{
                       				weightSum.put (to, weightSum.get (from) + weight);
                        			predecessor.put (to, from);
                        			pq.add (new VertexWeightPair (to,weightSum.get (to)));
                    			} // if
                		} // processing from's neighbors 
           		} // else path not yet found
		} // while not done and priority queue not empty

		LinkedList<Object> path = new LinkedList<Object>();
		if (pathFound) 
		{
      			Vertex current = v2;
            		while (!(current.equals (v1))) 
			{
                		path.addFirst (current);
                		current = predecessor.get (current);
           		} // while not back to v1
           		path.addFirst (v1);
		} // if path found
		path.addLast (weightSum.get (v2));
		return path;
  	} // method findShortestPath

 

  	public LinkedList<Object> getCycle()
  	{
    		LinkedList<Object> cycle = new LinkedList<Object>();

    		double cycleWeight = 0.0;

    		LinkedList<VertexWeightPair> edgeList;

    		Iterator<Vertex> itr = iterator();

    		Vertex v,
           	       start = itr.next();

    		cycle.add (start);
    		v = start;
    		while (cycle.size() < size())
    		{
        		edgeList = adjacencyMap.get (v);
        		for (VertexWeightPair vertexWeightPair : edgeList)
        		{
            			v = vertexWeightPair.getVertex();
            			if (!cycle.contains (v))
            			{
                			cycle.add (v);
                			cycleWeight += vertexWeightPair.getWeight();
                			break;
             			} // if
        		} // for
     		} // while
     		cycle.add (start);
     		cycleWeight += getEdgeWeight (v, start);
     		cycle.add (cycleWeight);
     		return cycle;
  	} // method getCycle


  	/**
  	 *  Returns a String representation of this Network object.
  	 *  The averageTime(V, E) is O(V + E).
  	 *
  	 *  @return a String representation of this Network object.
  	 *
  	 */
  	public String toString()
  	{
    		return adjacencyMap.toString();
  	} // method toString


  	protected class BreadthFirstIterator implements Iterator<Vertex>
  	{
    		protected PureQueue<Vertex> queue;

    		protected HashMap<Vertex, Boolean> reached;

    		protected Vertex current;

    		/**
    		 * Initializes this BreadthFirstIterator at start.
    		 *
    		 */
    		public BreadthFirstIterator (Vertex start)
    		{
      			queue = new LinkedListPureQueue<Vertex>();

      			reached = new HashMap<Vertex, Boolean>();

      			Iterator<Vertex> itr = adjacencyMap.keySet().iterator();
      			while (itr.hasNext())
        			reached.put (itr.next(), false);

      			queue.enqueue (start);
      			reached.put (start, true);
    		} // one-parameter constructor


    		/**
     	  	 * Returns true if this BreadthFirstIterator has not reached all of its 
    		 * reachable vertices.  Otherwise, returns false.
    		 *
    		 */
    		public boolean hasNext()
    		{
      			return !(queue.isEmpty());
    		} // method hasNext


    		/**
     		 * Returns the next reachable vertex in this BreadthFirstIterator object.
    		 *
    		 */    
    		public Vertex next()
    		{
      			VertexWeightPair vertexWeightPair;

      			Vertex to;

      			current = queue.dequeue();

      			LinkedList<VertexWeightPair> edgeList = adjacencyMap.get (current);

      			Iterator<VertexWeightPair> itr = edgeList.iterator();
      			while (itr.hasNext())
      			{
        			vertexWeightPair = itr.next();
        			to = vertexWeightPair.getVertex();

        			if (!reached.get (to))
        			{
          				reached.put (to, true);
          				queue.enqueue (to);
        			} // if
      			} // while
      			return current;
    		} // method next


    		/**
    		 * Removes the most recently returned vertex.
    		 *
    		 */
    		public void remove()
    		{
      			removeVertex (current);
    		} // method remove

  	} // class BreadthFirstIterator


  	protected class DepthFirstIterator implements Iterator<Vertex>
  	{
    		PureStack<Vertex> stack;

    		HashMap<Vertex, Boolean> reached;

    		Vertex current;


    		/**
    		 * Initializes this DepthFirstIterator at start.
    		 *
    		 */
    		public DepthFirstIterator (Vertex start)
    		{
      			stack = new ArrayPureStack<Vertex>();

      			reached = new HashMap<Vertex, Boolean>();

      			Iterator<Vertex> itr = adjacencyMap.keySet().iterator();
      			while (itr.hasNext())
        			reached.put (itr.next(), false);

      			stack.push (start);
      			reached.put (start, true);
    		} // one-parameter constructor


    		/**
    		 * Returns true if this DepththFirstIterator has not reached all of its 
    		 * reachable vertices.  Otherwise, returns false.
    		 *
    		 */
    		public boolean hasNext()
    		{
      			return !(stack.isEmpty());
    		} // method hasNext


    		/**
    		 * Returns the next reachable vertex in this DepththFirstIterator object.
    		 *
    		 */    
    		public Vertex next()
    		{
      			VertexWeightPair vertexWeightPair;

      			Vertex to;

      			current = stack.pop();

      			LinkedList<VertexWeightPair> edgeList = adjacencyMap.get (current);
      			Iterator<VertexWeightPair> itr = edgeList.iterator();
      			while (itr.hasNext())
      			{
        			vertexWeightPair = itr.next();
        			to = vertexWeightPair.getVertex();
        			if (!reached.get (to))
        			{
          				reached.put (to, true);
          				stack.push (to);
        			} // if
      			} // while
      			return current;
    		} // method next


    		/**
    		 * Removes the most recently returned vertex.
    		 *
    		 */
    		public void remove()
    		{
      			Network.this.removeVertex (current);
    		} // method remove

  	} // class DepthFirstIterator


  	protected class VertexWeightPair implements Comparable<VertexWeightPair>
  	{
    		Vertex vertex; 

    		double weight;


    		/**
    		 * Initializes this VertexWeightPair from vertex and weight.
    		 *
    		 */
    		public VertexWeightPair (Vertex vertex, double weight)
    		{
      			this.vertex = vertex;
      			this.weight = weight;
    		} // default constructor


    		/**
    		 *  Returns the vertex in this VertexWeightPair.
    		 *
    		 */
    		public Vertex getVertex()
    		{
      			return vertex;
    		} // method getVertex


    		/**
    		 *  Returns the weight in this VertexWeightPair.
    		 *
    		 */
    		public double getWeight()
    		{
      			return weight;
    		} // method getWeight


    		/**
    		 *  Returns an int <, = or > 0 , depending on whether this VertexWeightPair's 
    		 *  weight is <, = or > other's weight.
    		 *
    		 */
    		public int compareTo (VertexWeightPair other)
    		{
      			return (int)(weight - other.getWeight());
    		} // method compareTo


    		/**
    		 *  Returns a String representation of this VertexWeightPair.
    		 *
    		 */
    		public String toString()
    		{
      			return vertex.toString() + "  " + String.valueOf (weight);
    		} // method toString

  	} // class VertexWeightPair



  	protected class EdgeTriple implements Comparable<EdgeTriple>
  	{
    		Vertex from,
           	       to;

    		double weight;


    		/**
    		 *  Initializes this EdgeTriple from v1, v2 and weight.
    		 *
    		 */
    		public EdgeTriple (Vertex v1, Vertex v2, double weight)
    		{
      			from = v1;
      			to = v2;
      			this.weight = weight;
    		} // default constructor


    		/**
    		 *  Returns the "from" vertex in this EdgeTriple.
    		 *
    		 */
    		public Vertex getFromVertex()
    		{
     	 		return from;
    		} // method getFromVertex


    		/**
    		 *  Returns the "to" vertex in this EdgeTriple.
    		 *
    		 */
    		public Vertex getToVertex()
    		{
      			return to;
    		} // method getToVertex


    		/**
    		 *  Returns the weight vertex in this EdgeTriple.
    		 *
    		 */
    		public double getWeight()
    		{
      			return weight;
    		} // method getWeight


    		/**
    		 *  Returns an int <, = or > 0, depending on whether this EdgeTriple's 
    		 *  weight is <, = or > edge's weight.
    		 *
    		 */
    		public int compareTo (EdgeTriple edge)
    		{
      			return (int)(weight - edge.getWeight());
    		} // method compareTo


    		/**
    		 *  Returns a String representation of this EdgeTriple.
    		 *
    		 */
    		public String toString()
    		{
      			return from.toString() + "  " + to.toString() + String.valueOf (weight);
    		} // method toString

  	} // class EdgeTriple

} // class Network