EduBrick

E. Найдите цикл

3000 мс · 256 МБ · всё или ничего

Дан ориентированный граф. Определите, есть ли в нём цикл, и если есть — выведите его.

Ответ единственный за счёт правила обхода: обход в глубину запускается из вершин по возрастанию номера, соседи перебираются по возрастанию, а выводится первый найденный цикл.

Цикл ищется цветами. Белая вершина — не посещали, серая — вошли и ещё не вышли, чёрная — вышли. Ребро в серую вершину и есть цикл: серые вершины лежат на текущем пути обхода, значит из неё есть путь обратно.

Ребро в чёрную вершину циклом не является — это либо прямое, либо перекрёстное ребро. Путать эти два случая — самая частая ошибка задачи; в неориентированном графе такого различия нет, и оттого оно неочевидно.

Сам цикл — это кусок текущего пути от найденной серой вершины до текущей.

Формат ввода

Первая строка содержит числа nn (1≤n≤1051 \le n \le 10^5) и mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5).

Далее идут mm строк с рёбрами. Возможны кратные рёбра; петель нет.

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

Если цикла нет — NO.

Иначе YES, во второй строке длина цикла kk, в третьей — kk номеров вершин в порядке обхода цикла.

Примеры

ввод
3 3
1 2
2 3
3 1
вывод
YES
3
1 2 3
ввод
3 2
1 2
1 3
вывод
NO
Войдите, чтобы отправлять решения.