Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Дороги - 2

(Время: 1 сек. Память: 16 Мб Сложность: 53%)

Мэр города Гадюкино решил проверить состояние дорог после только что проведенного капитального ремонта. Для этого он хочет проехать по каждой дороге в обоих направлениях. Помогите мэру составить кратчайший маршрут, проходящий по каждой дороге в каждом направлении хотя бы один раз.

В городе Гадюкино n перекрестков и m дорог, каждая из которых соединяет два различных перекрестка. Между двумя перекрестками может быть не более одной дороги. Известно, что по дорогам от каждого перекрестка можно доехать до любого другого.

Входные данные

Входной файл INPUT.TXT содержит целые числа n и m (1 ≤ n ≤ 104, 1 ≤ m ≤ 105), и далее m пар целых чисел ai и bi - номера перекрестков, которые соединяет i-я дорога.

Выходные данные

В выходной файл OUTPUT.TXT выведите число s - минимальную длину пути и далее s+1 число - номера перекрестков в том порядке, в котором их нужно проезжать.

Пример

INPUT.TXTOUTPUT.TXT
13 3
1 2
2 3
1 3
6
1 2 3 1 3 2 1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483