Person in Charge

Problem Description

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

Next, you need to perform exactly $n - 1$ edge deletion operations. In each operation, you select an edge that has not been deleted yet. At this time, 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 be deleted. At this point, arrange the node numbers where the numbers $1 \sim n$ are located in ascending order of the numbers to obtain a permutation $P_i$ of node numbers. Now, please find the lexicographically smallest $P_i$ that can be obtained under the optimal operation scheme.

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

(The following images are from LibreOJ)

Input Format

This 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 integer ($1 \le i \le n$) represents the node number where the number $i$ is initially located.
• The next $n - 1$ lines each contain two integers $x$ and $y$, representing an edge connecting node $x$ and node $y$.

Output Format

For each test case, output a line with $n$ integers separated by spaces, representing the lexicographically smallest $P_i$ obtainable under the optimal operation scheme.

Sample 1

See tree/tree1.in and tree/tree1.ans in the contestant's directory.

Sample 2

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

Data Range

For $100\%$ of the data: $1 \le T \le 10$, $1 \le n \le 2000$, the given graph is a tree, and the initial $n$ numbers form a permutation of $1 \sim n$.