A project has n tasks, numbered 1 to n, and m dependency rules. Each rule u v means task u must be completed before task v can start. A dependency edge is one-way (directed): u v does NOT imply v must precede u.
The rules are a deadlock if there is no way to complete all tasks one at a time while respecting every rule — equivalently, the directed dependency graph contains a cycle. Rules may repeat, and a rule may even point a task at itself (u v with u = v), which is always a deadlock on its own.
Determine whether the dependencies are deadlocked.
Input format
Line 1: two integers n and m — number of tasks (1-indexed) and number of rules.
Next m lines: two integers u v — a directed rule meaning task u precedes task v.
Output format
A single integer: 1 if the dependencies contain a cycle (deadlock), 0 otherwise.
Constraints
- 1 ≤ n ≤ 40
- 0 ≤ m ≤ 200
- 1 ≤ u, v ≤ n