P5659 [CSP-S 2019] Numbers on a Tree.

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. 

**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$.

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.

Constraints | Test Point ID | $n \leq$ | Special Property | | :----------- | :----------- | :----------- | | $1 \sim 2$ | $10$ | None | | $3 \sim 4$ | $160$ | The tree is a chain | | $5 \sim 7$ | $2000$ | Same as above | | $8 \sim 9$ | $160$ | There exists a node with degree $n - 1$ | | $10 \sim 12$ | $2000$ | Same as above | | $13 \sim 16$ | $160$ | None | | $17 \sim 20$ | $2000$ | None | For all test points: $1 \leq T \leq 10$, and it is guaranteed that the input is a tree. Translated by ChatGPT 5