Harryxun/stf_run huggingface dataset:
def wa(h, w, f):
    if not (0 <= h <= H-1 and 0 <= w <= W-1):
        return
    elif mapp[h][w] != f:
        return
    else:
        mapp[h][w] = '$'
        wa(h, w+1, f)
        wa(h-1, w, f)
        wa(h, w-1, f)
        wa(h+1, w, f)

while True:
    H, W = map(int, raw_input().split(' '))
    if H == 0 and W == 0: break
    mapp = []
    for i in range(H):
        mapp.append(list(raw_input()))
    count = 0
    for h in range(H):
        for w in range(W):
            if mapp[h][w] == '@':
                wa(h, w, '@')
            elif mapp[h][w] == '#':
                wa(h, w, '#')
            elif mapp[h][w] == '*':
                wa(h, w, '*')
            else:
                continue
            count += 1
    else:
        print count

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)
def wa(h, w, f):
    if not (0 <= h < H and 0 <= w < W):
        return
    elif mapp[h][w] != f:
        return
    else:
        mapp[h][w] = '$'
        wa(h, w+1, f)
        wa(h-1, w, f)
        wa(h, w-1, f)
        wa(h+1, w, f)

while True:
    H, W = map(int, raw_input().split())
    if H == 0 and W == 0: break
    mapp = [list(raw_input()) for i in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if mapp[h][w] == '@':
                count += 1
                wa(h, w, '@')
            elif mapp[h][w] == '#':
                count += 1
                wa(h, w, '#')
            elif mapp[h][w] == '*':
                count += 1
                wa(h, w, '*')
    else:
        print count
K = (int(i) for i in input().split())
if K % 2 == 0:
    A = (K / 2) * (K / 2)
    print(A)
else:
    B = ((K / 2) + 1) * (K / 2)
    print(B)

### FIXED CODE ###

K = int(input())
if K % 2 == 0:
    A = (K // 2) * (K // 2)
    print(A)
else:
    B = ((K // 2) + 1) * (K // 2)
    print(B)
import numpy as np
import sys
H, W, M = map(int, input().split())
d = np.zeros((H, W), dtype=np.int64)

for _ in range(M):
    h, w = map(int, input().split())
    d[h-1, w-1] = 1
print(1)
tate = np.sum(d, axis=0)
yoko = np.sum(d, axis=1)
tate_max = tate.max()
yoko_max = yoko.max()

ans_tate, ans_yoko = [], []

for i in range(W):
    if tate[i] == tate_max:
        ans_tate.append(i)

for i in range(H):
    if yoko[i] == yoko_max:
        ans_yoko.append(i)

for h in ans_yoko:
    for w in ans_tate:
        if not d[h, w]:
            print(tate_max+yoko_max)
            sys.exit()
print(tate_max+yoko_max-1)

### FIXED CODE ###

import sys
H, W, M = map(int, input().split())
h_list, w_list = [0]*H, [0]*W
check = set()
for _ in range(M):
    h, w = map(int, input().split())
    check.add((h-1, w-1))
    h_list[h-1] += 1
    w_list[w-1] += 1
h_max, w_max = max(h_list), max(w_list)
h_bom = [i for i in range(H) if h_list[i]==h_max]
w_bom = [i for i in range(W) if w_list[i]==w_max]
for h in h_bom:
    for w in w_bom:
        if not (h, w) in check:
            print(h_max+w_max)
            sys.exit()
print(h_max+w_max-1)
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
memo_yoko = [False]*w
memo_tate = [False]*h
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            memo_yoko[i] = True
            memo_tate[j] = True

for i in range(h):
    if memo_yoko[i]:
        for j in range(w):
            if memo_tate[j]:
                print(a[i][j], end="")
        print()

### FIXED CODE ###

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
memo_yoko = []
memo_tate = []
for i in range(h):
    if "#" in a[i]:
        memo_yoko.append(i)

for j in range(w):
    if any(a[i][j] == "#" for i in range(h)):
        memo_tate.append(j)
#print(memo_yoko)
#rint(memo_tate)
for i in memo_yoko:
    for j in memo_tate:
        print(a[i][j], end="")
    print()
N,M = map(int,input().split())
PY = [list(map(int,input().split())) for _ in range(M)]
for i in range(M):
    PY[i].append(i)
PY.sort(key=lambda x:x[1])
ans = [0]*M
num = [0]*max(N,M)
for p,y,i in PY:
    ans[i] = str(p).zfill(6) + str(num[p]+1).zfill(6)
    num[p] += 1
for s in ans:print(s)

### FIXED CODE ###

N,M = map(int,input().split())
PY = [list(map(int,input().split())) for _ in range(M)]
for i in range(M):
    PY[i].append(i)
PY.sort(key=lambda x:x[1])
ans = [0]*M
num = [0]*N
for p,y,i in PY:
    ans[i] = str(p).zfill(6) + str(num[p-1]+1).zfill(6)
    num[p-1] += 1
for s in ans:print(s)
import numpy as np

N = int(input())
A = list(map(int,input().split()))

ans = np.zeros(N)

for i in range(N):
    ans[A[i]-1] = i+1

for i in range(N):
    print(int(ans[i]), sep=' ', end=' ')

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = [0]

for i in range(N-1):
    ans.append(0)

for i in range(N):
    ans[A[i]-1] = i+1

for i in range(N):
    print(int(ans[i]), end=' ')
N = int(input())

dic = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

old = ["a"]
new = []
for i in range(1, N):
    print(old)
    for word in old:
        for j in range(i+1):
            if word[-1] == dic[j] or word[-1] == dic[j-1]:
                new.append(word+dic[j])
    old = new.copy()
    new = []
for i in old:
    print(i)


### FIXED CODE ###

N = int(input())

S = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

def dfs(s, i):
    if len(s) == N:
        return [s]
    result = []
    for j in range(i+1):
        if j == i:
            result += dfs(s+S[j], i+1)
        else:
            result += dfs(s+S[j], i)
    return result
print("\n".join(dfs("", 0)))
n=int(input())
l=list(map(int,input().split()))
tl=[l[0]]
for i in range(1,n):
    if l[i]!=l[i-1] and l[i]!=0:
        tl.append(l[i])


a=[]
ma=False

for i in range(len(tl)):
    if i==0:
        if tl[i]>tl[i+1]:
            ma=True
            a.append(tl[i])
        else:
            ma=False
            a.append(tl[i])
    elif i==len(tl)-1:
        if tl[i]>tl[i-1]:
            a.append(tl[i])
        else:
            a.append(tl[i])
    else:
        if tl[i-1]<tl[i] and tl[i+1]<tl[i]:
            a.append(tl[i])
        elif tl[i-1]>tl[i] and tl[i+1]>tl[i]:
            a.append(tl[i])

if ma:
    a.pop(0)


num=0
ans=1000

for i in range(0,len(a)-1,2):
    
    thing1=(ans//a[i])*a[i+1]
    thing2=num*a[i+1]
    if thing1>thing2:
        ans=thing1+ans%a[i]
        num=0
        
    elif thing2>thing1:
        ans=thing2

print(ans)
            
            
        

    


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
tl=[l[0]]
for i in range(1,n):
    if l[i]!=l[i-1]:
        tl.append(l[i])


a=[]
ma=False

for i in range(len(tl)):
    if len(tl)==1:
        break
    if i==0:
        if tl[i]>tl[i+1]:
            ma=True
            a.append(tl[i])
        else:
            ma=False
            a.append(tl[i])
    elif i==len(tl)-1:
        if tl[i]>tl[i-1]:
            a.append(tl[i])
        else:
            a.append(tl[i])
    else:
        if tl[i-1]<tl[i] and tl[i+1]<tl[i]:
            a.append(tl[i])
        elif tl[i-1]>tl[i] and tl[i+1]>tl[i]:
            a.append(tl[i])

if ma:
    a.pop(0)


num=0
ans=1000

for i in range(0,len(a)-1,2):
    
    thing1=(ans//(a[i]))*a[i+1]
    thing2=num*a[i+1]
    if thing1>thing2:
        ans=thing1+ans%a[i]
        num=0
        
    elif thing2>thing1:
        ans=thing2

print(ans)
list(map(int,input().split()))

### FIXED CODE ###

s = input()

if ('A' in s) and ('B' in s):
    print('Yes')
else:
    print('No')
dat =list(input().split())

for i in dat:
	i = int(i)

dat.sort(reverse=True)

asum = 0
bsum = 0
sum=0

for i in range(len(dat)):
     if i % 2 == 0:
         asum = asum + dat[i]
      else:
         bsum = bsum + dat[i]
		
print(asum-bsum)

### FIXED CODE ###

n = int(input())
dat = list(input().split())

dat = list(map(int,dat))

dat.sort(reverse=True)

asum = 0
bsum = 0

for i in range(n):
	if i % 2 == 0:
		asum = asum + dat[i]
	else:
		bsum = bsum + dat[i]
		
print(asum-bsum)
A=[chr(i) for i in range(65, 65+26)]
N=int(input())
S=str(input())

for i in range(len(S)):
  k=(A.index(S[i])+N)%26
  S[i]=S[k]
  
print(S)

### FIXED CODE ###

A=[chr(i) for i in range(65, 65+26)]
N=int(input())
S=str(input())
T=[]
U=str()

for i in range(len(S)):
  k=(A.index(S[i])+N)%26
  T.append(A[k])
  U=U+str(T[i])
  
print(U)
N = int(input())
A=[list(map(int, input().split())) for i in range(N)]
num = 0
zoro = 0
while num < N:
  if A[num][0] ==A[num][1]:
    num +=1
    zoro +=1 
  else:
    num +=1
    if zoro >2:
      zoro = zoro
    else:
      zoro = 0
if zoro >2 :
  print("Yes")
else:
  print("No")

### FIXED CODE ###

text = input()
tend = len(text)
text2 = ""
if text[len(text)-1:len(text)] == "s":
    text2 = text +'es'
else:
    text2 = text +'s'
print(text2)
from scipy.special import comb

x, y = map(int,input().split())

if not((x + y) % 3 == 0):
    print(0)
elif (x > 2*y) or (y > 2 * x):
    print(0)
else:
    k = (x + y) // 3
    i = x - k
    print(comb(k, i, exact=True))

### FIXED CODE ###


# Python3 function to  
# calculate nCr % p 
def ncr(n, r, p): 
    # initialize numerator 
    # and denominator 
    num = den = 1 
    for i in range(r): 
        num = (num * (n - i)) % p 
        den = (den * (i + 1)) % p 
    return (num * pow(den,  
            p - 2, p)) % p 


x, y = map(int,input().split())

if not((x + y) % 3 == 0):
    print(0)
elif (x > 2*y) or (y > 2 * x):
    print(0)
else:
    k = (x + y) // 3
    i = x - k
    print(ncr(k, i, 10 ** 9 + 7))
import random


class Cube:
    def __init__(self, u, s, e, w, n, d):
        self.u = u
        self.s = s
        self.e = e
        self.w = w
        self.n = n
        self.d = d

    def rotate(self, dic):
        if dic == "N":
            tmp = self.u
            self.u = self.s
            self.s = self.d
            self.d = self.n
            self.n = tmp
        elif dic == "E":
            tmp = self.u
            self.u = self.w
            self.w = self.d
            self.d = self.e
            self.e = tmp
        elif dic == "W":
            tmp = self.u
            self.u = self.e
            self.e = self.d
            self.d = self.w
            self.w = tmp
        else:
            tmp = self.u
            self.u = self.n
            self.n = self.d
            self.d = self.s
            self.s = tmp


def main():
    u, s, e, w, n, d = map(int, input().split())
    cube = Cube(u, s, e, w, n, d)
    q = int(input())
    for i in range(q):
        upper, front = map(int, input().split())
        while True:
            cube.rotate(random.choice("NWES"))
            if upper == cube.u and front == cube.s:
                print(cube.e)
                break


if __name__ == '__main__':
    main(


### FIXED CODE ###

import random


class Cube:
    def __init__(self, u, s, e, w, n, d):
        self.u = u
        self.s = s
        self.e = e
        self.w = w
        self.n = n
        self.d = d

    def rotate(self, dic):
        if dic == "N":
            tmp = self.u
            self.u = self.s
            self.s = self.d
            self.d = self.n
            self.n = tmp
        elif dic == "E":
            tmp = self.u
            self.u = self.w
            self.w = self.d
            self.d = self.e
            self.e = tmp
        elif dic == "W":
            tmp = self.u
            self.u = self.e
            self.e = self.d
            self.d = self.w
            self.w = tmp
        else:
            tmp = self.u
            self.u = self.n
            self.n = self.d
            self.d = self.s
            self.s = tmp


def main():
    u, s, e, w, n, d = map(int, input().split())
    cube = Cube(u, s, e, w, n, d)
    q = int(input())
    for i in range(q):
        upper, front = map(int, input().split())
        while True:
            cube.rotate(random.choice("NWES"))
            if upper == cube.u and front == cube.s:
                print(cube.e)
                break


if __name__ == '__main__':
    main()
def d170(n,a):
    count=0
    sa=sorted(a)
    dp=[True for i in range(n)]
    if sa[0]==1:
        if 1 in t:
            return 0
        else:
            return 1
    else:
        for i in range(n):
            if dp[i]:
                for j in range(i+1,n):
                    if dp[j]:
                        if sa[j]%sa[i]==0:
                            dp[j]=False
        return dp.count(True)
    
n=int(input())
a= list(map(int, input().split()))    
print(d170(n,a))
            

### FIXED CODE ###

def d170(n,a):
    k=max(a)+1
    count=0
    dp=[0 for i in range(k)]
    for x in a:
        if dp[x]!=0:
                dp[x]=2
                
        else:
            for j in range(x,k,x):
                     dp[j]+=1
    for x in a:
        if dp[x]==1:
            count+=1
    return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))
n = int(input())
a = list(map,(int,input().split()))
a.sort()
c = int(a[-1])
if n%2 == 0:
  n1 = n//2-1
  for i in range(n1):
    a1 = int(a[n-2-i])
    c += a1*2
else:
  n2 = n//2
  a3 = int(a[n-n2-1])
  c += a3
  for i in range(n2-1):
    a2 = int(a[n-2-i])
    c += a2*2
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
c = a[-1]
if n%2 == 0:
  n1 = n//2-1
  for i in range(n1):
    a1 = a[n-2-i]
    c += a1*2
else:
  n2 = n//2
  a3 = a[n-n2-1]
  c += a3
  for i in range(n2-1):
    a2 = a[n-2-i]
    c += a2*2
print(c)
h,n=map(int,input().split())

ab=[]
dp=[10**9]*(h*2)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    ab.append((a,b))
    dp[a]=b
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)



    
    



### FIXED CODE ###

h,n=map(int,input().split())

ab=[]
dp=[10**9]*(10**5)

maxA=0
for _ in range(n):
    a,b=map(int,input().split())
    dp[a]=min(dp[a],b)
    maxA=max(maxA,a)
#print(dp)
#dp[a]は、相手にaダメージを与えるときの、消耗する自分の最小HP
result=10**9
for i in range(1,h+maxA):
    #print(i,"##########")
    for k in range(1,i//2+2):
        dp[i]=min(dp[i],dp[k]+dp[i-k])
    if i>=h:
        result=min(result,dp[i])
    #print(dp)
print(result)
a,b,c=input().split
if b=="-":
  print(int(a)-int(c))
else:
  print(int(a)+int(c))


### FIXED CODE ###

print(eval(input()))
a,b=map(int,input().split())
cnt=0
for l in range(a,b+1):
            l_i=list(str())
            if l_i[0]==l_i[-1] and l_i[1]=l_i[-2]:
                        cnt+=1
print(cnt)                        


### FIXED CODE ###

a,b=map(int,input().split())
cnt=0
for l in range(a,b+1):
            l_i=list(str(l))
            if l_i[0]==l_i[-1] and l_i[1]==l_i[-2]:
                        cnt+=1
print(cnt)
N = int(input())
L0 = 2
L1 = 1
if N == 1:
    print(L1)

for i in range(1,N):
    res = L0 + L1
    L0 = L1
    L1 = res

print(res)

### FIXED CODE ###

N = int(input())
L0 = 2
L1 = 1
if N == 1:
    print(L1)
    exit()

for i in range(1,N):
    res = L0 + L1
    L0 = L1
    L1 = res

print(res)
N = int(input())

A = [0] * (N + 1)
B = [0] * (N + 1)
C = [0] * (N + 1)

for i in range(1, N + 1):
    A[i], B[i], C[i] = map(int, input().split())

dp = [[0] * 3 for _ in range(N + 1)]#N+1
for i in range(1, N + 1):
    dp[i][0] = A[i] + max(dp[i-1][1], dp[i-1][2])#dp[i][0]=i日目でaを選んだ時の最大値＝i-1日目でbかcを選んだ時の最大値+ai
    dp[i][1] = B[i] + max(dp[i-1][2], dp[i-1][0])
    dp[i][2] = C[i] + max(dp[i-1][0], dp[i-1][1])

print(max(dp[N]))#Nの時の最大

### FIXED CODE ###

#　最小値を求めるDP　
#　Atcoder DP まとめコンテスト「A.Frog」　https://atcoder.jp/contests/dp/tasks/dp_a

N = int(input())
h = [int(x) for x in input().split()]

inf = float('inf')
dp = [inf] * N

dp[0] = 0
dp[1] = abs(h[1] - h[0]) #　1、２の初期値を設定

def chmin(a, b):
    if a > b:
        return b
    else:
        return a

for i in range(2, N):
    dp[i] = chmin(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    dp[i] = chmin(dp[i], dp[i-2] + abs(h[i] - h[i-2]))

print(dp[N - 1])
a,b=int(input().split())
print("Yes" if a==b else "No")

### FIXED CODE ###

a,b=map(int,input().split())
print("Yes" if a==b else "No")
# -*- coding: utf-8 -*-
"""
D - Handstand
https://atcoder.jp/contests/abc124/tasks/abc124_d

"""
import sys


from itertools import groupby
from collections import deque

def solve(N, K, S):
    seq = [[k, len(list(g))]  for k, g in groupby(S)]
    if len(seq) <= 2*K:
        return len(S)
    if seq[0][0] == '0':
        seq = [['1', 0]] + seq
    if len(seq) % 2 == 0:
        seq.append(['1', 0])

    seq = deque(seq)
    rem = deque()
    ans = 0
    for i in range(2*K+1):
        _, v = seq.popleft()
        ans += v
        rem.append(v)

    max_ans = ans
    while seq:
        ans -= rem.popleft()
        ans -= rem.popleft()
        _, v = seq.popleft()
        ans += v
        _, v = seq.popleft()
        ans += v
        max_ans = max(max_ans, ans)
    return max_ans


def main(args):
    N, K = map(int, input().split())
    S = input()
    ans = solve(N, K, S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
D - Handstand
https://atcoder.jp/contests/abc124/tasks/abc124_d
WA
"""
import sys


from itertools import groupby
from collections import deque

def solve(N, K, S):
    seq = [[k, len(list(g))]  for k, g in groupby(S)]
    if len(seq) <= 2*K:
        return len(S)
    if seq[0][0] == '0':
        seq = [['1', 0]] + seq
    if len(seq) % 2 == 0:
        seq.append(['1', 0])

    seq = deque(seq)
    rem = deque()
    ans = 0
    for i in range(2*K+1):
        _, v = seq.popleft()
        ans += v
        rem.append(v)

    max_ans = ans
    while seq:
        _, v = seq.popleft()
        ans += v
        rem.append(v)
        ans -= rem.popleft()
        _, v = seq.popleft()
        ans += v
        rem.append(v)
        ans -= rem.popleft()
        max_ans = max(max_ans, ans)
    return max_ans


def main(args):
    N, K = map(int, input().split())
    S = input()
    ans = solve(N, K, S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
w = a.index(1)
if w<k or n-w-1<k:
  print( math.ceil((n-1)/(k-1)) )
else:
  print( math.seil((w)/(k-1)) + math.ceil((n-w-1)/(k-1)) )

### FIXED CODE ###

n, k = map(int, input().split())
print(-((1-n)//(k-1)))
s = input()
print(s.count())

### FIXED CODE ###

s = input()
print(s.count("1"))
N=int(input())
A=list(map(int,input().split()))

def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)


dp=[0]*N
dp[1]=max(A[0],A[1])
dp[2]=max(gcd(A[0],A[1]),gcd(A[1],A[2]),gcd(A[2],A[0]))
for i in range(3,N):
  dp[i]=gcd(dp[i-1],A[i])

print(dp[N-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N=int(input())
A=list(map(int,input().split()))

def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)

L=[0]*(N+2)
R=[0]*(N+2)

for i in range(1,N+1):
  L[i]=gcd(L[i-1],A[i-1])

for i in reversed(range(1,N+1)):
  R[i]=gcd(R[i+1],A[i-1])

M=[gcd(L[i-1],R[i+1]) for i in range(1,N+1)]

print(max(M))
H, W = list(map(int, input().split()))
N = int(input())
A = list(map(int, input().split()))
res = [["" for _ in range(W)] for h in range(H)]
start_y, start_x = 0, -1
pos_y, pos_x = start_y, start_x
dy, dx = 0, 1
for idx, a in enumerate(A, 1):
    for i in range(a):
        pos_x += dx
        pos_y += dy
        res[pos_y][pos_x] = str(idx)
        if pos_x == W - 1:
            if dy == 0:
                dx = 0
                dy = 1
            else:
                dx = -1
                dy = 0
        elif not pos_y == 0 and pos_x == 0:
            if dy == 0:
                dx = 0
                dy = 1
            else:
                dx = 1
                dy = 0
res = ["".join(x) for x in res]
res = "\n".join(res)
print(res)



### FIXED CODE ###

H,W=map(int,input().split())
N=int(input())
a=list(map(int,input().split()))
a_all=[]
c=[[""]*W for i in range(H)]

for i in range(N):
    b=[i+1]*a[i]
    a_all.extend(b)

i=0
for j in range(H):
    if j%2==0:
        for k in range(W):
            c[j][k]=str(a_all[i])
            i+=1
    else:
        for k in range(W-1,-1,-1):
            c[j][k]=str(a_all[i])
            i+=1

for i in range(H):
    print(" ".join(c[i]))
def main()
n = int(input())
A = list(map(int,input().split()))
ans = 1
 
for i in range(n):
    ans = ans*A[i]
    if 0 in A:
        print(0)
        return
    elif ans > 10**18:
      print(-1)
      return
 
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 1

if 0 in A:
  ans = 0
else:
  for i in range(n):
    ans = ans*A[i]
    if ans > 10**18:
        ans = -1
        break
 
print(ans)
import copy
N, M = map(int, input().split())
XY = []
for _ in range(M):
    x, y = map(int, input().split())
    XY.append([x - 1, y - 1])

ans = [0] * N

def dfs(depth, lst):
    if depth == M:
        for i in range(N):
            if lst[i][0] == 1:
                global ans
                ans[i] = 1
                return 0
    start = XY[depth][0]
    goal = XY[depth][1]
    # print(start, goal)
    # print(lst)
    if lst[start][0] == 1 and lst[start][1] == 0:
        lst[start][0] -= 1
        lst[goal][0] += 1
        dfs(depth + 1, lst)
    elif lst[start][0] == 1 and lst[start][1] > 0:
        a = copy.deepcopy(lst)
        lst[start][0] -= 1
        lst[goal][0] += 1
        dfs(depth + 1, lst)

        a[start][1] -= 1
        a[goal][1] += 1
        dfs(depth + 1, a)
    elif lst[start][0] == 0 and lst[start][1] == 0: return 0
    else:
        lst[start][1] -= 1
        lst[goal][1] += 1
        dfs(depth + 1, lst)

tmp = [[0, 1] for _ in range(N)]
tmp[0] = [1, 0]
dfs(0, tmp)

print(sum(ans))

### FIXED CODE ###

import copy
N, M = map(int, input().split())
XY = []
for _ in range(M):
    x, y = map(int, input().split())
    XY.append([x - 1, y - 1])

ball_num = [1] * N
is_red = [False] * N
is_red[0] = True

for i in range(M):
    s = XY[i][0]
    g = XY[i][1]
    if is_red[s]:
        if ball_num[s] == 1:
            ball_num[s] -= 1
            ball_num[g] += 1
            is_red[s] = False
            is_red[g] = True
        else:
            ball_num[s] -= 1
            ball_num[g] += 1
            is_red[g] = True
    else:
        ball_num[s] -= 1
        ball_num[g] += 1

print(sum(is_red))
n,k=map(int,input().split())
a=list(map(int,input().split()))
m=[]
for i in range(10):
  if i not in a:
    m.append(i)
k=0
for a in m:
  for b in m:
    for c in m:
      for d in m:
        num=a*1000+b*100+c*10+d
        if k==0 and num>=n:
          ans=num
          k=1
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
m=list(map(int,input().split()))
for i in range(n,100000):
  k=1
  for a in str(i):
    if int(a) in m:
      k=0
  if k:
    print(i)
    break
ary = list(map(input().split())).sort()

print(ary[0])

### FIXED CODE ###

ary=list(map(int, input().split()))
ary.sort()
print("{} {} {}".format(ary[0], ary[1], ary[2]))
N=int(input())
G=[[]for _ in range(N)]

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

c=list(map(int,input().split()))

cnt=[[0,i] for i in range(N)]

for i in range(N):
    cnt[i][0]=len(G[i])

cnt.sort(reverse=True)
c.sort(reverse=True)

l=[-1 for _ in range(N)]
for i in range(N):
    num=cnt[i][1]
    l[num]=c[i]
#print(l)
ans=0
chk=[[0 for i in range(N)] for _ in range(N)]

def bfs(v,p,chk):
    global ans
    if chk[v][p]==1:
        return
    chk[v][p]=1
    chk[p][v]=1
    ans+=min(l[v],l[p])
    for tmp in G[v]:
        bfs(tmp,v,chk)

for v in range(N):
    bfs(v,G[v][0],chk)

print(ans)
print(*l)

### FIXED CODE ###

from collections import deque
N=int(input())
G=[[]for _ in range(N)]
cnt=[0]*N
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
    cnt[a]+=1
    cnt[b]+=1

C=list(map(int,input().split()))
C.sort(reverse=True)

root=0
v=0
for i in range(N):
    if v>cnt[i]:
        root=i
        v=cnt[i]

def bfs(s):
    que=deque()
    que.append(s)
    nodes=[-1]*N
    k=0
    ans=0
    while len(que)>0:
        q=que.pop()
        nodes[q]=C[k]
        k+=1

        for v in G[q]:
            if nodes[v]<0:
                que.append(v)
    print(sum(C[1:]))
    print(*nodes)

bfs(root)