Problems
Is there a cycle?
Is there a cycle?
The directed graph is given. Determine, does it contain a cycle.
Input data
First line contains number of vertices n~(n \le 50). Each of 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 data
Print 0 if there is no cycle in the graph and 1 if cycle exists.
Examples
Input example #1
3 0 1 1 0 0 1 0 0 0
Output example #1
0
Input example #2
5 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0
Output example #2
1