Задача z8. Force Choke Optimizer ≡

Условие

Гранд-мофф Таркин получил приказ от Императора установить тотальный контроль над гиперпространственными маршрутами в Внешнем Кольце. Разведка донесла, что повстанцы активно используют сеть из N планет, соединённых M гиперпространственными маршрутами, для переброски оружия и диверсантов.

Для перехвата транспортов необходимо разместить на планетах имперские гарнизоны с гравитационными колодцами — устройствами, способными выдёргивать корабли из гиперпространства. Маршрут считается под контролем, если хотя бы на одном из его концов размещён гарнизон.

Гравитационный колодец

Бюджет операции ограничен: Звезда Смерти требует колоссальных ресурсов. Однако Дарт Вейдер лично прибудет с инспекцией через неделю. Если лорд ситхов обнаружит, что количество гарнизонов превышает теоретический минимум (минимальное количество гарнизонов, перекрывающих все маршруты) более чем в два раза, Таркина ждёт Force choke и немедленная отставка.

Помогите Таркину рассчитать количество и дислокацию гарнизонов так, чтобы все маршруты оказались под наблюдением, а риск удушения Силой стремился к нулю.

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

В первой строке входных данных подаются два целых числа: N — количество планет в секторе (1 ≤ N ≤ 10⁵) и M — количество гиперпространственных маршрутов между ними (0 ≤ M ≤ 2 ⋅ 10⁵).

В следующих M строках содержится описание маршрутов. Каждая строка содержит два целых числа u и v (1 ≤ u, v ≤ N, u ≠ v) — номера планет, соединённых маршрутом. Между двумя планетами может быть не более одного маршрута.

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

В первой строке выведите K — количество размещённых гарнизонов. Во второй строке через пробел выведите K различных целых чисел — номера планет, на которых Таркину необходимо разместить имперские гарнизоны. Если существует несколько вариантов дислокации, выведите любой из них.

Примеры тестов

4 3
2 3
1 2
3 4

2
2 3

5 4
1 2
1 3
1 4
1 5

1
1