Я нашёл Принцессу в подвале таверны, как и ожидал. После того, как она сделала ставки на турнир, мы поднялись наверх пропустить по стаканчику виски. Я надеялся выведать информацию о Драконе, ведь Принцесса в своё время частенько заходила к нему на Чай.
Принцесса была непростой женщиной, и иметь с ней дело было крайне опасно. Как-то она по очереди встречалась с принцами, стараясь ради забавы перессорить их всех. Если Принцесса уходила от одного принца и начинала сразу же встречаться с его другом, то после этого они переставали быть друзьями. Со стороны было заметно, что она делает это специально: она перессорила всех друзей за минимальное количество переходов.
Под звуки голоса Принцессы я чувствовал, как тьма из углов таверны расползается и покрывает всё вокруг. Чувство реальности покидало меня. Не надо быть Добрым Волшебником, чтобы догадаться, что она подсыпала что-то мне в стакан. Пламя жизни внутри меня угасало, я провалился во тьму. Как ловко она перессорила тех принцев. Как же она это сделала? Никогда не пейте виски с Принцессой.
В первой строке записаны два целых числа через пробел: n и m (2 ≤ n ≤ 105, 1 ≤ m ≤ 2·105) — количество принцев и количество пар друзей среди них соответственно.
Далее в m строках через пробел записаны пары целых чисел ai и bi (1 ≤ ai < bi ≤ n) — пары номеров принцев, являющихся друзьями. Принцы нумеруются с единицы. Каждая пара представлена не более одного раза.
В первой строке выведите единственное целое число k — минимальное количество принцев, с которыми должна последовательно встречаться Принцесса, чтобы перессорить всех друзей.
Во второй строке выведите k целых чисел через пробел — номера принцев в том порядке, в котором Принцесса должна с ними встречаться. Если ответов несколько, выведите любой из них.
9 5
2 4
2 6
3 5
3 9
5 9
7
3 9 5 3 6 2 4
4 5
1 2
1 3
1 4
2 4
3 4
6
4 3 1 4 2 1
