p02369 Cycle Detection for a Directed Graph
Find a cycle in a directed graph G(V, E).

Constraints

* 1 ≤ |V| ≤ 100
* 0 ≤ |E| ≤ 1,000
* si ≠ ti

Input

A directed graph G is given in the following format:


|V| |E|
s0 t0
s1 t1
:
s|E|-1 t|E|-1


|V| is the number of nodes and |E| is the number of edges in the graph. The graph nodes are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target nodes of i-th edge (directed).

Output

Print 1 if G has cycle(s), 0 otherwise.

Examples

Input

3 3
0 1
0 2
1 2


Output

0


Input

3 3
0 1
1 2
2 0


Output

1
```python
from collections import deque
from typing import List, Optional, Tuple


def cycle_detectable_topological_sort(
    graph: List[List[int]], in_degrees: List[int], first_index: int = 0
) -> Tuple[Optional[List[int]], Optional[List[int]]]:
    """Topological sort that uses Kahn's algorithm and detects a loop (DAG or not).
    Returns:
        if the given graph is DAG, a list of sorted vertices and a list of depths of
        each vertex is returned.
        Otherwise, (None, None) is returned.
    """
    V = len(graph) + first_index
    order = []
    depths = [-1] * V  # depths[i] := the length of the longest path to V_i
    for i in range(first_index, V):
        if not in_degrees[i]:
            order.append(i)
            depths[i] = 0

    queue = deque(order)
    while queue:
        u = queue.popleft()
        cur_depth = depths[u]
        for v in graph[u]:
            in_degrees[v] -= 1
            if not in_degrees[v]:
                depths[v] = max(depths[v], cur_depth + 1)
                queue.append(v), order.append(v)
    return (order, depths) if len(order) + first_index == V else (None, None)


def grl_4_a():
    # https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_A
    V, _, *ST = map(int, open(0).read().split())
    graph = [[] for _ in range(V)]
    in_degrees = [0] * V
    for s, t in zip(*[iter(ST)] * 2):
        graph[s].append(t)
        in_degrees[t] += 1

    res, _ = cycle_detectable_topological_sort(graph, in_degrees)
    print(1 if res is None else 0)


if __name__ == "__main__":
    grl_4_a()


```