Course Schedule

There are n courses labeled 0 to n-1. Some courses have prerequisites, given as pairs (a, b) meaning you must take b before a. Print true if it's possible to finish all courses (i.e. no cycle in the prerequisite graph), false otherwise.

Example

Input:

(2 courses, 1 prerequisite pair: 1 requires 0) Output: true

Approach

Build an adjacency list from prerequisites, then detect a cycle via DFS with a "currently in this DFS path" set (not just a global visited set) — a node reached while already on the current path means a cycle, so it's impossible to finish.

Input format

Line 1: number of courses N Line 2: number of prerequisite pairs P Next P lines: a b meaning a requires b