K. Point Divide and Conquer
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For a tree $$$T$$$ with $$$n$$$ vertices (without a root), numbered $$$1, 2, \ldots, n$$$, Little A operates on it according to the permutation $$$p_1, p_2, \ldots, p_n$$$ to obtain a rooted tree $$$T'$$$ as follows:

  1. Find the vertex $$$x$$$ in the tree $$$T$$$ that appears first in the permutation $$$p_1, p_2, \ldots, p_n$$$.
  2. Remove $$$x$$$ from $$$T$$$ and add $$$x$$$ to $$$T'$$$ as the root of $$$T'$$$.
  3. The remaining vertices in $$$T$$$ form several connected components $$$T_1, T_2, \ldots, T_k$$$ (where $$$k$$$ may be $$$0$$$), each of which is still an unrooted tree. For each unrooted tree $$$T_i$$$, operate on it to obtain the rooted tree $$$T'_i$$$.
  4. Add each rooted tree $$$T'_i$$$ to $$$T'$$$ and set the parent of the root of $$$T'_i$$$ to be $$$x$$$.

Now given a tree $$$T$$$ and the operation permutation $$$p_1, p_2, \ldots, p_n$$$, Little A wants to find the parent of each vertex in the rooted tree $$$T'$$$ obtained after operating on $$$T$$$ according to the permutation $$$p_1, p_2, \ldots, p_n$$$.

Input

The first line contains a positive integer $$$T$$$ $$$(1 \leq T \leq 10^4)$$$, indicating the number of test cases.

For each test case, the first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ representing the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ $$$(1 \leq p_i \leq n, \forall i \neq j, p_i \neq p_j)$$$, representing the permutation.

The next $$$n-1$$$ lines each contain two integers $$$x, y$$$ $$$(1 \leq x, y \leq n, x \neq y)$$$, representing an edge in the tree.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a line with $$$n$$$ integers, where the $$$i$$$-th integer represents the parent of vertex $$$i$$$ in the rooted tree $$$T'$$$ obtained after the operation. If vertex $$$i$$$ is the root, then its parent is denoted by $$$0$$$.

Example
Input
3
3
2 3 1
1 2
2 3
5
2 1 4 5 3
1 2
1 3
2 4
2 5
5
1 2 3 4 5
1 2
1 3
2 4
2 5
Output
2 0 2
2 0 1 2 2
0 1 1 2 2
Note

For the first sample case, first $$$p_1=2$$$, so the root of $$$T'$$$ is $$$2$$$, and $$$T$$$ is divided into connected components $$$T_1=\{2\}, T_2=\{3\}$$$. Thus, both $$$2$$$ and $$$3$$$ have $$$2$$$ as their parent in $$$T'$$$.

For the second sample case, first $$$p_1=2$$$, so the root of $$$T'$$$ is $$$2$$$, and $$$T$$$ is divided into connected components $$$T_1=\{1,3\}, T_2=\{4\}, T_3=\{5\}$$$. Both $$$T_2$$$ and $$$T_3$$$ are trees consisting of single vertices, so both $$$4$$$ and $$$5$$$ have $$$2$$$ as their parent in $$$T'$$$; for $$$T_1=\{1,3\}$$$, since $$$1$$$ appears earlier in the sequence $$$p$$$ ($$$p_2=1, p_5=3$$$), the root of $$$T_1'$$$ is $$$1$$$, so the parent of $$$1$$$ in $$$T'$$$ is $$$2$$$, and the parent of $$$3$$$ in $$$T'$$$ is $$$1$$$.

For the third sample case, first $$$p_1=1$$$, so the root of $$$T'$$$ is $$$1$$$, and $$$T$$$ is divided into connected components $$$T_1=\{2,4,5\}, T_2=\{3\}$$$. $$$T_2$$$ is a tree consisting of a single vertex, so the parent of $$$3$$$ in $$$T'$$$ is $$$1$$$; for $$$T_1=\{2,4,5\}$$$, since $$$2$$$ appears earlier in the sequence $$$p$$$ ($$$p_2=2, p_4=4, p_5=5$$$), the root of $$$T_1'$$$ is $$$2$$$, so the parent of $$$2$$$ in $$$T'$$$ is $$$1$$$. Continuing to split, $$$4$$$ and $$$5$$$ each form separate subtrees, and their parents in $$$T'$$$ are both $$$2$$$.