Дан ориентированный невзвешенный связный граф. Требуется определить, содержит ли он циклы.
Входные данные: Первая строка содержит одно натуральное число n — количество вершин (0 ≤ n ≤ 1 111).
Следующие n строк содержат матрицу смежности графа. Если в позиции (i, j) квадратной матрицы стоит единичка, то i-ый и j-ый ребра соединены ребрами, а если нолик, то не соединены. При этом ребро направленно из i-ого в j-ое ребро графа, и j-ое и i-ое ребро не соеденены ребрами.
Выходные данные: Первая строка должна содержать YES, если граф содержит цикл и NO — в противном случае.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8
0 1 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
|
YES |