D. Муравей на дереве
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Дерево — это связный неориентированный граф без циклов. Деревья представляют собой широкий класс графов, интересный не только людям, но и муравьям.

В корне одного дерева стоит муравей. Он видит, что в дереве n вершин, и они соединены n - 1 ребрами так, что от любой вершины можно дойти до любой другой. Лист в дереве — это отличная от корня вершина, которая соединена ровно с одной другой вершиной.

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

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

В первой строке записано целое число n (3 ≤ n ≤ 300) — количество вершин в дереве. Далее следует n - 1 строк — описания ребер. Каждое ребро описывается двумя числами — номерами вершин, которые оно соединяет. По каждому ребру можно идти в любом направлении. Вершины нумеруются с 1. Корень дерева имеет номер 1.

На следующей строке задан порядок обхода всех листьев дерева — k целых чисел, где k — количество листьев в дереве. Гарантируется, что этот порядок обхода содержит все листья дерева и только их ровно один раз.

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

Если искомого порядка обхода всех n вершин не существует, выведите -1. Иначе выведите 2n - 1 чисел — сам обход. Каждый раз, когда муравей приходит в вершину, выводите номер этой вершины.

Примеры
Входные данные
3
1 2
2 3
3
Выходные данные
1 2 3 2 1
Входные данные
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
Входные данные
6
1 2
1 3
2 4
4 5
4 6
5 3 6
Выходные данные
-1