Y村有 n 间屋子和 n-1 条道路，并且任意屋子之间两两连通。

由于很多村民下雨天忘记收衣服导致衣服是湿的。

小w有一个神奇的机器，它会在小w走进一间屋子时自动激活(初始屋子不算)，变化屋内衣服的状态：从干变成湿或者从湿变成干。

现在小w在 1 号房屋，他希望你帮他规划一条路径，从一号点出发然后使得他按照这条路径遍历房屋之后所有屋子的衣服都是干的。

一条长度为 k 的合法路径 path=(v_1,v_2,v_3,\cdots,v_k) 满足：{v_i, v_{i+1}} \in E 。其中 E 是图的边集。

第一行输入一个整数 n 表示房屋数量。

第二行 n 个整数，每个数是 0 或者 1，其中 1 表示这间屋子的衣服是干的，0表示这间屋子的衣服是湿的。

接下来 n-1 行，每行两个整数 u,v 表示 u 和 v 之间有一条无向边。

输出一行表示路径，路径需要满足:

• 两个点之间用空格隔开。
• 从 1 号房屋出发，使得小w按照这条路径遍历房屋之后所有屋子的衣服都是干的。
• 路径包含的点数不超过 10^7。

任意合法路径都会被认为正确，数据保证答案存在。

样例解释

下面说明小w每一步后房屋衣服状态的变化:

• 1\to 2, 2号屋子变化，衣服状态 [1, 0, 0, 0]
• 2\to 3, 3号屋子变化，衣服状态 [1, 0, 1, 0]
• 3\to 2, 2号屋子变化，衣服状态 [1, 1, 1, 0]
• 2\to 4, 4号屋子变化，衣服状态 [1, 1, 1, 1]
• 4\to 2, 2号屋子变化，衣服状态 [1, 0, 1, 1]
• 2\to 1, 1号屋子变化，衣服状态 [0, 0, 1, 1]
• 1\to 2, 2号屋子变化，衣服状态 [0, 1, 1, 1]
• 2\to 1, 1号屋子变化，衣服状态 [1, 1, 1, 1]

此时所有屋子的衣服都是干的。

数据范围

20\% 的数据满足 n \leq 20

40\% 的数据满足 n \leq 100

另外 10\% 的数据满足只有一间屋子的衣服是湿的。

另外 10\% 的村庄是一条链。

100\% 的数据满足 n \leq 10^5。