19290번 - Hiding a Tree 스페셜 저지다국어

문제

XOR-scanner is a device which scans a sequence of integers and accepts it if and only if the bitwise XOR of all numbers in the sequence is equal to zero.

You have a tree with $n$ vertices, labeled with integers from 1ドル$ to $n$. You want to write down this tree in a standard format for the programming contest problem:

$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 vertices connected by the $i$-th edge.

You want the XOR-scanner to accept your output. It might be not the case initially, so you can change the labels of some vertices of the tree. After this operation all vertices must have distinct integer labels from 1ドル$ to 10ドル^9,ドル inclusive.

For each vertex it is known if it is possible to change its label. Find a way to relabel some allowed vertices (possibly, keeping some labels or all of them as is) in such a manner that the XOR-scanner accepts the tree representation or report that it is impossible.

입력

In the first line there is an integer $n$ (2ドル \leq n \leq 100,000円$), the number of vertices in a tree.

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

Each of the next $n-1$ lines contains two integers $u_i,ドル $v_i$ (1ドル \leq u_i, v_i \leq n$), which denote the endpoints of the edges.

출력

If the desired relabeling exists, print the relabeled tree in the same format as it is given in the statement, keeping the order of edges and the order of endpoints of the each edge. The bitwise XOR of all printed numbers must be zero.

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

제한

힌트