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

3 3
1 2
2 3
3 1

1

3 2
1 2
2 3

0