// This solution uses an inner class to keep, for each node, adjacency
// list, colour and a bookmark in the adjacency list up to which it was
// explored in the DFS


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


public class DiGraph{

    /** Fields */

    /** HashMap to hold label objects (as keys) and their information
	neighbours, colour, bookmark in the neighbours list (as values) */

    private HashMap nodes = new HashMap();

// inner class Node to hold node information

    class Node {
       ArrayList neighbours = new ArrayList(); // keeps labels of neighbours
       String colour = "white";
       int bookmark = 0;
       Node(){}
    }
       

    /** 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 Node());
	}
    }

    /** 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()) 
		((Node) nodes.get(nodeIterator.next())).neighbours.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);

	ArrayList edges = ((Node) nodes.get(x)).neighbours;
	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) {
        Node xnode = (Node) nodes.get(x);
        if (xnode==null) 
            return false;
        else {
            ArrayList edges = xnode.neighbours;
	    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) {
        Node xnode = (Node) nodes.get(x);
        if (xnode==null)
            return false;
        else {
            ArrayList edges = xnode.neighbours;
	    return edges.contains(y);
        }
    }

    public void print() {
        Iterator it = nodes.keySet().iterator();
        while(it.hasNext()){
            Object label = it.next();
            System.out.print(label + " --> ");
            Node n = (Node) nodes.get(label);
            for (int i = 0; i < n.neighbours.size(); i++) {
                System.out.print(n.neighbours.get(i) + ", ");
            }
            System.out.println();
        }
    }

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

    public boolean loops() {
       Iterator nodeIterator = nodes.values().iterator();
// reset all nodes as unvisited and their adjacency lists untraversed
       while(nodeIterator.hasNext()){
            Node n = (Node) nodeIterator.next();
            n.colour = "white";
            n.bookmark = 0;
       }

// start iterating over nodes again
       nodeIterator = nodes.values().iterator();
  
       Stack stack = new Stack();

// repeat while there are still white vertices

       while(nodeIterator.hasNext()){
          Node start = (Node) nodeIterator.next();
          if (start.colour.equals("white")) {
             start.colour = "grey";
// do DFS from start
             stack.push(start);
             while(! stack.empty()) { 
                Node current = (Node) stack.peek();
                ArrayList adj = current.neighbours;
                int size = adj.size();
             // find current's first white neighbour
             boolean looking = true;
             while(current.bookmark < size && looking) {
                Object next_label = adj.get(current.bookmark);
                current.bookmark++;
                Node next = (Node) nodes.get(next_label);
                if (next.colour.equals("grey")) return true;
                if (next.colour.equals("white")) {
                   next.colour = "grey";
                   stack.push(next);
                   looking = false;
                }
              } // end looking for white neighbour
              if(looking) { // if have not found, pop the stack
                  current.colour = "black";
                  stack.pop();
              }
           }// end DFS loop
         }// end if (do DFS for white vertices)
       } // end loop over white vertices
       return false; // if we got here, we searched all white vertices
    }
}