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

Чемпионат Урала 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Из истории банка Гринготтс

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Гоблинский банк "Гринготтс" по праву считается одним из самых надёжных банков в мире волшебников. Он находится в сотнях километров под Лондоном, и охраняется мощными заклинаниями и драконами. А знаете ли вы, как был построен этот банк? Гоблины ведь не такие дураки, как гномы — они не станут копать многокилометровые подземные ходы киркой и лопатой. Как они проложили все туннели без лопат и кирок? Очень просто: чтобы прорыть туннель, гоблины с помощью магии вызывали гипервяка. Гипервяк — это нечто вроде большущей змеи мощностью более тысячи мегачервей. Двигаясь, он поедает всё, что находится на его пути, оставляя за собой удобный, ровный и прочный коридор. Гипервяком легко управлять с помощью магии, заставляя его рыть туннели в нужном направлении.
А знаете ли вы, почему гномы и другие подземные создания не используют гипервяков? Потому, что гипервяки вообще не могут двигаться, не поедая землю или камни. Значит, если гипервяк докопал туннель до нужного вам места, и новые туннели из этого места не нужны, то единственный способ остановить гипервяка — это, … хм…, скажем так, дематериализовать бедную зверушку. Что конечно, строжайше запрещено, ведь эти создания внесены в оранжевую книгу редких магических существ, и за каждого положено платить большой штраф. Просто под землей, где никто не видит, гоблины не очень заботятся о законности. Зато они заботятся о надежности банка, поэтому никогда не копают больше одного туннеля между двумя комнатами. И уж конечно, гоблинам и в голову не придет копать туннель, не соединяющий две разные комнаты.
К сожалению, министру магии попала в руки полная схема туннелей между помещениями банка. Он хочет потребовать штраф за каждый прорытый туннель. Гоблины, конечно, могут заявить, что если два туннеля приходят в одну комнату, то они обошлись всего одним гипервяком для прокладывания обоих туннелей, проведя гипервяка по краю комнаты. И вообще, для любой цепочки туннелей, где конечная комната очередного туннеля совпадает с начальной комнатой следующего, хватит одного гипервяка. Но, разумеется, никто не поверит, что гоблины перетаскивали гипервяка из одного помещения в другое, а расширять существующие туннели они не могли из соображений безопасности.
Помогите гоблинам представить министру магии такой план рытья туннелей, при котором погибло бы минимальное количество гипервяков.

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

В первой стоке входа находятся числа N и M (2 ≤ N ≤ 20000; 1 ≤ M ≤ 20000) — количество помещений банка и туннелей между помещениями. В следующих M строках указаны пары чисел (каждое число от 1 до N) — номера помещений, которые соединяет очередной туннель. От каждого помещения банка можно добраться до другого, пользуясь только прогрызенными гипервяками туннелями.

Результат

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

Пример

исходные данныерезультат
7 7
1 2
4 1
6 7
5 7
7 4
2 3
4 2
3
5 7 4 2 1 4
2 3
6 7
Автор задачи: Идея — Магаз Асанов, текст — Станислав Васильев, подготовил — Павел Зуев
Источник задачи: X командный Чемпионат Урала по спортивному программированию, 24-25 марта 2006 года
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1441. Из истории банка Гринготтс