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 (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 any alternating sequence of vertices and edges, starting and ending with a vertex, such that every edge in the sequence connects the vertices before and after it.

Input Specification

The first line of input contains the integer $N$, denoting the number of nodes of the graph. The following $N$ lines each contain one integer, the color of the $i^{\text{th}}$ node.

If the $i^{\text{th}}$ integer is:

• $1$, then the corresponding node is black
• $-1$, then the node is pink

Each of the next $N-1$ lines contains two integers, which represent the indices of the nodes which are connected (one-based).

Output Specification

Output the path of a squirrel: output a sequence of visited nodes' indices in order of visiting. In case all of the nodes are initially black you should print $1$.

Constraints

• $2\le N\le 2\cdot {10}^5$

Sample Input

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

Sample Output

1 4 2 5 2 4 3

Explanation

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
• Finally, we visit node 3 and change its color to black