eolymp
bolt
Try our new interface for solving problems
Problems

Is there a cycle?

Is there a cycle?

Time limit 1 second
Memory limit 128 MiB

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