Course Schedule (Cycle Detection)

Problem statement

A training program specifies prerequisites between courses. A learner may take a course only after all of its prerequisite courses, and the registrar wants to know whether there is any order that completes the whole program. Your task Given n courses and pairs a b meaning course b must be completed before a, determine whether all courses can be completed. Important details A directed cycle makes completion impossible. Disconnected groups of courses must all be considered, while a course with no prerequisites can be taken immediately. The output asks only whether an ordering exists, not for one particular ordering. Worked example For pairs (1, 0) and (2, 1), the order 0, 1, 2 works and the result is true. Adding (0, 2) would create a cycle.

Input format

First line: n m. Next m lines: a b prerequisite pairs.

Output format

Print true if the condition holds, otherwise false.

Constraints

1 <= n <= 2000; 0 <= m <= 5000; 0 <= a, b < n; pairs are distinct.

Sample input

3 2
1 0
2 1

Sample output

true