405909: GYM102155 K Hiding a Tree

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Hiding a Treetime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

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 u1 v1 ... un - 1 vn - 1

Here n is the number of vertices and ui, vi 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 109, 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.

Input

In the first line there is an integer n (2 ≤ n ≤ 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 ui, vi (1 ≤ ui, vi ≤ n), which denote the endpoints of the edges.

Output

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.

ExampleInput
5
0 1 0 1 0
1 3
1 4
2 5
3 5
Output
5
1 3
1 7
2 5
3 5

加入题单

上一题 下一题 算法标签: