Description

给定 $n$ 个球，第 $i$ 个球的值为 $p_i$。保证 $p_1,p_2,\dots,p_n$ 是 $1,2,3\dots,n$ 的一个排列。

有一棵有根树，包含 $n$ 个顶点，每个顶点是一个洞，每个洞只能容纳一个球。

树的根是第一个顶点。

现在你需要用这些球填满洞。

你需要按 $1$ 到 $n$ 的顺序依次投掷每个球，步骤如下：

1. 将球投到顶点 $1$。
2. 设球所在的顶点为 $p$。
3. 如果第 $p$ 个顶点已经被其他球填满，你需要选择一个顶点 $x$，将球投到第 $x$ 个顶点，然后返回步骤 $2$。你需要保证第 $x$ 个顶点是第 $p$ 个顶点的子节点，并且第 $x$ 个顶点的子树中至少有一个顶点未被填满。
4. 否则，球将填满第 $p$ 个顶点。

投完所有球后，用 $a_i$ 表示第 $i$ 个顶点中球的值。

你需要找到 $\{a_n\}$ 的最小字典序。

我们定义 $dep_i$ 为从第 $i$ 个顶点到树根（第一个顶点）的路径上的顶点数。

特别地，对于任意两个顶点 $x<y$，保证 $dep_x\le dep_y$。

Input Format

第一行包含一个整数 $n(1\le n\le 5\times 10^5)$，表示这棵树的顶点数。

接下来一行包含 $n$ 个数字，第 $i$ 个数字是 $p_i(1\le p_i\le n)$。保证 $p_1,p_2,\dots,p_n$ 是 $1,2,3\dots,n$ 的一个排列。

接下来的 $n-1$ 行描述了树的边。第 $i$ 行包含两个整数 $u_i$ 和 $v_i(1\le u_i,v_i\le n)$，表示第 $i$ 条边连接的顶点编号。

保证给定的边构成一棵树。

并且对于任意顶点 $x<y$，保证 $dep_x\le dep_y$。

Output Format

输出 $n$ 个整数，表示 $\{a_n\}$ 的最小字典序。

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

3 1 5 4 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

9 2 1 3 6 4 8 5 7

Hint

（由 ChatGPT 4o 翻译）