# Is there a cycle?

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

The directed graph is given. Determine, does it contain a cycle.

## Input

First line contains number of vertices $n(n≤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

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

## Examples

Input #1

Answer #1

Input #2

Answer #2

Submissions 10K

Acceptance rate 34%