题目翻译:
连通且无环的无向图称为树。树这类图不仅对人类来说很有趣,对蚂蚁来说也是如此。
一只蚂蚁站在某棵树的根节点上。它看到这棵树有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