Изначально компьютерная сеть некоторой организации имела вид дерева, то
есть от любого устройства сети до любого другого существовал единственный путь
передачи данных. Для улучшения работы сети и повышения её надёжности было
решено дополнительно соединить между собой те пары устройств, которые ещё не
соединены напрямую, но расположены друг от друга достаточно близко. Термин
"достаточно близко" определяется так: если кратчайший путь между
двумя устройствами A и B проходит не более чем через два
промежуточных устройства, то они считаются близкими (реальную длину кабелей
учитывать не стали, поскольку она ограничена некоторой константой в силу
физических причин). Пример исходной сети и сети после модернизации показан на
рисунке:
Получив сеть такой слегка странной топологии, было решено исследовать
её свойства. Одним из возникших вопросов был следующий: можно ли в данной сети
организовать передачу по кольцу, т.е. существует ли такой путь, по которому
пакет с данными проходит через все устройства сети по одному разу и
возвращается в устройство-отправитель (т.е. существует ли в сети гамильтонов
цикл).
Дана исходная структура
сети, требуется определить, найдётся ли в этой сети после модернизации
гамильтонов цикл, и если найдётся, то вывести один из них.
В первой строке входного файл находится
число N — количество вершин
дерева (3 <= N <= 100). Следующая N – 1 строка описывает рёбра дерева. В
каждой строке содержатся два числа, ui
и vi (от 1 до N) — номера вершин, соединённых данным
ребром.
В первой строке выходного файла выведите
слово "YES", если гамильтонов цикл существует,
или "NO" в противном случае. Если цикл существует, то
выведите его в следующей строке как N +
1 номер вершин (в порядке прохождения цикла), разделённых пробелами (первая
вершина должна совпадать с последней). Если решений несколько, выведите любое
из них.
Пример
|
STDIN
|
STDOUT
|
|
6
1 2
3 2
2 4
4 5
5 6
|
YES
3 5 4 6 2 1 3
|
