Problems
Голосование
Голосование
В Байтляндии было решено провести голосование. Чтобы проголосовать человеку нужно подъехать в ближайший пункт голосования. Жители Байтляндии ленивы. Если путешествие от того места, где они живут, до пункта голосования занимает больше одного дня, на голосование они не пойдут. Байтляндия имеет вид неориентированного графа. Время путешествия по каждой из дорог - ровно один день. Вдоль каждой дороги страны живут люди (равномерно по дороге и очень густо). Пункты голосования можно строить только в вершинах. Соответственно, чтобы все проголосовали (т.е. пошли на голосование), нужно, чтобы у каждого ребра в одном из двух концов был пункт голосования.
Необходимо помочь правителю страны сэкономить деньги и выбрать минимальное по размеру множество вершин, в которых нужно соорудить пункты голосования.
\InputFile
На первой строке числа \textbf{N} и \textbf{M} - количество вершин и ребер графа соответственно (\textbf{1} ≤ \textbf{N} ≤ \textbf{50000}, \textbf{1} ≤ \textbf{M} ≤ \textbf{100000}). Следующие \textbf{M} строк содержат по \textbf{2} числа - \textbf{a} и \textbf{b} (\textbf{1} ≤ \textbf{a}, \textbf{b}, ≤ \textbf{N}, \textbf{a} ≠ \textbf{b}), что означает, что между городами \textbf{a} и \textbf{b} есть дорога.
\OutputFile
Выходной файл должен состоять из двух строк - число вершин \textbf{k} на первой строке и \textbf{k} чисел от \textbf{1} до \textbf{n} на второй.
\Note
На реальном контесте оцивание происходило так:
\begin{enumerate}
\item Вы могли скачать входные тесты.
\item Оценивались выходные тесты, а не программа.
\item Если ваши \textbf{k} вершин не покрывают все \textbf{m} ребер, вы получите \textbf{0} баллов за тест. Если же ответ корректен, число баллов зависит от размера выбранного вами множества. Пусть ваш ответ = \textbf{y}, а оптимальный = \textbf{b}. Тогда вы заработаете \textbf{10·((8b-7y)/b)^2} баллов (округленное к ближайшему целому).
\end{enumerate}
Мы решились пойти на эксперимент и на свой страх и риск оценить именно Вашу программу.
\includegraphics{https://static.e-olymp.com/content/00/0093d56e427e0063d34bfc00c31387bdad60ff9e.jpg}
Input example #1
4 4 1 2 2 3 3 1 1 4
Output example #1
2 1 3