Чи є цикл?

Задано орієентовний граф. Визначіть, чи містить він цикл.

Вхідні дані

Перший рядок містить кількість вершин $n(n\le 50)$. Далі у $n$ рядках йде по $n$ чисел, кожне з яких дорывнює $0$ або $1$. $j$-те число в $i$-му рядку дорівнює $1$ тоді і лише тоді, коли існує ребро, яке йде з $i$-ї вершини у $j$-ту. Гарантується, що на діагоналі матриці будуть стояти нулі.

Вихідні дані

Виведіть $0$, якщо у заданому графі циклу немає, і $1$, якщо він є.

Приклади