Hiding a Tree

XOR-scanner is a device that checks a sequence of integers. It accepts the sequence if and only if the bitwise XOR of all numbers in the sequence is $0$.

You have a tree with $n$ vertices, labeled with integers from $1$ to $n$. You want to write this tree in the following standard format.

$n$ $u_1$ $v_1$ $\dots$ $u_{n-1}$ $v_{n-1}$

Here $n$ is the number of vertices, and $u_i$, $v_i$ are the vertices connected by the $i$-th edge.

You want the XOR-scanner to accept your output. It may not accept it at first, so you can change the labels of some vertices. After relabeling, all vertices must have distinct integer labels from $1$ to $10^9$, inclusive.

For each vertex, it is known whether its label can be changed. Relabel some of the vertices that can be changed (you may keep some or all of their labels as they are) so that the XOR-scanner accepts the output. If this is impossible, report it.

The first line contains an integer $n$ ($2 \leq n \leq 100000$), the number of vertices in the tree.

The next line contains $n$ integers. The $i$-th of them is $0$ if the label of vertex $i$ is fixed, and $1$ if it can be changed.

Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), the endpoints of an edge.

If a valid relabeling exists, print the relabeled tree in the same format as the statement. Keep the order of the edges and the order of the endpoints within each edge. The bitwise XOR of all printed numbers must be $0$.

If it is impossible, print a single number -1.