Lexicographically Smallest Node Permutation after Edge Swaps in a Tree

Given an undirected tree with $n$ nodes and $n-1$ edges where the nodes are numbered from $1$ to $n$, each node initially contains a unique integer from $1$ to $n$. You are to perform exactly $n-1$ edge‐deletion operations. In each operation, you choose an edge that has not yet been removed; at that moment, the numbers on its two endpoint nodes are swapped, and then the edge is removed. After all operations the tree becomes edgeless. Now, define a permutation $P$ as follows: for each integer $i$ from $1$ to $n$, let $P_i$ be the node number in which the digit $i$ resides in the final configuration. Your task is to determine the lexicographically smallest permutation $P$ that can be obtained by choosing an optimal order of deletions.

For example, consider a tree with $5$ nodes. Suppose initially the numbers $1,\,2,\,3,\,4,\,5$ are placed on nodes $2$, $1$, $3$, $5$, $4$, respectively. With an optimal deletion order (for instance, deleting the edges in the order indicated by (E2), (E4), (E3), (E1) in the figure), the final permutation obtained by listing the node numbers in the increasing order of the digits is 1 3 2 5 4 (which is lexicographically smallest among all possible outcomes).

It can be shown that the order of the $n-1$ swaps affects the final assignment. In other words, if we denote the final number on vertex $i$ by f[i], then for each digit $d$ (which originally appears exactly once) there exists a unique vertex $v$ with f[v] = d, and the permutation $P=(v_1,v_2,\dots,v_n)$ (where digit $1$ is at vertex $v_1$, digit $2$ is at vertex $v_2$, etc.) depends on the order in which the edges are removed. Your goal is to choose the deletion order so that $P$ is lexicographically minimum.

Note: A sequence $P$ is lexicographically smaller than $Q$ if there exists an index $j$ such that $P_1=Q_1, P_2=Q_2, \dots, P_{j-1}=Q_{j-1}$ and $P_j<Q_j$.

inputFormat

The first line contains a single integer $n$ ($2\le n\le 8$).

The second line contains $n$ distinct integers $a_1, a_2, \dots, a_n$, where $a_i$ is the initial number on node $i$ (each from $1$ to $n$).

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1\le u,v\le n$, $u\ne v$) representing an undirected edge between nodes $u$ and $v$. It is guaranteed that these edges form a tree.

outputFormat

Output the lexicographically smallest permutation $P$, consisting of $n$ space‐separated integers, where $P_i$ is the node number that eventually holds the digit $i$.

sample

2
1 2
1 2

2 1