Determine whether every vertex of a directed graph can reach every other vertex.

Input

The first line contains n and m. The next m lines contain directed edges.

• 1 <= n <= 1000

Output

Print 1 if the graph is strongly connected; otherwise, print 0.

Example

Input

4 5
1 2
2 3
3 1
3 4
4 3

Output

1