29367번 - Пёсик 스페셜 저지다국어

Пёсик, принадлежащий Аликс, как и все песики, любит играть с мячиком. Но в этот раз вместо мячика ему попалась конструкция из металлических звеньев. Каждое звено в ней может быть соединено с некоторыми другими звеньями. Пёсику срочно необходимо с ней поиграть! Для этого Пёсику необходимо удалить несколько звеньев (возможно, ноль) и разорвать несколько (также, возможно, ноль) связей между звеньями, чтобы в итоге получилась замкнутая цепь из звеньев, в которой каждое звено соединено только с двумя соседними. Каждое звено в такой цепи должно быть использовано ровно один раз.

Пёсик хочет, чтобы получившаяся цепь была как можно длиннее. К счастью, изначальная конструкция такова, что вариантов сделать замкнутую цепь у него немного, а именно, не более трех. Помогите Пёсику!

В первой строке входного файла находятся два целых числа $n$ и $m$ ($1 \le n \le 200{\,}000$, $1 \le m \le 500{\,}000$) --- количество звеньев и соединений между ними соответственно. В следующих $m$ строках находятся описания соединений: в каждой строке находится по два числа $u$ и $v$ ($1 \le u, v \le n$), означающие, что звенья с номерами $u$ и $v$ соединены между собой. Никакое звено не соединено с собой, и никакие два звена не соединены более одного раза. Гарантируется, что из данной конструкции можно получить хотя бы одну замкнутую цепь. Также гарантируется, что имеется не более трех вариантов удаления соединений и звеньев, после применения которых остается замкнутая цепь из звеньев. Исходная конструкция является связной.

В первой строке выходного файла выведите число $k$: длину максимальной замкнутой цепи, которую может получить Пёсик. В следующей строке выведите $k$ чисел $a_1, a_2, \dots, a_k$ --- номера звеньев в этой цепи. Все $a_i$ должны быть различны, и звенья с номерами $a_1$ и $a_2$, $a_2$ и $a_3$, $\dots$, $a_{k-1}$ и $a_k$, а также $a_k$ и $a_1$ должны быть соединены в изначальной конструкции.