import java.util.*;

public class ListGraph {

   protected LinkedList M[];  // adjacency list 
   protected int n;           // number of vertices


   // Creates a graph with numVertex number of vertices by first creating an 
   // array of numVertices empty linked lists, and then creating a new linked 
   // lists for each of the vertices.

   public ListGraph (int numVertices) {
      n = numVertices;
      M = new LinkedList[n];
      for (int i=0; i<n; i++)
         M[i] = new LinkedList();
   }  

   public ListGraph (int numVertices, int type) {
	// Insert code here
   }  

   // returns a string containing the adjacency lists for each vertex.  The 
   // string should contain the vertex/weight pair for the nodes in each of 
   // the lists.  Note, that the nodes in each list do not need to be in any 
   // specific order. 

   public String toString() {   
      String result = "";
      for (int i=0; i<n; i++) {
         result += i + ": ";
         int size = M[i].size();    // number of elements in this list
         for (int j=0; j<size; j++) 
            result += (GraphEdge)M[i].get(j)  + "  ";
         result += "\n";
      } 
      return result;
   } 


   // Adds destination to source's list to indicate that destination is 
   // adjacent to source.  The edge has a weight. 
   // insert new node in LinkedList M[source] so that the list is in
   // increasing destination vertex order

   public void addEdge(int source, int destination, int weight) { 
      int curr;
      for (curr=0; curr<M[source].size(); curr++) {
         GraphEdge x = (GraphEdge)M[source].get(curr);
         if (destination < x.vertex) {
            M[source].add(curr, new GraphEdge(destination, weight));
            break;
         } 
         else if (destination == x.vertex) {
            x.weight = weight;
            break;
         } 
      } 
  
      // add the edge to the end of list.
      if (curr == M[source].size())
         M[source].add(new GraphEdge(destination, weight));

   } 


   // Removes destination from source's list to indicate that the two 
   // vertices u, v are not adjacent.  If there is no such edge, nothing 
   // should be done. No exceptions should be thrown.

   public void deleteEdge(int source, int destination) { 
      M[source].remove(new GraphEdge(destination,0));
   } 


   // This method looks in source's adjacency list for destination to 
   // determine if v is adjacent to u.
   public boolean isAdjacent(int source, int destination) { 
      return (M[source].indexOf(new GraphEdge(destination,0)) > -1);
   } 


   // returns number of nodes adjacent to node source
   public int outdegree(int source) {
      return M[source].size();
   } 

   // returns number of nodes adjacent to node source
   public int indegree(int destination) {
      int numIn = 0;
      for (int i=0; i<n; i++)
         numIn += (M[i].indexOf(new GraphEdge(destination,0)) > -1) ? 1 : 0;
      return numIn;
   } 


   // Returns the number of edges in the graph. 
   public int numberEdges() {
      int numEdges = 0;
      for (int i=0; i<n; i++)
         numEdges += M[i].size();
      return numEdges;
   } 

////////////////////////////////////////////////////

	public  int getEdgeWeight(int source, int destination) {

	// Insert code here

	}
	
	public  int [][] toAdjMatrix() {

	// Insert code here

	}



} // end ListGraph