题目背景

小 L 感到无聊，于是希望在树上行走。

题目描述

小 L 有一棵 $n$ 个点的树，树上点有点权，其中第 $i$ 个点权值为 $a_i$。

他不喜欢奇奇怪怪的权值，于是他保证 $a_i$ 一定是 $-1, 0, 1$ 之一。

他认为在树上行走是有趣的，于是他想要在这棵树上走出一条路径 $P$，其需要满足以下条件：

• $P$ 是一条可以为空的简单有向路径。
• 设 $P$ 中依次经过的点为 $P_1, P_2, \cdots, P_{|P|}$，则你求出的 $P$ 需要满足 $P_1 = 1$。
• 设 $f(P) = \displaystyle\sum_{i = 1}^{|P|} \frac{a_{P_i}}{2^{i - 1}}$，则你求出的 $P$ 需要满足 $f(P)$ 最大。
• 在 $f(P)$ 最大的前提下，你求出的 $P$ 还需要满足 $P$ 的字典序最小。

请你求出符合上述条件的路径 $P$。

关于本题中字典序的定义：

设有两条待比较的路径 $P \neq Q$。

• 若存在 $1 \leq i \leq \min(|P|, |Q|)$，使得 $\forall 1 \leq j < i, P_j = Q_j$ 且 $P_i < Q_i$，则我们称 $P$ 的字典序小于 $Q$。
• 若存在 $1 \leq i \leq \min(|P|, |Q|)$，使得 $\forall 1 \leq j < i, P_j = Q_j$ 且 $P_i > Q_i$，则我们称 $P$ 的字典序大于 $Q$。
• 若 $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ 且 $|P| < |Q|$，则我们称 $P$ 的字典序小于 $Q$。
• 若 $\forall 1 \leq i \leq \min(|P|, |Q|), P_i = Q_i$ 且 $|P| > |Q|$，则我们称 $P$ 的字典序大于 $Q$。

输入格式

第一行，一个整数 $n$；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$；

接下来 $n - 1$ 行，每行两个整数 $u, v$，表示树上的一条边。

输出格式

一行，$|P|$ 个整数，表示你求出的路径 $P$ 中依次经过的点。

特别的，若 $P$ 为空路径，请不要进行任何输出操作。

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

1 2 4

提示

样例 #1 解释

$P = [1, 2, 4]$ 时 $f(P) = 1 + 0 + \frac{1}{4} = \frac{5}{4}$。可以证明不存在更优的 $P$。

数据范围

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$a_i \in \{-1, 0, 1\}$，$1 \leq u, v \leq n$，保证给出的边可以构成一棵无根树。