Is there a cycle?
Problem
Given a directed graph. You want to determine if it contains a cycle.
Input
The first line contains the number of vertices N≤ 50. Next, N lines are followed by N numbers, each of which – 0 or 1. The j-th number in the i-th row is equal to 1 if and only if there is an edge going from the i-th vertex to the j-th one. It is guaranteed that there will be zeros on the diagonal of the matrix.
Output
Print 0 if there is no cycle in the given graph, and 1 if there is one.
Examples
| # |
Input |
Output |
| 1 |
3
0 1 0
0 0 1
0 0 0
|
0 |
| 2 |
3
0 1 0
0 0 1
1 0 0
|
1 |