Tree of Lamps

You are given a tree with n bulbs (vertices) numbered from 1 to n and n-1 wires (edges) connecting them. Each bulb is either on (state 1) or off (state 0). Every bulb has a button; when pressed it toggles the state of that bulb (from 0 to 1 or from 1 to 0). Initially, at least one bulb is off. Your task is to find a shortest walk (a sequence of vertices) satisfying the following:

• The sequence represents a valid walk on the tree, i.e. every two consecutive vertices in the sequence are adjacent.
• Each time a vertex appears in the sequence, its button is pressed (thus its state is toggled).
• After processing the entire sequence (i.e. performing all toggles in order), every bulb is on (state 1).

Note: A vertex may appear several times in the sequence. If a vertex’s button is pressed an even number of times, its state remains unchanged from the initial state; if pressed an odd number of times, its state is flipped. In other words, if the initial state of bulb i is A_i and it is pressed c_i times then the final state is A_i \oplus c_i (mod 2). Since the desired final state is 1 for every bulb, for each i it must hold that

$$A_i \oplus c_i \;=\; 1.$$

Your output should be a shortest valid sequence of vertices (i.e. a walk on the tree) for which the above condition holds. It can be shown that a solution always exists.

inputFormat

The first line contains an integer n (2 ≤ n ≤ 2×10⁵), the number of bulbs (vertices).

The second line contains n space‐separated integers, each 0 or 1, representing the initial state of bulbs 1 through n (0 means off, 1 means on). It is guaranteed that at least one bulb is off.

The next n-1 lines each contain two integers u and v (1 ≤ u, v ≤ n) denoting that there is an edge between vertices u and v.

outputFormat

On the first line, output a single integer k denoting the length of your sequence (i.e. the number of button presses). On the next line, output k space‐separated integers representing the sequence of vertices whose buttons are pressed in order. The sequence must form a valid walk in the tree. If there are multiple solutions, output any one of them.

sample

2
0 1
1 2

5
1 2 1 2 1