Harryxun/stf_run huggingface dataset:
z,v,a=input,range,print
h,w,k=map(int,z().split())
r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)]
l=[[-1]*w for _ in v(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      if not((0<=(p:=x+e*i)<h)&(0<=(q:=y+f*i)<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)

### FIXED CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                #dp[x][y+j]=d
                cand.add((x,y+j))
                #now.append([x,y+j])
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                #dp[x][y-j]=d
                cand.add((x,y-j))
                #now.append([x,y-j])
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                #dp[x+j][y]=d
                cand.add((x+j,y))
                #now.append([x+j,y])
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                #dp[x-j][y]=d
                cand.add((x-j,y))
                #now.append([x-j,y])
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq
INF = float("inf")
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N = ii()
As = [map(lambda x : int(x) - 1, input().split())]

print(sum(As))

### FIXED CODE ###

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq
INF = float("inf")
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N = ii()
As = list(map(lambda x : int(x) - 1, input().split()))

print(sum(As))
#D
import math

a, b = map(int, input().split())

kouyaku = math.gcd(a, b)
#ruto = round(math.sqrt(kouyaku))
ans = 1

pn=[2];A=kouyaku
for L in range(3,A):
    chk=True
    for L2 in pn:
        if L%L2 == 0:chk=False
    if chk==True:pn.append(L)

for i in pn:
    if kouyaku % i == 0:
        ans += 1
print(ans)

### FIXED CODE ###

#D
import fractions

a, b = map(int, input().split())

kouyaku = fractions.gcd(a, b)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
import collections
c = collections.Counter(prime_factorize(kouyaku))
d =list(c.values())
print(len(d) +1)
import numpy as np

D = int(input())
c = np.array(list(map(int, input().split())))
s = np.array([list(map(int, input().split())) for x in range(D)])

l_opt = np.array(list(range(1, 27)) * (D // 26) + list(range(1, D % 26 + 1)))
l_max = s.argmax(axis=1) + 1

for day in range(1, D + 1):
    if 2 * s[l_opt[day - 1] - 1] < s[l_max[day - 1] - 1]:
        l_opt[day - 1] = l_max[day - 1]

for l in l_opt:
    print(l)

### FIXED CODE ###

import numpy as np

D = int(input())
c = np.array(list(map(int, input().split())))
s = np.array([list(map(int, input().split())) for x in range(D)])

l_opt = s.argmax(axis=1)
for l in l_opt:
    print(l + 1)
abc = map(int,input().split())
if len(abc) == len(set(abc)):
  print("No")
  exit()
print("Yes")abc = list(map(int, input().split()))
if len(abc) == len(set(abc)):
    print("No")
    exit()
print("Yes")


### FIXED CODE ###

abc = list(map(int, input().split()))
a = len(set(abc))
if len(set(abc)) == 2:
    print("Yes")
    exit()
print("No")
def main():
    n = input().split()
    if n[1] == '+':
        print(int(n[0]) + int(n[1]))
    else:
        print(int(n[0]) - int(n[1]))


if __name__ == "__main__":
    main()


### FIXED CODE ###


def main():
    n = input().split()
    if n[1] == '+':
        print(int(n[0]) + int(n[2]))
    else:
        print(int(n[0]) - int(n[2]))


if __name__ == "__main__":
    main()
import sys

def main():
    N = int(input())
    t = [0] * (N+1)
    x = [0] * (N+1)
    y = [0] * (N+1)
    for i in range(1, N+1):
        t[i], x[i], y[i] = map(int, input().split())
    
    flag = True
    for i in range(N):
        dt = t[i+1] - t[i]
        dist = abs(x[i+1] - x[i]) + abs(y[i+1] - y[i])
        if dt % 2 != dist % 2 || dt < dist:
            flag = False
            break
            
    print('Yes' if flag else 'No')
    
    

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    t = [0] * (N+1)
    x = [0] * (N+1)
    y = [0] * (N+1)
    for i in range(1, N+1):
        t[i], x[i], y[i] = map(int, input().split())
    
    flag = True
    for i in range(N):
        dt = t[i+1] - t[i]
        dist = abs(x[i+1] - x[i]) + abs(y[i+1] - y[i])
        if dt % 2 != dist % 2 or dt < dist:
            flag = False
            break
            
    print('Yes' if flag else 'No')
    
    

if __name__ == '__main__':
    main()
N = input()
a = []
for i in range(N):
    a.append(input())
for i in range(3):
    m = max(a)
    a.remove(m)
    print (m)


### FIXED CODE ###

import sys
e = [int(i) for i in sys.stdin.readlines()]
for i in range(3):
    m = max(e)
    e.remove(m)
    print (m)
N = input()
K = int(input())

def K1(N):
  le = len(N)
  if le == 1:
    return int(N)
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    return 0
  else:
    j=1
    for i in range(le-1):
      if int(N[i+1]) == 0:
        j+=1
      
    n = N[j:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    return 0
  else:
    j=1
    for i in range(le-1):
      if int(N[i+1]) == 0:
        j+=1
    n2 = N[j:le]
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))
  

### FIXED CODE ###

N = input()
K = int(input())

def K1(N):
  le = len(N)
  if le == 1:
    return int(N)
  else:
    return 9*(le-1)+int(N[0])
def K2(N):
  le = len(N)
  if le == 1:
    return 0
  else:
    j=1
    if int(N[j]) == 0 and j != le-1:
      while int(N[j]) == 0:
        j+=1
        if j == le-1:
          break
        
    n = N[j:le]
    return (9**2)*((le-1)*(le-2)//2) + K1(n) +(int(N[0])-1)*K1("9"*(le-1))
  
def K3(N):
  le = len(N)
  if le == 1 or le == 2:
    return 0
  else:
    j=1
    if int(N[j]) == 0 and j != le-1:
      while int(N[j]) == 0:
        j+=1
        if j == le-1:
          break
        
    n2 = N[j:le]
    
    return (9**3)*((le-1)*(le-2)*(le-3)//6) + K2(n2) + (int(N[0])-1)*K2("9"*(len(N)-1))
if K == 1:
  print(K1(N))
    
if K == 2:
  print(K2(N))
  
if K == 3:
  print(K3(N))
n = int(input())

score_taro, score_hanako = 0, 0
for _ in range(n):
    card_taro, card_hanako = input().split()

    if card_taro == card_hanako:            # DRAW
        score_taro += 1
        score_hanako += 1
        #print("draw")#
        continue
    for i in range(n):
        if ord(card_taro[i:i+1]) > ord(card_hanako[i:i+1]):         # TARO WIN
            score_taro += 3
            #print("taro win")#
            break
        if ord(card_taro[i:i+1]) < ord(card_hanako[i:i+1]):         # HANAKO WIN
            score_hanako += 3
            #print("hanako win")#
            break
        if ord(card_taro[i:i+1]) == ord(card_hanako[i:i+1]):        # NEXT CHAR
            continue

print("{0} {1}".format(score_taro, score_hanako))

### FIXED CODE ###

n = int(input())

score_taro, score_hanako = 0, 0
for _ in range(n):
    card_taro, card_hanako = input().split()

    point_taro = 0
    point_hanako = 0
    if card_taro == card_hanako:
        score_taro += 1
        score_hanako += 1
        continue
    for i in range(min(len(card_taro), len(card_hanako))):
        if len(card_taro) > len(card_hanako):
            point_taro = 3
        elif len(card_taro) < len(card_hanako):
            point_hanako = 3
        if ord(card_taro[i:i+1]) > ord(card_hanako[i:i+1]):
            point_taro = 3
            point_hanako = 0
            break
        if ord(card_taro[i:i+1]) < ord(card_hanako[i:i+1]):
            point_taro = 0
            point_hanako = 3
            break
    score_taro += point_taro
    score_hanako += point_hanako
print("{0} {1}".format(score_taro, score_hanako))
import math
r=int(input())
area1=pi
arear=pi*pow(r,2)
ratio=int(arear/area1)
print(ratio)

### FIXED CODE ###

r=int(input())
print(r*r)
v = input()
 if v % 9 == 0
     print('Yes')
 else:
     print('No')

### FIXED CODE ###

s=int(input())
if s%9==0:
    print("Yes")
else:
    print("No")
import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  count = 0
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    if s1 < count:
      continue
    count = s1+1
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (s1+1, i))
      ans[i] = s2
      subindex = i
    index = subindex
      
  
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
  
    print(*answer)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  count = 0
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    if s1 < count:
      continue
    count = s1+1
    subindex = index
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (count, i))
      ans[i] = s2
      subindex = i
    index = subindex
      
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
  
    print(*answer)
  
if __name__ == "__main__":
  main()
import sys
input=sys.stdin.readline
#for _ in range(int(input())):
#	n=int(input())
#	n,m=map(int,input().split())
#	s=input().strip()

def dfs(i):
	if dp[i]!=-1:return dp[i]
	c=0
	for j in v[i]:c=max(c,dfs(j)+1)
	dp[i]=c
	return c

n,m=map(int,input().split())
v=[[] for i in range(n+1)]
for i in range(m):
	x,y=map(int,input().split())
	v[x].append(y)
dp = [-1]*(n+1) 
m=0
for i in range(1,n+1):
	m=max(m,dfs(i))
print(m)

### FIXED CODE ###

import sys
input=sys.stdin.readline
#for _ in range(int(input())):
#	n=int(input())
#	n,m=map(int,input().split())
#	s=input().strip()
sys.setrecursionlimit(10**9)
def dfs(i):
	if dp[i]!=-1:return dp[i]
	c=0
	for j in v[i]:c=max(c,dfs(j)+1)
	dp[i]=c
	return c

n,m=map(int,input().split())
v=[[] for i in range(n+1)]
for i in range(m):
	x,y=map(int,input().split())
	v[x].append(y)
dp = [-1]*(n+1) 
m=0
for i in range(1,n+1):
	m=max(m,dfs(i))
print(m)
l = map(int(input(), 16).split())

if l[0] < l[1]:
  print("<")
elif l[0] = l[1]:
  print ("=")
elif l[0] > l[1]:
  print(">")


### FIXED CODE ###

l = input().split()
l2 = [int(s, 16) for s in l]

if l2[0] < l2[1]:
  print("<")
elif l2[0] == l2[1]:
  print ("=")
elif l2[0] > l2[1]:
  print(">")
n=int(input())
a=int(input())
print('Yes' if n%500 =< a else 'No')

### FIXED CODE ###

n=int(input())
a=int(input())
print('Yes' if n%500 <= a else 'No')
# encoding: utf-8
n, a = map(int, raw_input().split())
if n>10**7 or a >= 10**7:
    exit(1)

memo = [-1]*(n+1)
# 残りx個を貯めるために最小の時間を返す予定
def dfs(x):
    if x == 0:
        return 0
    if memo[x] != -1:
        return memo[x]
    i = 0
    res = x
    for i in xrange(2, x+1):
        # i-sec待つ
        res = min(res, dfs((x+i-1)/i)+a+i)
    memo[x] = res
    return memo[x]
print dfs(n)


### FIXED CODE ###

# seishin.py
N, A = map(int, input().split())

ans = N
if N > 1:
    for k in range(1, 41):
        left = 0; right = N+1
        while left+1 < right:
            mid = (left + right) // 2
            if mid**(k+1) < N:
                left = mid
            else:
                right = mid
        m = right
        v = (m-1)**(k+1)
        for i in range(k+1):
            v //= m-1
            v *= m
            if N <= v:
                ans = min(ans, A*k + (m-1)*(k+1) + (i+1))
                break
print(ans)
n = int(input())
arrayP = [int(s) for s in input().split()]

cnt = 0

for i in range(0, n-2):
    threeNums = arrayP[i:i+3].sort()
    if threeNums[1] == arrayP[i+1]:
        cnt += 1

print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
arrayP = [int(s) for s in input().split()]
 
cnt = 0
 
for i in range(0, n-2):
    threeNums = arrayP[i:i+3]
    threeNums.sort()
    if threeNums[1] == arrayP[i+1]:
        cnt += 1
 
print(cnt)
x=str(input())
n=x.split(" ", 2)
a=n[0]
b=n[1]
ab=a*b
a_b=(a+b)*2
print('ab', end=' ')
print('a_b')

### FIXED CODE ###

x=str(input())
n=x.split(" ", 2)
a=int(n[0])
b=int(n[1])
ab=a*b
a_b=(a+b)*2
print(ab, end=' ')
print(a_b)
N, K = list(map(int, input().split()))
h = []
for i in range(N):
    h.append(int(input()))
else:
    h.sort()

hi = []
i = 0
while i + (K - 1) < N:
    hi.append(int(h[i + 2] - h[i]))
    i += 1

print(min(hi))


### FIXED CODE ###

N, K = list(map(int, input().split()))
h = []
for i in range(N):
    h.append(int(input()))
else:
    h.sort()

hi = []
i = 0
while i + (K - 1) < N:
    hi.append(int(h[i + (K - 1)] - h[i]))
    i += 1

print(min(hi))
n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
			new_now=pair[now][i][0]
	now=new_now
	stack.remove(now)
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)



### FIXED CODE ###

n=int(input())
dis=[10**15]*n
dis[0]=0
pair=[[]for _ in range(n)]
for i in range(n-1):
	a,b,c=map(int,input().split())
	pair[a-1].append([b-1,c])
	pair[b-1].append([a-1,c])
now=0
stack=set()
cnt=n-1
while cnt!=0:
	for i in range(len(pair[now])):
		if dis[pair[now][i][0]]==10**15:
			dis[pair[now][i][0]]=dis[now]+pair[now][i][1]
			stack.add(pair[now][i][0])
	now=stack.pop()
	cnt-=1
for i in range(n):
	if dis[i]%2==0:
		print(0)
	else:
		print(1)
N = int(input())
x = []
y = []
for i in range(N):
    new_x, new_y = map(int, input().split())
    x.append(new_x)
    y.append(new_y)

dist_list = []
count_list = []
for i in range(N):
    for j in range(i+1, N):
        p = x[i] - x[j]
        q = y[i] - y[j]
        for index, dist in enumerate(dist_list):
            x_dist, y_dist= dist
            if (x_dist == p and y_dist == q) or (x_dist == -p and y_dist == -q):
                dist_list[index] = [x_dist, y_dist]
                count_list[index] += 1
                break
        else:
            dist_list.append([p, q])
            count_list.append(1)

print(N - max(count_list))

### FIXED CODE ###

N = int(input())
x = []
y = []
for i in range(N):
    new_x, new_y = map(int, input().split())
    x.append(new_x)
    y.append(new_y)

dist_list = []
count_list = []
for i in range(N):
    for j in range(i+1, N):
        p = x[i] - x[j]
        q = y[i] - y[j]
        for index, dist in enumerate(dist_list):
            x_dist, y_dist= dist
            if (x_dist == p and y_dist == q) or (x_dist == -p and y_dist == -q):
                count_list[index] += 1
                break
        else:
            dist_list.append([p, q])
            count_list.append(1)

if N == 1:
    print(1)
else:
    print(N - max(count_list))
s = input()
a = 'abcdefghijklmnopqrstuvwxyz'
ans = ''
if len(s) < 26:
    for w in a:
        if not w in s:
            ans = s + w
            break
elif s == 'zyxwvutsrqponmlkjihgfedcba':
    ans = '-1'
else:
    l = list(a)
    l.sort(reverse=True)
    l = ''.join(l)
    ele = 0
    for i in range(len(s)):
        if l[:i] == s[-i:]:
            ele = i
    if ele < 25:
        t = s[:-(ele+1)]
        u = l[:ele]+s[-(ele+1):-(ele)]
        u2 = sorted(u)
        ans = t + u2[1]
'''
        for w in a:
            if not w in t and t + w != s[:-ele]:
                ans = t + w
                break
'''
print(ans)

### FIXED CODE ###

s = input()
a = 'abcdefghijklmnopqrstuvwxyz'

if len(s) < 26:
    for w in a:
        if not w in s:
            print(s + w)
            exit()

if len(s) == 26:
    for i in range(len(s)-2, -1, -1):
        for j in range(len(s)-1, i, -1):
            if s[i] < s[j]:
                print(s[:i]+s[j])
                exit()

print('-1')
while True:
    n=input()
    if n==0:
        break
    s=list(n)
    a=[int(i) for i in s]
    print(sum(a))


### FIXED CODE ###

while True:
    n=input()
    if n=='0':
        break
    s=list(n)
    a=[int(i) for i in s]
    print(sum(a))
import re
while 1:
	n,m = map(int,raw_input().split())
	P = []; D = []
	for i in range(n):
		p,s,d = raw_input().replace("?","[0-9]").split()
		r = re.compile(s+d)
		if p[0] == "p":
			P.append(r)
		else:
			D.append(r)
	for i in range(m):
		s,d,name = raw_input().split()
		tf = any(r.search(s+d) for r in P) and not any(r.search(s+d) for r in D)
		if tf:
			print s,d,name

### FIXED CODE ###

import re
while 1:
	n,m = map(int,raw_input().split())
	if n == m == 0: break
	R = [0]*n
	for i in range(n):
		p,s,d = raw_input().replace("?","[0-9]").split()
		R[i] = [re.compile(s+d), p[0] == "p"]
	ans = []
	for i in range(m):
		s,d,name = raw_input().split()
		for r,p in R[::-1]:
			if r.search(s+d):
				if p: ans.append([s,d,name])
				break
	print len(ans)
	for s,d,name in ans:
		print s,d,name
import math

def main():
  n = int(input())
  a = list(map(int, input().split()))

  right = []
  left  = []

  right.append(a[0])
  left.append(a[-1])

  for i in range(1, len(a)-1):
    right.append(math.gcd(right[i-1], a[i]))
    left.append(math.gcd(left[i-1], a[len(a)-i-1]))
  
  ans = max(right[-1], left[-1])
  
  for i in range(len(right)-1):
    ans = max(ans, math.gcd(right[0], left[len(left)-2-i]))
    
  print(ans)
  
main()

### FIXED CODE ###

import fractions

def main():
  n = int(input())
  a = list(map(int, input().split()))

  right = []
  left  = []

  right.append(a[0])
  left.append(a[-1])

  for i in range(1, len(a)-1):
    right.append(fractions.gcd(right[i-1], a[i]))
    left.append(fractions.gcd(left[i-1], a[-i-1]))
  
  ans = max(right[-1], left[-1])
  
  for i in range(len(right)-1):
    ans = max(ans, fractions.gcd(right[i], left[-i-2]))
    
  print(ans)
  
main()
from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip() 
def main():
    moji=input()
    d=deque(moji)
    cycle=int(input())
    flont_or_back=0
    for i in range(cycle):
        line=input()
        if line[0]=="1":
            flont_or_back+=1
        else:
            fi=line[2]
            ci=line[4]
            if flont_or_back%2==0:
                if fi=="1":
                    d.appendleft(ci)
                else:
                    d.append(ci)
            else:
                if fi=="1":
                    d.append(ci)
                else:
                    d.appendleft(ci)
    if flont_or_back%2==0:
        print("".join(d))
    else:
        print("".join(d[::-1]))

if __name__ == '__main__':
    main() 
    


### FIXED CODE ###

def main():
    moji=input()
    cycle=int(input())
    flont_or_back=0
    flont=""
    back=""
    for i in range(cycle):
        line=input()
        if line[0]=="1":
            flont_or_back+=1
        else:
            fi=line[2]
            ci=line[4]
            if flont_or_back%2==0:
                if fi=="1":
                    flont=ci+flont
                else:
                    back+=ci
            else:
                if fi=="1":
                    back+=ci
                else:
                    flont=ci+flont
    moji=flont+moji+back
    if flont_or_back%2==0:
        print(moji)
    else:
        print(moji[::-1])
    

if __name__ == '__main__':
    main()
n = int(input())
s = "Q"+input()
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
ans = 10**18
for root in range(1,n+1):
  stack = []
  group = [-1 for i in range(n+1)]
  dist = [0 for i in range(n+1)]
  group[root] = 0
  cnt = 1
  for y in graph[root]:
    stack.append(y)
    group[y] = cnt
    dist[y] = 1
    cnt += 1
  table = [0 for i in range(cnt)]
  while stack:
    x = stack.pop()
    if s[x] == "1":
      table[group[x]] += dist[x]
    for y in graph[x]:
      if group[y] == -1:
        group[y] = group[x]
        dist[y] = dist[x]+1
        stack.append(y)
  sm = sum(table)
  if sm%2 == 0 and max(table)*2 <= sm:
    ans = min(ans,sm//2)
if ans == 10**18:
  print(2/0)
  print(-1)
else:
  print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = "Q"+input()
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
leaf = set()
for i in range(1,n+1):
  if deg[i] == 1:
    leaf.add(i)
if s.count("1") == 1:
  print(0)
  exit()
ans = 10**18
for root in range(1,n+1):
  degr = deg[:]
  degr[root] += 1
  if root in leaf:
    continue
  stack = list(leaf)
  dpn = [[] for i in range(n+1)]
  dpmn = [[] for i in range(n+1)]
  dpmx = [[] for i in range(n+1)]
  info = [[0,0,0] for i in range(n+1)]
  for i in leaf:
    if s[i] == "1":
      info[i][0] += 1
  vis = set(i for i in leaf)
  anstmp = 0
  while stack:
    x = stack.pop()
    if dpn[x]:
      if len(dpn[x]) == 1:
        num = dpn[x][0]
        info[x] = [num,dpmn[x][0]+num,dpmx[x][0]+num]
        if s[x] == "1":
          info[x][0] += 1
      else:
        info[x][0] = sum(dpn[x])
        info[x][2] = sum(dpmx[x])+info[x][0]
        mxv = -1
        mxind = -1
        for i in range(len(dpmn[x])):
          if mxv < dpmn[x][i]+dpn[x][i]:
            mxv = dpmn[x][i]+dpn[x][i]
            mxind = i
        cnst = mxv-info[x][2]+dpmx[x][mxind]+dpn[x][mxind]
        info[x][1] = max(0,cnst%2,cnst)
        if s[x] == "1":
          info[x][0] += 1
    for y in graph[x]:
      if y not in vis:
        dpn[y].append(info[x][0])
        dpmn[y].append(info[x][1])
        dpmx[y].append(info[x][2])
        degr[y] -= 1
        if degr[y] == 1:
          vis.add(y)
          stack.append(y)
  if info[root][1] == 0:
    ans = min(ans,info[root][2]//2)
if ans == 10**18:
  print(-1)
else:
  print(ans)