lizhous 爱玩第五人格。

lizhous 爱玩囚徒。

lizhous 爱玩随笔浮想。

lizhous 做了一张地图。

lizhous 喜欢囚徒的连接电机的机制。所以他发明了一个更加强大的传输链。

在这张地图中有 $n$ 台密码机。共有 $n-1$ 条无向传输链，第 $i$ 条传输链连接两台密码机 $u_i,v_i$。任意两台密码机可以通过若干条传输链相互到达。

初始每台密码机都有破译进度 $c_i$ 。保证 $c$ 是一个 $1\sim n$ 的排列。

接下来每个时刻都会进行破译进度的 传输 ：

• 对于每台密码机，其破译进度会变成与其有传输链直接相连的密码机和自己的破译进度的最大值。

• 每个时刻，所有密码机的 传输 同时进行。

由于 lizhous 喜欢修机，所以他总会找到一个破译进度最少的密码机进行破译。

对于时刻 $t=1\sim n$，你需要帮助 lizhous 求出当前时刻破译进度最少的密码机的破译进度是多少。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $T$，表示测试用例的组数。

对于每组测试用例，第一行包含一个整数 $n$，表示地图中的密码机数量。

第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$，表示每个密码机的破译进度。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$，表示一条连接密码机 $u_i$ 和 $v_i$ 的传输链。

输出格式

对于每组测试用例，输出一行 $n$ 个数，其中第 $i$ 个数表示当 $t=i$ 时，破译进度最少的密码机的破译进度。

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

3 4 5 5 5

• 当 $t=0$ 时，密码机的破译进度为 $[2,5,1,3,4]$，破译进度最少的密码机的破译进度为 $1$；
• 当 $t=1$ 时，密码机的破译进度为 $[5,5,4,3,4]$，破译进度最少的密码机的破译进度为 $3$；
• 当 $t=2$ 时，密码机的破译进度为 $[5,5,5,4,4]$，破译进度最少的密码机的破译进度为 $4$；
• 当 $t=3$ 时，密码机的破译进度为 $[5,5,5,5,5]$，破译进度最少的密码机的破译进度为 $5$；
• 当 $t=4$ 时，密码机的破译进度为 $[5,5,5,5,5]$，破译进度最少的密码机的破译进度为 $5$；
• 当 $t=5$ 时，密码机的破译进度为 $[5,5,5,5,5]$，破译进度最少的密码机的破译进度为 $5$；

样例二~六

见附件下载。

数据范围

本题采用捆绑测试。

对于所有测试数据，保证：

• $1\le T\le 10^4$。
• $1\le n,\sum n\le 10^6$。同一测试点中每组测试用例的 $n$ 相等。
• $c$ 是一个 $1\sim n$ 的排列。
• $1\le u_i,v_i\le n$。

特殊性质 A：树是一条链；

时间限制：$\texttt{4s}$

空间限制：$\texttt{1G}$