[AGC034E] Complete Compress

给你一颗 $n$ 个节点的树，并用二进制串告诉你哪些节点上有棋子（恰好一颗）。 可以进行若干次操作，每次操作可以将两颗距离至少为 $2$ 的棋子向中间移动一步。 问能否通过若干次操作使得所有的棋子都在一个点上，如果能，输出最小操作次数，如果不能，输出 $-1$ 。 数据范围：$2 \leq n\leq 2000$。

[problemUrl]: https://atcoder.jp/contests/agc034/tasks/agc034_e 頂点に番号 $ 1,\ 2,\ ...,\ N $ がついた $ N $ 頂点の木が与えられます。$ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 また長さ $ N $ の `0`, `1` からなる文字列 $ S $ が与えられ、$ S $ の $ i $ 文字目は頂点 $ i $ に置いてあるコマの個数を表しています。 すぬけ君は、以下の操作を好きなだけ行います。 - 距離が $ 2 $ 以上離れたコマ $ 2 $ 個を選び、お互いに $ 1 $ ずつ近づける。 正確に述べると、コマの置かれた頂点 $ u,\ v $ を選び、$ u,\ v $ 間の最短パスを考える。ここでパスの辺数が $ 2 $ 以上となるように選ぶことにする。パスにおいて $ u $ に隣り合う頂点にコマを $ 1 $ 個 $ u $ から動かし、$ v $ に隣り合う頂点にコマを $ 1 $ 個 $ v $ から動かす。 すぬけ君はこれを繰り返し、すべてのコマを同じ頂点に集めたいです。このようなことは可能でしょうか？ 可能な場合、それを達成するのに必要な操作の最小回数も求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ : $ $ a_{N\ -\ 1} $ $ b_{N\ -\ 1} $

コマを同じ頂点に集められない場合 `-1`、集められる場合は操作の最小回数を出力せよ。

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

3

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

-1

2
01
1 2

0

### 制約 - $ 2\ \leq\ N\ \leq\ 2000 $ - $ |S|\ =\ N $ - $ S $ は `0`, `1`からなり、また少なくとも $ 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}) $ は木をなす ### Sample Explanation 1 \- 頂点 $ 3,\ 5 $ のコマを選ぶ - 頂点 $ 2,\ 7 $ のコマを選ぶ - 頂点 $ 4,\ 6 $ のコマを選ぶ の $ 3 $ 回の操作ですべてのコマを頂点 $ 1 $ に集めることができます。