Given a tree of size $n$, it has $n$ nodes and $n-1$ edges, with nodes numbered $1 \sim n$. Initially, each node contains a number from $1 \sim n$, and each number from $1 \sim n$ appears on exactly one node.

You need to perform exactly $n-1$ edge deletion operations. In each operation, you must choose an edge that has not yet been deleted. The numbers on the two nodes connected by this edge will be swapped, and then the edge will be deleted.

After $n-1$ operations, all edges will have been deleted. At this point, by arranging the node indices where the numbers $1 \sim n$ are located in increasing order of the numbers, we obtain a sequence of node indices $P_i$. Please find the lexicographically smallest $P_i$ that can be obtained under an optimal operation strategy.

Input

The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. For each test case: The first line contains an integer $n$, representing the size of the tree. The second line contains $n$ integers, where the $i$-th ($1 \le i \le n$) integer represents the initial node index of the number $i$. The next $n-1$ lines each contain two integers $x, y$, representing an edge connecting node $x$ and node $y$.

Output

For each test case, output a single line containing $n$ space-separated integers, representing the lexicographically smallest $P_i$ obtainable under an optimal operation strategy.

Examples

Input 1

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

Output 1

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

Examples 2

See tree/tree2.in and tree/tree2.ans in the contestant directory.

Constraints

For all test cases: $1 \le T \le 10$, and the input is guaranteed to be a tree.