← 返回题目列表

Codeforces · 29/D

D. 树上的蚂蚁

中文机器翻译题面 查看原题

没有环的连通无向图称为树。树是一类图表,不仅对人类来说很有趣,对蚂蚁来说也很有趣。

一只蚂蚁站在某棵树的根部。他看到树中有n个顶点,它们由n-1条边连接,因此任何一对顶点之间都有一条路径。叶子与根顶点不同,根顶点恰好与另一个顶点相连。

蚂蚁想要访问树中的每个顶点并返回到根,通过每条边两次。此外,他还想按照特定的顺序访问树叶。你要找到蚂蚁的一些可能的路线。

输入

第一行包含整数 n (3 ≤ n ≤ 300) — 树中的顶点数量。接下来的 n - 1 行描述边缘。每条边都用两个整数来描述——它所连接的顶点的索引。每条边都可以在任何方向上通过。顶点从 1 开始编号。树的根编号为 1。最后一行包含 k 个整数,其中 k 是树中叶子的数量。这些数字描述了访问叶子的顺序。保证每个叶子节点按此顺序恰好出现一次。

输出

如果所需路由不存在,则输出-1。否则,输出 2n - 1 个数字,描述路线。每当蚂蚁到达一个顶点时,输出它的索引。

示例

输入 #1

3
1 2
2 3
3

输出 #1

1 2 3 2 1

输入 #2

6
1 2
1 3
2 4
4 5
4 6
5 6 3

输出 #2

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

输出 #3

-1