Interview : How to traverse tree meeting two requirements below

Question

Recently, I'm asked to write a program to solve a problem below.
Describe

Given a tree, two requirements,

1. Traverse all nodes starting from root node. In the same time, you should guarantee every edge has been visited twice.
2. Especially, leaf nodes should be visited as the order given.

Input

• first line: integer K, represents number of nodes, K >= 1 && K <= 300
• K-1 lines: each line contains two integers, represents an edge(Node ID is 1, 2, 3 .., 1 represents ID of root node).
• last line: All the leaf nodes in order(leaf nodes should be visited in this order).

Output

If you can traverse the tree meeting two requirements above, outputs that node sequence. Otherwise, outputs -1

Two samples:

Input 1:
3
1 2
2 3
3
output is:
1 2 3 2 1

Input 2:
6
1 2
1 3
2 4
4 5
4 6
5 3 6
output is:
-1

Answer 1

Start by building a digraph.

Detecting whether it has cycles is a well-known problem. Return -1 if it has cycles. The remainder assumes there aren't.

Perform now an in-order traversal of the tree recursively, assigning order pairs, from the leaves to the root, to the nodes as follows.

1. For a leaf node, say its order in the input is o. It's order pair is (o, o).

2. For a non-leaf node, Check if there is an overlap between the order pairs of its children (say that one child has an order pair (1, 20), and another has an order pair (3, 4)). If there is an overlap, output -1. Otherwise, sort the children by the second item of their order pairs. If the order pairs of the children are (s1, e1), (s2, e2), ..., (sm, em), then the order pair of the node is (s1, em).

Finally, run again an in-order walk, this time by the order of the children. This traversal is the answer to the question.