Голосування

У Байтляндії було вирішено провести голосування. Щоб проголосувати людині потрібно під'їхати у найближчий пункт голосування. Жителі Байтляндії ліниві. Якщо подорож від того місця, де вони живуть, до пункта голосування заємає більше одного дня, на голосування вони не підуть. Байтляндія має вигляд неорієнтовного графа. Час подорожі по кожній з доріг - рівно один день. Вздовж кожної дороги країни живуть люди (рівномірно по дорозі і дуже густо). Пункти голосування можна будувати лише у вершинах. Відповідно, щоб усі проголосували (тобто пішли на голосування), потрібно, щоб у кожного ребра у одному з двох кінців був пункт голосування.

Необхідно допомогти правителю країни зекономити гроші і вибрати мінімальну за розміром множину вершин, у яких потрібно спорудити пункти голосування.

Вхідні дані

У першому рядку числа N та M - кількість вершин та ребер графа відповідно (1 ≤ N ≤ 50000, 1 ≤ M ≤ 100000). Наступні M рядків містять по 2 числа - a та b (1 ≤ a, b, ≤ N, a ≠ b), що означає, що між містами a та b є дорога.

Вихідні дані

Вихідний файл повинен складатись з двох рядків - число вершин k у першому рядку та k чисел від 1 до n у другому.

Примітка

На реальному контесті оцінювання відбувалось так:

1. Ви могли скачати вхідні тести.

2. Оцінювались вихідні тести, а не програма.

3. Якщо ваші k вершин не покривають усі m ребер, ви отримаєте 0 балів за тест. Якщо ж відповідь коректна, число балів залежить від розміру вибраної вами множини. Нехай ваша відповідь = y, а оптимальна = b. Тоді ви зарабите 10·((8b-7y)/b)^2 балів (округлені до найближчого цілого).

Ми ризикнули піти на експеримент і на свій страх та ризик оцінити саме Вашу програму.

Приклади