Harryxun/stf_run huggingface dataset:
import collections
import sys
S = input()
count_dict = collections.Counter(S)
Num_A = count_dict["a"]
Num_B = count_dict["b"]
Num_C = count_dict["c"]

s_list = {}
if Num_A !=0:
    s_list[0] ="a"
    Num_A -=1
elif Num_B != 0:
    s_list[0] ="b"
    Num_B -= 1
elif Num_C != 0:
    s_list[0] ="c"
    Num_C -= 1

if Num_A !=0 and s_list[0] !="a":
    s_list[1] ="a"
    Num_A -=1
elif Num_B != 0 and s_list[0] !="b":
    s_list[1] ="b"
    Num_B -= 1
elif Num_C != 0 and s_list[0] !="c":
    s_list[1] ="c"
    Num_C -= 1


i = 0
while Num_A + Num_B + Num_C != 0:
    if s_list[i] != "a" and s_list[i+1] != "a" and Num_A != 0:
        s_list[i+2] = "a"
        Num_A -=1
        i +=1

    elif s_list[i] != "b" and s_list[i+1] != "b" and Num_B != 0:
        s_list[i+2] = "b"
        Num_B -=1
        i +=1    
     
    elif s_list[i] != "c" and s_list[i+1] != "c" and Num_C != 0:
        s_list[i+2] = "c"
        Num_C -=1
        i +=1
    else:
        print("NO")    
        sys.exit()

print("YES")


### FIXED CODE ###

import sys
import collections
S = input()
count_dict = collections.Counter(S)
Num_A = count_dict["a"]
Num_B = count_dict["b"]
Num_C = count_dict["c"]

judge = sorted([Num_A, Num_B, Num_C])
if judge[2]-judge[0]>1:
    print('NO')
else:
    print('YES')
N = int(input())
A = []
for i in range(N):
	A.append(input())
 
B = sorted(A, reverse=True, key=number)
max_first = B[0]
max_second = B[1]
max_third = B[2]
 
for i in range(N):
	if A[i] != max_first:
		print(max_first)
    else if A[i] != max_second:
		print(max_second)
    else:
		print(max_third)


### FIXED CODE ###

N = int(input())
A = []
B = []
for _ in range(N):
    temp = int(input())
    A.append(temp)
    B.append(temp)

B.sort(reverse=True)
max_first = B[0]
max_second = B[1]

for i in range(N):
    if A[i] == max_first:
        print(max_second)
    else:
        print(max_first)
N = int(input())
A = map(int,input().split())
print(max(A)-min(A))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
print(max(A)-min(A))
def main():
    N,K,Q=map(int,input().split())
    sum2=[]
    score=[K]*N
    for i in range(Q):
        num=int(input())
        comp[i][:num-1]=[-1]*[num-1]
        comp[i][num-1]=[0]
        comp[i][num:N]=[-1]*[N-num]
    for i in range(N):
        sum2.append(sum(comp[i]))
    for i,j in zip(score,sum2):
        score.append(i+j)
    for s in score:
        if s>0:
            print('Yes')
        else:
            print('No')

if __name__=='__main__':
    main()


### FIXED CODE ###

n, k, q = map(int, input().split())
points = [k] * n
a = []
for i in range(q):
    a.append(int(input())-1)
for cand in a:
    points[cand] += 1
points = [i-q for i in points]
ans = ["Yes" if i > 0 else "No" for i in points]
print(*ans, sep="\n")
n=int(input())
print('{:.0f}'.format(math.floor(n/3)))

### FIXED CODE ###

import math
n=int(input())
print('{:.0f}'.format(math.floor(n/3)))
X = int(input())
coins = [100,101,102,103,105]
DP = [int(i%coins[0]==0) for i in range(X+1)]
for coin in coins[1:]:
  for i in range(X+1):
    DP[i] += DP[i - coin]
if DP[-1] != 0:
  print(1)
else:
  print(0)


### FIXED CODE ###

N=int(input())
coins = [100,101,102,103,104,105]
dp = [int(i%coins[0]==0) for i in range(N+1)]
for coin in coins[1:]:
  for i in range(coin,N+1):
    dp[i] += dp[i - coin]
if dp[-1] != 0:
  print(1)
else:
  print(0)
def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

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(mod_combination(k, i, 10 ** 9 + 7))

### 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))
k=int(input())
a=list(map(int, input().split()))
mon=1000
kai=0
for i in range(n-1):
  if a[i]>a[i+1] and a[i+1]>a[i+2]:
    mon+=kai*a[i]
    kai=0
  elif a[i]<a[i+1] and a[i+1]<a[i+2]:
    kai=int(mon/a[i])
    mon-=kai*a[i]

mon+=kai*a[n-1]

print(mon)


### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
mon=1000
kai=0
for i in range(n-1):
  if a[i]>a[i+1]:
    mon+=kai*a[i]
    kai=0
  elif a[i]<a[i+1] and kai==0:
    kai=int(mon/a[i])
    mon-=kai*a[i]

mon+=kai*a[n-1]

print(mon)
import collections
n=int(input())
a=list(map(int,input().split()))
b=collections.Counter(a)
c=list(b.items())
d=[]
e=[]
for i in range(len(c)):
  if c[i][1]>3:
    d.append(int(c[i][0]))
  elif c[i][1]>1:
    e.append(int(c[i][0]))
d.sort(reverse=True)
e.sort(reverse=True)
if len(d)<1 and len(e)<2:
  print(0)
else:
  print(max((d[0])**2,e[0]*e[1]))
    


### FIXED CODE ###

import collections
n=int(input())
a=map(int,input().split())
b=list(collections.Counter(a).items())
lst=[]
Lst=[]
for i in range(len(b)):
  if b[i][1]>1:
    lst.append(int(b[i][0]))  
    if b[i][1]>3:
      Lst.append(int(b[i][0]))
if len(lst)<2 and len(Lst)==0:
  print(0)
else:
  if len(lst)==1:
    Lst.sort(reverse=True)
    print(Lst[0]**2)
  else:
    if len(Lst)>0:
      lst.sort(reverse=True)
      Lst.sort(reverse=True)
      print(max(lst[0]*lst[1],Lst[0]**2))     
    else:
      lst.sort(reverse=True)
      print(lst[0]*lst[1])
N = str(input())
L = list(N)
f = 0
for l in L:
  f += l
if (int(N) % f) == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = str(input())
L = list(N)
f = 0
for l in L:
  f += int(l)
if (int(N) % f) == 0:
  print("Yes")
else:
  print("No")
n,m,r=map(int,input().split())
road=list(map(int,input().split()))
cost=[[float("inf")]*n for i in range(n)]
for i in range(n):
    cost[i][i]=0
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    cost[a][b]=c
    cost[b][a]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
import itertools
ans=float("inf")
for i in itertools.permutations(road):
    tmp=0
    for j in range(len(i)-1):
        tmp+=cost[i[j]-1][i[j+1]-1]
    if tmp<ans:
        ans=tmp
print(ans)

### FIXED CODE ###

n,m,r=map(int,input().split())
road=list(map(int,input().split()))
cost=[[float("inf")]*n for i in range(n)]
for i in range(n):
    cost[i][i]=0
for i in range(m):
    
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    cost[a][b]=c
    cost[b][a]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
import itertools
ans=float("inf")
for i in itertools.permutations(road):
    tmp=0
    for j in range(len(i)-1):
        tmp+=cost[i[j]-1][i[j+1]-1]
    if tmp<ans:
        ans=tmp
print(ans)
x = list(map(int,input().split()))
for i in 0 to X[0]
    A.append(input())

result = ''.join(A)
print(result)


### FIXED CODE ###

x = list(map(int,input().split()))
A = []
for i in range(x[0]):
    A.append(input())

A.sort()
result = ''.join(A)
print(result)
s=[]
for _ in range(int(input())):
 e=input()
 if'i'==e[0]:s=[e.split()[1]]+s
 else:
  if' '==e[6]:s.remove(e.split()[1])
  elif len(e)%2:s=s[1:]
  else:s.pop()
print(*s)


### FIXED CODE ###

import collections,sys
def s():
 d=collections.deque()
 input()
 for e in sys.stdin:
  if'i'==e[0]:d.appendleft(e[7:-1])
  else:
   if' '==e[6]:
    m=e[7:-1]
    if m in d:d.remove(m)
   elif'i'==e[7]:d.popleft()
   else:d.pop()
 print(*d)
if'__main__'==__name__:s()
s = input()
a = s.fin("A")
z = s. find("Z")
print(z - a + 1)


### FIXED CODE ###

s = input()
a_index = s.find("A")
z_index = s.rfind("Z")
print(z_index - a_index + 1)
import copy

def warshall_floyd(V, E):
    INF = 10 ** 9
    d = [[[INF, []] for j in range(V + 1)] for i in range(V + 1)]
    for i, j, c in E:
        d[i][j] = [c, []]
        d[j][i] = [c, []]
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i][k][0] + d[k][j][0]
                if d[i][j][0] > dk:
                    root = copy.copy(d[i][k][1]) + [k] + copy.copy(d[k][j][1])
                    d[i][j] = [dk, root]
                    d[j][i] = [dk, root]
    return d

n, m = map(int, input().split())
E = [[None for j in range(n + 1)] for i in range(n + 1)]
E_list = []
for i in range(m):
    a, b, c = map(int, input().split())
    E_list.append([a, b, c])
    E[a][b] = 0
    E[b][a] = 0
d = warshall_floyd(n, E_list)
ans = m
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        k = i
        for r in d[i][j][1]:
            if E[r][k] == 0:
                ans -= 1
            E[r][k] += 1
            E[k][r] += 1
            k = r
        if E[j][k] == 0:
            ans -= 1
        E[j][k] += 1
        E[k][j] += 1
print(ans)

### FIXED CODE ###

import copy

def warshall_floyd(V, E):
    INF = 10 ** 9
    d = [[[INF, 0] for j in range(V + 1)] for i in range(V + 1)]
    for i, j, c in E:
        d[i][j] = [c, 0]
        d[j][i] = [c, 0]
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i][k][0] + d[k][j][0]
                if d[i][j][0] > dk:
                    d[i][j] = [dk, k]
                    d[j][i] = [dk, k]
    return d

def find_path(i, j, d, E):
    k = d[i][j][1]
    if k == 0:
        E[i][j] += 1
        E[j][i] += 1
        return E
    E = find_path(i, k, d, E)
    E = find_path(k, j, d, E)
    return E

n, m = map(int, input().split())
E = [[None for j in range(n + 1)] for i in range(n + 1)]
E_list = []
for i in range(m):
    a, b, c = map(int, input().split())
    E_list.append([a, b, c])
    E[a][b] = 0
    E[b][a] = 0
d = warshall_floyd(n, E_list)
ans = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        E = find_path(i, j, d, E)
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if E[i][j] == 0:
            ans += 1
print(ans)
import math
a,b,c,d = map(int,input().split())


an1 = math.floor(b/c)
an2 = math.floor((a-1)/c)
an3 = math.floor(b/d)
an4 = math.floor((a-1)/d)

gcd = round(c * d / math.gcd(c, d))

an5 = math.floor(b/gcd)
an6 = math.floor((a-1)/gcd)
an = an1-an2 + an3-an4 -(an5-an6)
print((b-a+1)-an)

    

### FIXED CODE ###

from fractions import gcd
import math
a,b,c,d = map(int,input().split())

if c == 1 or d == 1:
    print(0)
elif a == b:
    if a%c == 0 or a%d == 0:
        print(0)
    else:
        print(1)
else:
    an1 = (b//c)
    an2 = ((a-1)//c)
    an3 = (b//d)
    an4 = ((a-1)//d) 
    gcd = round(c * d / gcd(c, d))
    an5 = (b//gcd)
    an6 = ((a-1)//gcd)
    if c == d:
        an = an1-an2
    else:
        an = an1-an2 + an3-an4 -(an5-an6)
    print((b-a+1)-an)
N, K = map(int, input().split())
S = list(list(input()))

a = []
temp = S[0]
s = []
ans = 0

if temp == S[1]:
    hantei = True
    a.append(temp)
else:
    hantei = False
    s.append(list(S[0]))


for i in range(1, N):
    if temp == S[i]:
        ans += 1
    if hantei and temp != S[i]:
        s.append(a)
        a = []
        hantei = False
    if temp != S[i] or hantei:
        hantei = True
        a.append(S[i])
        temp = S[i]
s.append(a)

length = len(s)
for i in range(K):
    if length > 2:
        ans += 2
        length -= 2
    elif length == 2:
        ans += 1
        break

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
S = list(list(input()))

a = []
temp = S[0]
s = []
ans = 0

if len(S) > 1 and temp == S[1]:
    hantei = True
    a.append(temp)
else:
    hantei = False
    s.append(list(S[0]))

for i in range(1, N):
    if temp == S[i]:
        ans += 1
    if hantei and temp != S[i]:
        s.append(a)
        a = []
        hantei = False
    if temp != S[i] or hantei:
        hantei = True
        a.append(S[i])
        temp = S[i]
if len(S) > 1:
    s.append(a)

length = len(s)
for i in range(K):
    if length > 2:
        ans += 2
        length -= 2
    elif length == 2:
        ans += 1
        break

print(ans)
n, k= map(int, input().split())
x = [0]*n
for i in range(k):
  z = int(input())
  if z == 1:
    x[z-1] +=1
  else:
    a = list(map(int, input().split()))
    for j in a:
      x[j-1] +=1
print(x.count(0))

### FIXED CODE ###

n, k= map(int, input().split())
x = [0]*n
for i in range(k):
  z = int(input())
  if z == 1:
    x[int(input())-1] +=1
  else:
    a = list(map(int, input().split()))
    for j in a:
      x[j-1] +=1
print(x.count(0))
import bisect
import sys
sys.setrecurtionlimit(10**8)

def dfs(v,l,tr):
  ans[v]=l
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      pos=bisect.bisect_left(tr,arr[u])
      if pos==l:
        dfs(u,l+1,tr+[arr[u]])
      elif tr[pos]==arr[u]:
        dfs(u,l,tr)
      else:
        dfs(u,l,tr[:pos]+[arr[u]]+tr[pos+1:])

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dfs(1,1,[arr[1]])
for i in range(1,n+1):
  print(ans[i])

### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**7)

def dfs(v):
  pos=bisect.bisect_left(dp,arr[v])
  changes.append((pos,dp[pos]))
  dp[pos]=arr[v]
  ans[v]=bisect.bisect_left(dp,10**18)
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      dfs(u)
  pos,val=changes.pop()
  dp[pos]=val

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dp=[10**18 for _ in range(n+1)]
changes=[]
dfs(1)
for i in range(1,n+1):
  print(ans[i])
n=int(input())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
c=list(map(int, input().split()))

sum=0
for i in range(n):
  sum=sum+b[a[i]]
  if i>0 | a[i-1] == a[i]+1:
    sum=sum+c[a[i-1]]

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
c=list(map(int, input().split()))

sum=0
for i in range(n):
    sum=sum+b[i]
    if i>0 and a[i-1] == a[i]-1:
        sum=sum+c[a[i]-2]
print(sum)
import math
r = input()
rr = int(r)
print("{0:f} {1:f}".format(rr * rr * math.pi, rr * 2 * math.pi))

### FIXED CODE ###

import math
r = [float(x) for x in input().split()]
print("{0:f} {1:f}".format(r[0] * r[0] * math.pi, r[0] * 2 * math.pi))
N = int(input())
S = input()
c = 0
for i in range(N - 1, -1, -1):
    if S[i] == ".":
        c1 = i
        break
cc = 0
for i in range(N - 1, c1, -1):
    if S[i] == "#":
        cc += 1
a = S[:i + 1].count(".")
b = S[:i + 1].count("#")
ans = min(a, b, c2)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
r1 = [0] * N
r2 = [0] * (N+1)
r1[0] = 1 * (S[0] == '#')
for i in range(1, N):
    if S[i] == "#":
        r1[i] = r1[i - 1] + 1
    else:
        r1[i] = r1[i - 1]
#print(r1)
r2[N - 1] = 1 * (S[N - 1] == ".")
r2[N] = r2[N-1]
for i in range(N - 2, -1, -1):
    if S[i] == ".":
        r2[i] = r2[i + 1] + 1
    else:
        r2[i] = r2[i + 1]
#print(r2)
c1 = S.count("#")
c2 = S.count(".")
ans = N
for i in range(N):
    ans = min(ans, r1[i] + r2[i + 1])
print(min(ans, c1, c2))
N=int(input())
A=list(map(int, input().split()))

c=max(A)
D=[0]*(c+1)
div=[0]*(c+1)
P=[]

for i in range(2,c+1):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>c and i>D[j]:
           break
        D[i*j]=j

for i in A:
    c=gcd(c,i)
    if i==1:
        continue
    temp=i
    if temp==D[temp]:
        div[temp]+=1
        continue
    while temp!=D[temp]:
        div[D[temp]]+=1
        temp=temp//D[temp]

if max(div)<=1:
    print('pairwise coprime')

elif c==1:
    print('setwise coprime')

else:
    print('not coprime')

### FIXED CODE ###

from functools import reduce
from math import gcd

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

c=max(A)+1
D=[0]*c
div=[0]*c
P=[]

for i in range(2,c):
    if D[i]==0:
        P.append(i)
        D[i]=i
    for j in P:
        if i*j>=c  or j>D[i] :
           break
        D[i*j]=j
f=0
for i in A:
    if i==1:
        continue
    temp=i
    while temp!=1:
        if div[D[temp]]==1:
            f=1
            break
        div[D[temp]]+=1
        temp2=D[temp]
        while temp%temp2==0 and temp>=temp2:
            temp=temp//temp2
    if f==1:
        break
        


if max(div)<=1 and f==0:
    print('pairwise coprime')

elif reduce(gcd, A) == 1:
    print('setwise coprime')

else:
    print('not coprime')
N, K = map(int, input().split())
V = list(map(int, input().split()))
l = [0]
for i in range(1, K + 1): #左に何回操作するか
    #print("i=",i)
    b = 0
    for j in range(i // 2 + 1): #いくつ捨てるか
        #print("j=",j)
        a = V[0:i - j]
        s = sum(a)
        #print("s=",s)
        a.sort()
        for m in range(j):
            if a[m] >= 0:
                break
            s -= a[m]
        b = max(b, s)
    #print("b=",b)
    l.append(max(b, l[-1]))
#print(l)
r = [0]
for i in range(1, K + 1): #右に何回操作するか
    #print("i=",i)
    b = 0
    for j in range(i // 2 + 1): #いくつ捨てるか
        #print("j=",j)
        a = V[N - i + j:N]
        s = sum(a)
        #print("s=",s)
        a.sort()
        for m in range(j):
            if a[m] >= 0:
                break
            s -= a[m]
        b = max(b, s)
    #print("b=",b)
    r.append(max(b, r[-1]))
#print(r)
ans = 0
for i in range(K + 1):
    ans = max(ans, l[i] + r[K - i])
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for i in range(N + 1):#左から何個とるか
    if i > K:
        break
    for j in range(N + 1):#右から何個とるか
        if i + j > N or i + j > K:
            break
        for l in range(N + 1):#何個捨てるか
            if i + j + l > K:
                break
            a = V[:i] + V[N-j:]
            a.sort()
            s = sum(a[l:])
            ans = max(ans, s)
print(ans)
def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    tmp_lst = tree_dic[current_node][:]

    for next_node in tmp_lst:
        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)

        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除

        try:

            else:   #   次のノードにつながっている辺があるとき
                ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)
 
 
        except:
            return ans

    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)



### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)

def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    next_node_lst = tree_dic[current_node][:]

    for next_node in next_node_lst:
        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)

        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除
        else:   #   次のノードにつながっている辺があるとき
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)
x1,y1,x2,y2=map(int, input().split())
print(x2+y1-y2,y2-x1+x2,x1-x2+x3,y1-y2+y3)

### FIXED CODE ###

x1,y1,x2,y2=map(int, input().split())
print(x2+y1-y2,y2-x1+x2,x1-x2+x2+y1-y2,y1-y2+y2-x1+x2)
A = int(input())
B = int(input())
if(A > B):
  print("Alice")
elif(B > A):
  print("Bob")
else:
  print("Draw")

### FIXED CODE ###

A, B = map(int, input().split())
if(A ==1):
  A += 13
if(B ==1):
  B += 13
if(A > B):
  print("Alice")
elif(B > A):
  print("Bob")
else:
  print("Draw")
import numpy as np
n=int(input())
A=list(map(int,input().split()))
B=np.array([[0]*n for i in range(n)])
for i in range(n-1):
	B[i,i]=B[i,i+1]=1
B[n-1,0]=B[n-1,n-1]=1
X=np.linalg.solve(B,A)
print(*[int(2*x) for x in X])


### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
X=[0]*n
s=0
for i in range(n):
    s+=((-1)**i)*A[i]
X[0]=s//2
for i in range(n-1):
    X[i+1]=A[i]-X[i]
print(*[2*x for x in X])
s = st(input())
string = list(s)
cnt = sum(string)
print("x" * cnt)

### FIXED CODE ###

s = str(input())
string = list(s)
cnt = len(string)
print("x" * cnt)
from math import sqrt
a,b,c,d = map(int,input().split())
print(sqrt((c-a)**2+(d-b)**2))

### FIXED CODE ###

from math import sqrt
a,b,c,d = map(float,input().split())
print(sqrt((c-a)**2+(d-b)**2))
while True:
    H,W = map(int,input().split())
    if (H,W) = =0:
        break
    for i in range(H):
        print("#"*W)
    print()


### FIXED CODE ###

while True:
    H,W = map(int,input().split())
    if H == 0 and W==0:
        break
    for i in range(H):
        print("#"*W)
    print()
N, D = input().split()

x = [0] * N
y = [0] * N

for i in range(N):
  x[i], y[i] = map(int, input().split())
  
counter = 0

for i in range(N):
  dist = x[i] * x[i] + y[i] * y[i]
  if dist <= D*D:
    counter += 1

print(counter)

### FIXED CODE ###

N, D = map(int, input().split())

x = [0] * N
y = [0] * N

for i in range(N):
  x[i], y[i] = map(int, input().split())
  
counter = 0

for i in range(N):
  dist = x[i] * x[i] + y[i] * y[i]
  if dist <= D*D:
    counter += 1

print(counter)
n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
b = 1
ans = 1
while ans:
  a = b
  b = A[a-1]
  B.append(b)
  if len(B) == len(A):
    ans = 0
  else:
    continue

print(B[k-1])


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
roop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(roop[(K-(len(move)-len(roop)))%len(roop)]+1)
a,b = map(int,input().split())

if a % 3 == 0 or b % 3 == 0 or (a+b) % 3 == 0:
  print('Possible')
else:
  pritn('Impossible')

### FIXED CODE ###

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

if a % 3 == 0 or b % 3 == 0 or (a+b) % 3 == 0:
  print('Possible')
else:
  print('Impossible')