XOR-scanner 是一种设备，它扫描一个整数序列，当且仅当序列中所有数字的按位异或和为零时，它才会接受该序列。

你有一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。你希望以编程竞赛题目中常见的标准格式写下这棵树： $n$ $u_1 \ v_1$ $\dots$ $u_{n-1} \ v_{n-1}$

其中 $n$ 是顶点数，$u_i, v_i$ 是第 $i$ 条边连接的两个顶点。

你希望 XOR-scanner 能够接受你的输出。初始情况下可能无法满足要求，因此你可以更改树中某些顶点的标签。操作完成后，所有顶点的标签必须是 $1$ 到 $10^9$ 之间（包含边界）的互不相同的整数。

对于每个顶点，已知其标签是否可以更改。请找到一种方法，通过重新标记某些允许更改的顶点（可以保持某些或全部标签不变），使得树的表示能够被 XOR-scanner 接受，或者报告这是不可能的。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)，表示树的顶点数。

第二行包含 $n$ 个整数，其中第 $i$ 个整数为 $0$ 表示第 $i$ 个顶点的标签是固定的，为 $1$ 表示该标签可以更改。

接下来的 $n-1$ 行，每行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$)，表示边的两个端点。

输出格式

如果存在满足要求的重新标记方案，请按照题目给出的格式打印重新标记后的树，保持边的顺序以及每条边端点的顺序。所有打印出的数字的按位异或和必须为零。

如果不可能，输出单个数字 $-1$。

样例

输入 1

5
0 1 0 1 0
1 3
1 4
2 5
3 5

输出 1

5
1 3
1 7
2 5
3 5