ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1389. Дорожные работы

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В некотором государстве король подсчитал собранные налоги и решил пустить их на ремонт дорог. Всего в том королевстве было N городов, которые соединялись M двусторонними дорогами таким образом, что из любого города можно было проехать в любой другой. Дорожная сеть находилась в катастрофическом состоянии, поэтому король решил, пока еще собранные деньги не обесценились, починить за лето как можно большее количество дорог. Жители королевства возмутились тем, что все пути, которыми они пользовались ежедневно, будут закрыты на лето. Поэтому королю пришлось пойти на уступки, пообещав, что для любого города будет закрыто на ремонт не более одной дороги, выходящей из него. Помогите королю выполнить свой план, не вызвав недовольства со стороны жителей.

Исходные данные

В первой строке расположены через пробел два целых числа: N и M (2 ≤ N ≤ 105, M = N − 1). В следующих M строках описываются дороги королевства в виде пар (ai, bi) — номеров городов, соединяемых очередной дорогой (1 ≤ ai, biN).

Результат

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

Пример

исходные данныерезультат
4 3
1 2
2 3
3 4
2
1 2
3 4
Автор задачи: Дмитрий Иванков & Александр Ипатов
Источник задачи: Petrozavodsk summer training camp, August 2005.