A certification track has n exams, numbered 1 to n, and m prerequisite rules. Rule u v means exam u must be passed before a candidate is allowed to attempt exam v. Rules may repeat, and a rule may even require an exam as its own prerequisite (u v with u = v), which makes that exam impossible to schedule.
Determine whether there exists SOME order in which a candidate could take all n exams, one at a time, satisfying every prerequisite rule.
Input format
Line 1: two integers n and m — number of exams (1-indexed) and number of prerequisite rules.
Next m lines: two integers u v — exam u must be passed before exam v.
Output format
A single integer: 1 if all n exams can be scheduled in some valid order, 0 otherwise.
Constraints
- 1 ≤ n ≤ 40
- 0 ≤ m ≤ 200
- 1 ≤ u, v ≤ n