Маршрут для гонца
(Время: 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.TXT | OUTPUT.TXT |
1 | 4
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 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|