e-olymp
Competitions

ADA Classes - November 20

Is there a cycle?

Oriented graph is given. Determine, does it contain a cycle.

Input

First line contains number of vertices n (n50). Each if the next n lines contains n numbers, each of them is either "0" or "1". j-th number in the i-th line equals to "1" if and only if there exist an edge from i-th vertex to j-th. It is guaranteed that diagonal of the matrix contains zeros.

Output

Print "0" if there is no cycle in the graph and "1" if cycle exists.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
0 1 0
0 0 1
0 0 0
Output example #1
0