Problem Description

Given a tree of size $n$, it has $n$ nodes and $n - 1$ edges, with nodes numbered from $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.

Next, you need to perform exactly $n - 1$ edge-deletion operations. In each operation, you choose an edge that has not been deleted. The numbers on the two endpoints of this edge will swap, and then this edge will be deleted.

After $n - 1$ operations, all edges will have been deleted. At this time, list the node indices where numbers $1 \sim n$ are located in increasing order of the numbers, and you obtain a permutation of node indices $P_i$. Now, please find the lexicographically smallest $P_i$ that can be obtained under an optimal sequence of operations.

As shown above, the numbers $1 \sim 5$ in the blue circles are initially on nodes ②, ①, ③, ⑤, ④ respectively. Delete all edges in the order (1)(4)(3)(2), and the tree becomes the figure below. The node index permutation obtained by the number order is ①③④②⑤, which is the lexicographically smallest among all possible results.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case:

The first line contains an integer $n$, indicating the size of the tree.

The second line contains $n$ integers. The $i (1 \leq i \leq n)$-th integer indicates the node index where number $i$ is initially located.

The next $n - 1$ lines each contain two integers $x$, $y$, indicating an edge connecting node $x$ and node $y$.

Output Format

For each test case, output one line with $n$ integers separated by spaces, representing the lexicographically smallest $P_i$ that can be obtained under an optimal sequence of operations.

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

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

Hint

Constraints

For all test points: $1 \leq T \leq 10$, and it is guaranteed that the input is a tree.

Translated by ChatGPT 5