Дан ориентированный граф. Используя алгоритм Флойда определите, есть ли в заданном графе цикл.
Формат входных данных
В первой строке вводится число вершин N≤ 50. Далее в N строках следуют по N чисел, каждое из которых – 0 или 1. j-ое число в i-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из i-ой вершины в j-ую. Гарантируется, что на диагонали матрицы будут стоять нули.
Формат выходных данных
Выведите 0, если в заданном графе цикла нет, и 1, если он есть.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 1 0
0 0 1
0 0 0
|
0
|
|
2
|
3
0 1 0
0 0 1
1 0 0
|
1
|