Paint it really, really dark gray

#### 题目描述： 给你一棵节点编号为$1...n$的树，每个节点都有两种颜色：粉色或黑色。现在你要从1号节点（即树根）出发，每经过一个节点，该节点的颜色就会改变。（粉色变为黑色，黑色变为粉色）。 现在请你找出一条从1号节点（即树根）出发的路径，使得沿这条路径走完后，所有的节点颜色都变为黑色。**注意：你可以经过一个节点或一条边多次，并且路径不要求一定要在1号节点（即树根）结束。** ----------------------------- #### 输入格式： 第一行一个正整数$n$，代表树中节点的数量。 接下去第 $2$ 到 $n+1$ 行，每行一个整数：$1$代表黑色，$-1$代表粉色。其中第 $i$ 行的整数表示第 $i$ 号节点的颜色。 最后 $n-1$ 行，每行两个正整数 $x$ ，$y$ ，表示第 $x$ 号节点到第 $y$ 号节点有一条边相连。 #### 输出格式： 共一行，为能使所有节点变为黑色的路径上的节点编号。如果树中所有节点已经全为黑色，请输出$1$。数据保证有一条这样的路径存在。 ------------------------------ **关于样例输出：注意输出的第一个1号节点，实际上我们并没有将其变色。真正变色的节点为输出的第二个节点及之后的节点。**

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.

The first line of input contains integer $ n $ ( $ 2<=n<=200000 $ ), 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 $ .

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 $ 10^{7} $ .

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

1 4 2 5 2 4 3 4 1 4 1

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.