You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

提交时请开启 O2 优化，并使用较快的输入输出方式。

保证时间限制与 std 单个测试点运行时间的最大值的差值 $\boldsymbol{>1000\textbf{ ms}}$，且空间限制在 std 的 1.5 倍以上。

亡灵飘飞，惊悚之舞。

Description

一棵 $n$ 个节点的树，每个节点上有一只幽灵，初始有黑白两色。

现在害怕幽灵的小玖动用了超能力，她每次可以选择一条边，并且这条边连接的两个幽灵颜色相同，然后她使出超能力，将这两个节点颜色取反。

最后她希望可以看到所有幽灵，于是她希望最后所有幽灵的颜色均为白色。

她实在太害怕幽灵了，所以希望她希望你给出最小的步数，或报告无解。

Format

Input

第一行一个正整数 $n$。

第二行为 $n$ 个整数 $c_i$，$c_i=0$ 表示节点 $i$ 上的幽灵是白色的，$c_i=1$ 表示为黑色。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示树上的一条连接 $u,v$ 的边。

Output

若无解，输出一行一个 -1。

若有解，输出一行一个正整数，表示最小步数。

Samples

3
1 0 1
1 2
1 3

1

3
0 1 1
1 2
1 3

-1

14
1 1 0 1 0 1 0 1 1 1 0 0 0 1
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
6 10
6 11
8 12
9 13
9 14

4

23
0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 9
5 10
6 11
6 12
7 13
7 14
8 15
8 16
9 17
9 18
10 19
13 20
13 21
21 22
21 23

47

Limitation

本题开启捆绑测试。

• 特殊性质 $\alpha$：$c_i=1$。
• 特殊性质 $\beta$：树是一个菊花。
• 特殊性质 $\gamma$：树是一条链。