提交时请开启 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$：树是一条链。