import java.lang.*;
import java.util.*;
import node.*;

class CourseSchedule {
	public static boolean detectCycle(GraphNode node) {
		Stack<GraphNode> stack = new Stack<GraphNode>();
		ArrayList<GraphNode> visited = new ArrayList<GraphNode>();
		stack.push(node);
		while (!stack.empty()) {
			node = stack.pop();
			if (visited.contains(node)) {
				System.out.println("Cycle " + node.val);
				return true;
			}
			visited.add(node);
			System.out.println("Node: " + node.val);
			System.out.print("Neighbors: ");
			for (GraphNode neighbor : node.neighbors) {
				stack.push(neighbor);
				System.out.print(neighbor.val + " ");
			}
			System.out.println();
		}
		return false;
	}

	public static GraphNode createGraph(int[][] prerequisites) {
		HashMap<Integer, GraphNode> map = new HashMap<Integer, GraphNode>();
		for (int[] prerequisite : prerequisites) {
			if (map.containsKey(prerequisite[0])) {
				if (map.containsKey(prerequisite[1])) {
					map.get(prerequisite[0]).neighbors.add(map.get(prerequisite[1]));
				} else {
					GraphNode node = new GraphNode(prerequisite[1]);
					map.put(node.val, node);
					map.get(prerequisite[0]).neighbors.add(node);
				}
				continue;
			}
			GraphNode pre = new GraphNode(prerequisite[1]);
			GraphNode node = new GraphNode(prerequisite[0],
					new ArrayList<GraphNode>(Arrays.asList(pre)));
			map.put(pre.val, pre);
			map.put(node.val, node);
		}
		// TODO: return first GraphNode in map
		return map.get(1);
	}

	public static boolean canFinish(int[][] prerequisites) {
		GraphNode node = createGraph(prerequisites);
		return !detectCycle(node);
	}

	public static void main(String[] args) {
		int[][] prerequisites = {{1, 4}, {1, 2}, {2, 3}, {3, 6}, {6, 2}, {4, 5}};
		System.out.println(canFinish(prerequisites));
	}
}