import java.util.*;
import java.io.*;


public class DiGraph{

    /** Fields */

    /** HashMap to hold label objects (as keys) and lists of their
	neighbours (as values) */

    private HashMap nodes = new HashMap();

    /** Methods */
      
    /** Adds a node labelled by the object x to the graph.  If the graph
	contains a node with a label which equals() x, does nothing.  */

    public void addNode(Object x) {
	if (!nodes.containsKey(x)) {
	    nodes.put(x, new LinkedList());
	}
    }

    /** Removes the node labelled by the object x from the graph if it is
	present, otherwise does nothing.  Returns true if the graph
	contained the specified node.  */

    public boolean removeNode(Object x) {
	if (nodes.containsKey(x)) {
	    nodes.remove(x);
	    // now remove it from other lists!
	    Iterator nodeIterator = nodes.keySet().iterator();
	    while (nodeIterator.hasNext()) 
		((LinkedList) nodes.get(nodeIterator.next())).remove(x);
	    return true;
	}
	return false;
    }

    /** Returns true if the graph contains a node labelled by the object
	x and false otherwise */

    public boolean containsNode(Object x) {
	return nodes.containsKey(x);
    }


    /** Adds an edge from the node labelled by the object x to the node
	labelled by the object y to the graph.  If the graph already
	contains an edge from a node with a label which equals() x to a
	node with a label which equals() y does nothing.  If the nodes
	don't exist, they are created.  */

    public void addEdge(Object x, Object y) {
	addNode(x);
	addNode(y);

	LinkedList edges = (LinkedList) nodes.get(x);
	if (!edges.contains(y)) edges.add(y);
    }

    /** Removes the edge from the node labelled by the object x to the
	node labelled by the object y if it is present, otherwise does
	nothing.  Returns true if the graph contained the specified
	edge.  */
   
    public boolean removeEdge(Object x, Object y) {
        LinkedList edges = (LinkedList) nodes.get(x);
        if (edges == null)
	    return false;
	else
	    return edges.remove(y);
    }

    /** Returns true if the graph contains an edge from the node labelled
	by the object x to the node labelled by the object y and false
	otherwise.  */

    public boolean containsEdge(Object x, Object y) {
        LinkedList edges = (LinkedList) nodes.get(x);
        if (edges == null) 
	    return false;
	else
	    return edges.contains(y);
    }

    public void print() {
        Iterator it = nodes.keySet().iterator();
        while (it.hasNext()) {
           Object label = it.next();
           System.out.print(label + " --> ");
           LinkedList neighbours = (LinkedList) nodes.get(label);
           Iterator neighboursIterator = neighbours.iterator();
           while (neighboursIterator.hasNext()) {
              System.out.print(neighboursIterator.next() + ", ");
           }
           System.out.println();
        }
    }

/** returns true iff the graph contains a cycle */

    public boolean loops() {
       HashMap white = new HashMap();
       HashMap gray =  new HashMap();
       HashMap black = new HashMap();
       Boolean mark = Boolean.TRUE;
       Iterator nodeIterator = nodes.keySet().iterator();
       while(nodeIterator.hasNext()){
          white.put(nodeIterator.next(), mark);
       }
  
       Stack stack = new Stack();

// repeat while there are still white vertices

       while(!white.isEmpty()) {
          Iterator whiteIterator = white.keySet().iterator();
          Object start = whiteIterator.next();
          gray.put(start,mark);
          white.remove(start);
          stack.push(start);
          while(! stack.empty()) { // DFS loop: DFS from start
             Object current = stack.peek();
             ListIterator li = ((LinkedList) nodes.get(current)).listIterator(0);        
             // find current's the first white neighbour
             boolean looking = true;
             while(li.hasNext() && looking) {
                Object neighbour = li.next();
                if (gray.get(neighbour) != null) return true;

                if (white.get(neighbour) !=null) {
                   white.remove(neighbour);
                   gray.put(neighbour,mark);
                   stack.push(neighbour);
                   looking = false;
                }
              } // end looking for white neighbour
              if(looking) { // if have not found, pop the stack
                  gray.remove(current);
                  black.put(current, mark);
                  stack.pop();
              }
           }// end DFS loop
       } // end loop over white vertices
       return false; // if we got here, we searched all white vertices
    }
}