没有环的连通无向图称为树。树是一类图表,不仅对人类来说很有趣,对蚂蚁来说也很有趣。
一只蚂蚁站在某棵树的根部。他看到树中有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