Школа программиста
Резервная копия - VPS Hoster 

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

HotLog


 

Маршрут для гонца

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

В королевстве N городов, пронумерованных от 1 до N. Столица имеет номер 1. Каждый город окружен городской стеной с 4 воротами. Ворота пронумерованы следующим образом: ворота i-го города (1 ≤ i ≤ N) имеют номера 4i−3, 4i−2, 4i−1, 4i. Через каждые ворота проходит ровно 1 дорога, которая ведет до некоторых ворот другого города (заметьте, что может существовать несколько дорог между двумя городами). По всем дорогам можно двигаться в обоих направлениях. Благодаря системе туннелей и мостов дороги не пересекаются вне городов.

Королевский гонец должен развесить копии Очень важного Королевского Указа на внешней стороне всех ворот каждого города. Гонец может свободно передвигаться от одних ворот к другим в пределах города, но вне города он может двигаться только по дорогам. Гонец выезжает из столицы и должен туда вернуться после выполнения задания.

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

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

Первая строка входного файла INPUT.TXT содержит целое число N (2 ≤ N ≤ 1000). Каждая из последующих 2N строк описывает одну дорогу и содержит 2 целых числа, разделенных пробелом: номера ворот, соединенных дорогой.

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

В первой строке выходного файла OUTPUT.TXT выведите «Yes», если поручение гонца может быть выполнено, и «No» в противном случае. В случае если это возможно, вторая строка выходного файла должна содержать 4N целых чисел: номера ворот в порядке прохождения через них гонцом. Если существует несколько решений, выведите любое из них.

Пример

INPUT.TXTOUTPUT.TXT
14
1 9
2 10
3 13
4 8
5 11
6 14
7 16
15 12
Yes
3 13 14 6 7 16 15 12 9 1 2 10 11 5 8 4

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Алгоритм Флойда
 Алгоритм Форда-Беллмана
 Алгоритм Дейкстры
 Минимальный каркас
 Эйлеров цикл, конденсация
 Паросочетания
 A. Ковбои
 B. Маршрут для гонца
 C. Конденсация графа
 D. Манхэттенский полицейский

Красноярский краевой Дворец пионеров, (c)2006 - 2022, ICQ: 151483, E-mail: admin@acmp.ru



Как выбрать обеденный стол