Competitions

# Depth First Search

# Is there a cycle?

Oriented 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.

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