Дан неориентированный граф без петель и кратных ребер. Напишите программу, которая проверит, верно ли, что этот граф представляет собой один простой цикл (простой цикл - это цикл без самопересечений), проходящий через все вершины этого графа, и не содержит никаких ребер, не входящих в этот цикл.
Входные данные
Вводится число N - количество вершин исхоного графа (2≤N≤100). Далее идет
матрица смежности исходного графа - матрица размером N*N, где число в позиции
i,j описывает ребро между вершинами i и j: 1 обозначает наличие ребра, 0 - отсутствие.
Выходные данные
Выведите сообщение YES, если граф является простым циклом, и NO иначе.
| Пример ввода | Пример вывода | Комментарий |
4 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 |
YES |
Цикл проходит через вершины 1, 2, 4, 3, 1... |
4 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 |
NO |
В графе помимо цикла есть лишнее ребро из 2 в 3 |
4 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 |
NO |
В графе есть простой цикл, но он не проходит через вершину 4 |