CF717E.Paint it really, really dark gray

I see a pink boar and I want it painted black. Black boars look much more awesome and mighty than the pink ones. Since Jaggy became the ruler of the forest, he has been trying his best to improve the diplomatic relations between the forest region and the nearby ones.

Some other rulers, however, have requested too much in return for peace between their two regions, so he realized he has to resort to intimidation. Once a delegate for diplomatic relations of a neighboring region visits Jaggy’s forest, if they see a whole bunch of black boars, they might suddenly change their mind about attacking Jaggy. Black boars are really scary, after all.

Jaggy’s forest can be represented as a tree (connected graph without cycles) with n vertices. Each vertex represents a boar and is colored either black or pink. Jaggy has sent a squirrel to travel through the forest and paint all the boars black. The squirrel, however, is quite unusually trained and while it traverses the graph, it changes the color of every vertex it visits, regardless of its initial color: pink vertices become black and black vertices become pink.

Since Jaggy is too busy to plan the squirrel’s route, he needs your help. He wants you to construct a walk through the tree starting from vertex 1 such that in the end all vertices are black. A walk is a sequence of vertices, such that every consecutive pair has an edge between them in a tree.

我看到一头粉红色的野猪，想把它涂成黑色。黑色的野猪看起来比粉红色的野猪更加威武霸气。自从贾吉成为森林之王后，他一直竭尽全力改善森林地区与邻近地区之间的外交关系。

然而，一些其他地区的统治者为换取双方地区的和平，索要了过高的条件，因此贾吉意识到他不得不诉诸威慑手段。一旦邻近地区负责外交事务的使节访问贾吉的森林，如果他们看到一大群黑色野猪，或许会突然改变进攻贾吉的想法——毕竟，黑色野猪真的非常可怕。

贾吉的森林可被建模为一棵包含 $n$ 个顶点的树（即无环连通图）。每个顶点代表一头野猪，其颜色为黑色或粉红色。贾吉已派出一只松鼠穿越整片森林，将所有野猪涂成黑色。然而，这只松鼠的训练方式极为特殊：它在图中行进时，会翻转所经过的每一个顶点的颜色（无论其初始颜色如何）——粉红色顶点变为黑色，黑色顶点变为粉红色。

由于贾吉公务繁忙，无暇规划松鼠的行进路线，因此需要你的帮助。请你构造一条从顶点 $1$ 出发、遍历该树的路径，使得最终所有顶点均为黑色。此处，“路径”指一个顶点序列，其中任意两个相邻顶点在树中均存在一条边相连。

The first line of input contains integer n (2 ≤ n ≤ 200 000), denoting the number of vertices in the tree. The following n lines contains n integers, which represent the color of the nodes.

If the i-th integer is 1, if the i-th vertex is black and  - 1 if the i-th vertex is pink.

Each of the next n - 1 lines contains two integers, which represent the indexes of the vertices which are connected by the edge. Vertices are numbered starting with 1.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 200\,000$），表示树中顶点的数量。接下来的 $n$ 行每行包含一个整数，表示对应节点的颜色。

若第 $i$ 个整数为 $1$，则第 $i$ 个顶点为黑色；若为 $-1$，则第 $i$ 个顶点为粉色。

接下来的 $n-1$ 行每行包含两个整数，表示由一条边相连的两个顶点的编号。顶点编号从 $1$ 开始。

Output path of a squirrel: output a sequence of visited nodes' indexes in order of visiting. In case of all the nodes are initially black, you should print 1. Solution is guaranteed to exist. If there are multiple solutions to the problem you can output any of them provided length of sequence is not longer than 107.

松鼠的输出路径：按访问顺序输出所访问节点的索引序列。若所有节点初始均为黑色，则应输出 1。题目保证解存在。若存在多个解，可输出其中任意一个，但序列长度不得超过 $10^7$。

At the beginning squirrel is at node 1 and its color is black. Next steps are as follows:

• From node 1 we walk to node 4 and change its color to pink.
• From node 4 we walk to node 2 and change its color to pink.
• From node 2 we walk to node 5 and change its color to black.
• From node 5 we return to node 2 and change its color to black.
• From node 2 we walk to node 4 and change its color to black.
• We visit node 3 and change its color to black.
• We visit node 4 and change its color to pink.
• We visit node 1 and change its color to pink.
• We visit node 4 and change its color to black.
• We visit node 1 and change its color to black.

初始时，松鼠位于节点 1，其颜色为黑色。接下来的步骤如下：

• 从节点 1 出发，走到节点 4，并将其颜色改为粉色。
• 从节点 4 出发，走到节点 2，并将其颜色改为粉色。
• 从节点 2 出发，走到节点 5，并将其颜色改为黑色。
• 从节点 5 返回节点 2，并将其颜色改为黑色。
• 从节点 2 出发，走到节点 4，并将其颜色改为黑色。
• 访问节点 3，并将其颜色改为黑色。
• 访问节点 4，并将其颜色改为粉色。
• 访问节点 1，并将其颜色改为粉色。
• 访问节点 4，并将其颜色改为黑色。
• 访问节点 1，并将其颜色改为黑色。