Дерево — это связный неориентированный граф без циклов. Деревья представляют собой широкий класс графов, интересный не только людям, но и муравьям.
В корне одного дерева стоит муравей. Он видит, что в дереве n вершин, и они соединены n - 1 ребрами так, что от любой вершины можно дойти до любой другой. Лист в дереве — это отличная от корня вершина, которая соединена ровно с одной другой вершиной.
Муравей хочет обойти все вершины дерева и вернуться назад к корню, пройдя по каждому ребру ровно два раза. При этом он хочет обойти все листья в заданном порядке. Ваша задача найти любой возможный путь муравья.
Выходные данные
Если искомого порядка обхода всех n вершин не существует, выведите -1. Иначе выведите 2n - 1 чисел — сам обход. Каждый раз, когда муравей приходит в вершину, выводите номер этой вершины.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
2 3
3
|
1 2 3 2 1
|
|
2
|
6
1 2
1 3
2 4
4 5
4 6
5 6 3
|
1 2 4 5 4 6 4 2 1 3 1
|
|
3
|
6
1 2
1 3
2 4
4 5
4 6
5 3 6
|
-1
|