Background

Xiao L feels bored, so he wants to walk on a tree.

Problem Description

Xiao L has a tree with $n$ nodes. Each node has a weight, and the weight of node $i$ is $a_i$.

He does not like strange weights, so he guarantees that $a_i$ must be one of $-1, 0, 1$.

He thinks walking on a tree is interesting, so he wants to find a path $P$ on this tree that satisfies the following conditions:

• $P$ is a simple directed path that can be empty.
• Let the nodes visited by $P$ in order be $P_1, P_2, \cdots, P_{|P|}$. The path you find must satisfy $P_1 = 1$.
• Let $f(P) = \displaystyle\sum_{i = 1}^{|P|} \frac{a_{P_i}}{2^{i - 1}}$. The path you find must maximize $f(P)$.
• Under the condition that $f(P)$ is maximized, the path you find must also have the smallest lexicographical order.

Please find a path $P$ that satisfies the conditions above.

Definition of lexicographical order in this problem:

Given two paths to compare $P \neq Q$.

• If there exists $1 \leq i \leq \min(|P|, |Q|)$ such that $\forall 1 \leq j < i, P_j = Q_j$ and $P_i < Q_i$, then we say that $P$ is lexicographically smaller than $Q$.
• If there exists $1 \leq i \leq \min(|P|, |Q|)$ such that $\forall 1 \leq j < i, P_j = Q_j$ and $P_i > Q_i$, then we say that $P$ is lexicographically larger than $Q$.
• If $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ and $|P| < |Q|$, then we say that $P$ is lexicographically smaller than $Q$.
• If $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ and $|P| > |Q|$, then we say that $P$ is lexicographically larger than $Q$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$.

The next $n - 1$ lines each contain two integers $u, v$, representing an edge in the tree.

Output Format

Output one line with $|P|$ integers, representing the nodes visited by the path $P$ in order.

In particular, if $P$ is an empty path, do not output anything.

5
1 0 -1 1 -1
1 2
2 3
2 4
1 5

1 2 4

Hint

Sample #1 Explanation

When $P = [1, 2, 4]$, we have $f(P) = 1 + 0 + \frac{1}{4} = \frac{5}{4}$. It can be proven that there is no better $P$.

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^5$, $a_i \in \{-1, 0, 1\}$, $1 \leq u, v \leq n$. It is guaranteed that the given edges form an unrooted tree.

Translated by ChatGPT 5