ЯндексCodeRunCodeRun
Telegram-чатик

11. Поиск цикла

  • средняя
  • dfs

Дан неориентированный граф. Требуется определить, есть ли в нем цикл, и, если есть, вывести его.

Формат ввода

В первой строке дано одно число n — количество вершин в графе ( 1  $\le$ n $\le$  500 ). Далее в n строках задан сам граф матрицей смежности.

Формат вывода

Если в иcходном графе нет цикла, то выведите «NO». Иначе, в первой строке выведите «YES», во второй строке выведите число k — количество вершин в цикле, а в третьей строке выведите k различных чисел — номера вершин, которые принадлежат циклу в порядке обхода (обход можно начинать с любой вершины цикла). Если циклов несколько, то выведите любой.

Пример 1

Ввод
3
0 1 1
1 0 1
1 1 0
Вывод
YES
3
3 2 1

Пример 2

Ввод
4
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
Вывод
NO

Пример 3

Ввод
5
0 1 0 0 0
1 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
Вывод
YES
3
5 4 3