题目描述

给定一个 $N$ 个顶点编号为 $1, 2, ..., N$ 的树。第 $i$ 条边连接了顶点 $a_i$ 和顶点 $b_i$。你还被给定了一个长度为 $N$ 的字符串 $S$，由 0 和 1 组成。$S$ 的第 $i$ 个字符表示顶点 $i$ 上的棋子数量。

Snuke 将执行以下操作一定次数：

• 选择两个相距至少 $2$ 的棋子，并将这些棋子彼此靠近 $1$ 步。更正式地说，选择两个具有一个或多个棋子的顶点 $u$ 和 $v$，并考虑它们之间的最短路径。此处路径必须包含至少两条边。然后，将一个棋子从 $u$ 移动到路径上的相邻顶点，将一个棋子从 $v$ 移动到路径上的相邻顶点。

通过重复这个操作，Snuke 想要所有的棋子都在同一个顶点上。这是否可能？如果是，还要找出实现该目标所需的最小操作数。

约束条件

• $2 \leq N \leq 2000$
• $|S| = N$
• $S$ 由 0 和 1 组成，其中至少包含一个 1。
• $1 \leq a_i, b_i \leq N(a_i \neq b_i)$
• 边 $(a_1, b_1), (a_2, b_2), ..., (a_{N - 1}, b_{N - 1})$ 构成一棵树。

输入

输入以以下格式从标准输入给出：

$N$ $S$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_{N - 1}$ $b_{N - 1}$

输出

如果无法使所有棋子位于同一个顶点上，则输出 -1。如果可以，则输出实现该目标所需的最小操作数。

示例输入1

7
0010101
1 2
2 3
1 4
4 5
1 6
6 7

示例输出1

3

我们可以通过以下三个操作将所有棋子聚集在一起：

• 选择顶点 $3$ 和 $5$ 上的棋子。
• 选择顶点 $2$ 和 $7$ 上的棋子。
• 选择顶点 $4$ 和 $6$ 上的棋子。

示例输入2

7
0010110
1 2
2 3
1 4
4 5
1 6
6 7

示例输出2

-1

示例输入3

2
01
1 2

示例输出3

0