E. Найдите цикл
Дан ориентированный граф. Определите, есть ли в нём цикл, и если есть — выведите его.
Ответ единственный за счёт правила обхода: обход в глубину запускается из вершин по возрастанию номера, соседи перебираются по возрастанию, а выводится первый найденный цикл.
Цикл ищется цветами. Белая вершина — не посещали, серая — вошли и ещё не вышли, чёрная — вышли. Ребро в серую вершину и есть цикл: серые вершины лежат на текущем пути обхода, значит из неё есть путь обратно.
Ребро в чёрную вершину циклом не является — это либо прямое, либо перекрёстное ребро. Путать эти два случая — самая частая ошибка задачи; в неориентированном графе такого различия нет, и оттого оно неочевидно.
Сам цикл — это кусок текущего пути от найденной серой вершины до текущей.
Формат ввода
Первая строка содержит числа () и ().
Далее идут строк с рёбрами. Возможны кратные рёбра; петель нет.
Формат вывода
Если цикла нет — NO.
Иначе YES, во второй строке длина цикла , в третьей — номеров вершин в порядке обхода цикла.
Примеры
3 3 1 2 2 3 3 1
YES 3 1 2 3
3 2 1 2 1 3
NO