Problem: You are given a tree with N vertices numbered 1, 2, ..., N. The i-th edge connects Vertex a_i and Vertex b_i. You are also given a string S of length N consisting of `0` and `1`. The i-th character of S represents the number of pieces placed on Vertex i.

Snuke will perform the following operation some number of times:

* Choose two pieces the distance between which is at least 2, and bring these pieces closer to each other by 1. More formally, choose two vertices u and v, each with one or more pieces, and consider the shortest path between them. Here the path must contain at least two edges. Then, move one piece from u to its adjacent vertex on the path, and move one piece from v to its adjacent vertex on the path.



By repeating this operation, Snuke wants to have all the pieces on the same vertex. Is this possible? If the answer is yes, also find the minimum number of operations required to achieve it.

Constraints

* 2 \leq N \leq 2000
* |S| = N
* S consists of `0` and `1`, and contains at least one `1`.
* 1 \leq a_i, b_i \leq N(a_i \neq b_i)
* The edges (a_1, b_1), (a_2, b_2), ..., (a_{N - 1}, b_{N - 1}) forms a tree.

Input

Input is given from Standard Input in the following format:


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


Output

If it is impossible to have all the pieces on the same vertex, print `-1`. If it is possible, print the minimum number of operations required.

Examples

Input

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


Output

3


Input

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


Output

-1


Input

2
01
1 2


Output

0

Solution (in PYTHON3):

Solution:

"""

https://atcoder.jp/contests/agc034/tasks/agc034_e

まず、可能かどうかの判定をしたい
木を白黒に塗り分ける。
最後に集める点をまずVとする。
1回の操作で、2つの駒は
●両方vに近づく　　　　　　　→距離和は2減る(同一パス上に無い場合)
●片方は近づき、片方は離れる →距離和は変化しない (同一パス上にある場合)
の2通りがある。
なので、距離和を0にするためには全ての頂点との距離の和が偶数の点のみがVになりうる

Vを決めたとすると、答えの最小は距離和//2
あるVに集めるのが可能か & 最小の操作回数を求めたい

最小回数は、Vからのパスの直線上に無い2点を選び続けること
操作2を行うことで可能なになる例を考えたい→どう状況が変化するか？
片方の点が戻ることが異なる点→他のパス上の点からすると選択回数の総和は変わらない…？
同一パス上の点からすると、これも変わらない
→操作1だけで達成可能？

後はdfsかなぁ
→それぞれの子にある選択回数の最大値と最小値を管理する？
→Vで選択回数0にできるならおｋ

最大は何も消さずに送り付ける場合なので特に難しくない
最小は…　とやるのはきつくないか…？

選べないのはパス上の2点→あるパス上の寄与が過半数にならなければ全て選べるのでは？
パスから分岐している部分を考えると、分岐以降は全てパスの値を減らすのに使える
が、統合以降はパスの値になる
→これでいけそうだぞ！？

実装はdfs
最大値が分かればよいので、maxで送っていけばよい

十分か…？
最後の状態では、全てのパス上の寄与は0→過半数のパスはない
過半数がない場合、最大のパスに含まれる点とそれ以外のパス(→必ず存在する…？)を選べば過半数にはならない
過半数ではないのでそれ以外のパスは必ず存在する
→最後の状態に絶対収束する

なぜWA?
→前の回答はある点の寄与が半分以下だったらおkにしてる
→それだと正解なケース
→一つの点の寄与は過半数だが、一つのパスからの寄与はそうではない→ありえん
→一つの点からの寄与は半分以下だが、一つのパスからは過半数→ありうる
→可能を不可能として出力している？…ありえなさそう
→プログラムのミス？(総合距離が小さい or 最大距離が大きい)

→不可能を可能として出していた模様??

=====答えを見た=====
面倒くさいと切り捨てた方針っぽい
確かにパス上の寄与は正しそうだけど絶対正しいと証明できてたわけではない…

→部分木内での操作を行ってから部分木間で操作を行えばよい
dfs(v,p) = vの部分木内での操作のうち、どこまで操作回数を減らせるか
偶奇は保存される。過半数を超えるのがなかった場合極限まで減らせる

"""

import sys
from sys import stdin
sys.setrecursionlimit(3000)

dic = {}
def dfs(v,p):
    if (v,p) in dic:
        return dic[(v,p)]
    clis = []
    dsum = 0
    vsum = int(S[v])
    tmpsum = 0

    for nex in lis[v]:
        if nex != p:
            tnm,tds,tvs = dfs(nex,v)
            vsum += tvs
            dsum += tds + tvs
            clis.append( (tnm+tvs , tds+tvs) )

    if len(clis) == 0:
        dic[(v,p)] = (dsum,dsum,vsum)
        return dsum,dsum,vsum

    ret = float("-inf")
    for i in range(len(clis)):
        ret = max(ret , clis[i][0] - dsum + clis[i][1] )
    if ret < 0:
        ret %= 2
    
    dic[(v,p)] = (ret,dsum,vsum)
    return ret,dsum,vsum
    

N = int(stdin.readline())
S = stdin.readline()
S = S[:-1]

lis = [ [] for i in range(N) ]
for i in range(N-1):
    a,b = map(int,stdin.readline().split())
    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

ans = float("inf")
for st in range(N):

    nmin,dsum,vsum = dfs(st,st)
    if nmin == 0 and dsum % 2 == 0:
        ans = min(ans,dsum//2)

#print (dic)
if ans == float("inf"):
    print (-1)
else:
    print (ans)



"""
import sys
from sys import stdin
sys.setrecursionlimit(3000)
dic = {}

def dfs(v,p):
    if (v,p) in dic:
        return dic[(v,p)]

    nmax = 0
    nsum = 0
    vsum = 0
    
    for nex in lis[v]:
        if nex != p:
            tnm,tns,tv = dfs(nex,v)
            nmax = max(nmax , tnm + tv)
            nsum += tns+tv
            vsum += tv
    vsum += int(S[v])
    dic[(v,p)] = (nmax,nsum,vsum)
    return dic[(v,p)]
            

N = int(stdin.readline())
S = stdin.readline()
S = S[:-1]

lis = [ [] for i in range(N) ]
for i in range(N-1):
    a,b = map(int,stdin.readline().split())
    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

ans = float("inf")
for st in range(N):

    nmax,nsum,vsum = dfs(st,st)

    #print (st+1,nmax,nsum,vsum)
    if nsum % 2 == 0 and nmax*2 <= nsum:
        ans = min(ans , nsum//2)

if ans == float("inf"):
    print (-1)
else:
    print (ans)
"""