Задача №1704. Маршрут для гонца
В королевстве \(N\); городов, пронумерованных от 1 до \(N\). Столица имеет номер 1. Каждый город окружен городской стеной с 4 воротами. Ворота пронумерованы следующим образом: ворота \(i\)-го города (1 \(\le\) \(i\) \(\le\) \(N\)) имеют номера 4\(i\)−3, 4\(i\)−2, 4\(i\)−1, 4\(i\). Через каждые ворота проходит ровно 1 дорога, которая ведет до некоторых ворот другого города (заметьте, что может существовать несколько дорог между двумя городами). По всем дорогам можно двигаться в обоих направлениях. Благодаря системе туннелей и мостов дороги не пересекаются вне городов.
Королевский гонец должен развесить копии Очень важного Королевского Указа на внешней стороне всех ворот каждого города. Гонец может свободно передвигаться от одних ворот к другим в пределах города, но вне города он может двигаться только по дорогам. Гонец выезжает из столицы и должен туда вернуться после выполнения задания.
Может ли гонец выполнить поручение, проходя через каждые ворота только один раз? Выход из города через ворота только для того, чтобы вывесить на их внешней стороне указ, а затем немедленное возвращение в город, считается за один проход через ворота.
Первая строка входного файла содержит целое число \(N\) (2 \(\le\) \(N\) \(\le\) 1000). Каждая из последующих 2\(N\) строк описывает одну дорогу и содержит 2 целых числа, разделенных пробелом: номера ворот, соединенных дорогой.
В первую строку выходного файла выведите Yes или No в зависимости от того, может ли поручение гонца быть выполнено, если проходить через ворота только один раз. В случае если это возможно, вторая строка выходного файла должна содержать 4\(N\) целых чисел, разделенных пробелом: номера ворот в порядке прохождения через них гонцом. Если существует несколько решений, выведите любое из них.