You are given an undirected tree with $$$n$$$ vertices rooted at $$$1$$$. Recall that a tree is a connected acyclic graph. You are also given a permutation $$$p$$$ of length $$$n$$$. A preorder traversal of a rooted tree with $$$n$$$ vertices is a permutation of length $$$n$$$ that can be generated by the following pseudo-code:
seq = list()
function preorder(u):
seq.append(u)
shuffle(children(u))
for v in children(u):
preorder(v)
preorder(1)
where seq is the generated preorder traversal. Note that there might be more than $$$1$$$ possible preorder traversals of a tree.
Among all possible preorder traversals, you need to find one such that the following sum is maximised: $$$$$$\sum_{i=1}^n \left[p_i=s_i \right]$$$$$$
where $$$s$$$ is the preorder traversal you have chosen. Informally, you need to find a preorder traversal $$$s$$$ such that it has the most number of matching positions with $$$p$$$.
If there are many possible solutions, you may output any of them.
The first line of each test contains a single integer $$$n$$$ ($$$1 \le n \le 18$$$) — the number of vertices in the given tree.
The second line contains $$$n$$$ distinct integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$) — the given permutation.
Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), indicating an edge between vertices $$$u$$$ and $$$v$$$.
It is guaranteed that the input forms a tree.
Output $$$n$$$ integers, representing the preorder traversal you found.
53 5 2 4 11 25 43 21 4
1 2 3 4 5
