Problem Description

You are given $n$ balls, where the $i$-th ball's value is $p_i$. It is guaranteed that $p_1, p_2, \dots, p_n$ is a permutation of $1, 2, 3, \dots, n$.

There is also a rooted tree with $n$ vertices, each representing a hole, and each hole can hold only one ball.

The root of the tree is the first vertex.

Now you need to fill the holes with the balls. You need to throw each ball in order from $1$ to $n$ following these steps:

1. Throw the ball into vertex $1$.
2. Let the vertex where the ball is be $p$.
3. If the $p$-th vertex has already been filled with another ball, you need to choose a vertex $x$ and throw the ball into the $x$-th vertex, then return to step $2$. You must ensure that the $x$-th vertex is a child of the $p$-th vertex and at least one vertex in the subtree of the $x$-th vertex is not filled.
4. Otherwise, the ball will fill the $p$-th vertex.

After throwing all the balls, let $a_i$ represent the value of the ball in the $i$-th vertex.

You need to find the minimum lexicographical order of $\{a_n\}$.

We define $dep_i$ as the number of vertices on the path from the $i$-th vertex to the tree's root (the first vertex).

Specially, for any two vertices $x < y$, it is guaranteed that $dep_x \le dep_y$.

Input Format

The first line contains a single integer $n (1 \le n \le 5 \times 10^5)$ - the number of vertices in the tree.

The next line contains $n$ numbers, where the $i$-th number is $p_i (1 \le p_i \le n)$. It is guaranteed that $p_1, p_2, \dots, p_n$ is a permutation of $1, 2, 3, \dots, n$.

The next $n-1$ lines describe the tree's edges. The $i$-th of these lines contains two integers $u_i$ and $v_i (1 \le u_i, v_i \le n)$ - the numbers of vertices connected by the $i$-th edge.

It is guaranteed that the given edges form a tree.

And for any vertices $x < y$, it is guaranteed that $dep_x \le dep_y$.

Output Format

Output $n$ integers, the minimum lexicographical order of $\{a_n\}$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3 1 5 4 2

Sample Input #2

9
9 2 6 3 5 7 1 4 8
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9

Sample Output #2

9 2 1 3 6 4 8 5 7

见题面 Input 部分

见题面 Output 部分