Harryxun/stf_run huggingface dataset:
import collections
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
def kaijo(x):
    a=1
    for i in range(1,x+1):
        a*=i
    return a
def perm(x,y):
    ans=1
    for i in range(x,x-y,-1):
        ans*=i
    return ans
def com(x,y):
    return perm(x,min(y,x-y))//kaijo(min(y,x-y))

nn,m=map(int,input().split())
x=primes(int(m**0.5+1))
y=[]
z=m
for t in x:
    while(z%t==0):
        z//=t
        y.append(t)
c=list(collections.Counter(y).values())

ans=1
for t in c:
    ans*=com(t+nn-1,t)
    ans%=mod
print(ans)

### FIXED CODE ###

import collections
def com(x,y):
    y=min(y,x-y)
    a=1
    for i in range(x,x-y,-1):
        a*=i
    b=1
    for i in range(1,y+1):
        b*=i
    return a//b
n,m=map(int,input().split())
y=[]
i=2
z=m
while(i*i<=m):
    if m%i:
        i+=1
    else:
        m//=i
        y.append(i)
if m>1:
    y.append(m)
c=collections.Counter(y).values()
ans=1
mod=10**9+7
for t in c:
    ans*=com(t+n-1,t)
    ans%=mod
print(ans)
n,k=map(int,input().split())
s=[]
for i in range(n):
  a,b=map(int,input().split())
  if a>max(s) and len(s)>k:
    continue
  s+=[a]*b
p=sorted(s)
print(p[k-1])

### FIXED CODE ###

n,k=map(int,input().split())
d=[0]*(10**5+1)
for i in range(n):
  a,b=map(int,input().split())
  d[a]+=b
for i in range(10**5+1):
  if d[i]>=k:
    print(i)
    break
  else:k-=d[i]
N=int(input())
array=input()
L=[int(val) for val in array.split()]
L=sorted(L)
total=0
start=0
P=[L for val in L]
for _ in range(N):
  total+=min(P[start],P[start+1])
  P.pop(start)
  P.pop(start+1)
  start+=2
print(total)

### FIXED CODE ###

N=int(input())
inp=input()
L=[int(val) for val in inp.split()]
L=sorted(L,reverse=True)
total=0
start=0
for _ in range(N):
  total+=min(L[start],L[start+1])
  start+=2
print(total)
"""
8
4 23 75 0 23 96 50 100
"""

[0,75,0,96,50,100]

n = int(raw_input())
ais = map(int, raw_input().split(' ')) #set()
i = 0
while(i < len(ais) and ais[i] == 0): i+=1
ais = ais[i:]

r = [0]
for i in range(len(ais)):
	if (ais[i-1] if i-1 >= 0 else 0) <= ais[i] > (ais[i+1] if i+1 < len(ais) else 0): 
		r.append(ais[i])
	if (ais[i-1] if i-1 >= 0 else 0) >= ais[i] < (ais[i+1] if i+1 < len(ais) else 0): 
		if i:
			r.append(ais[i])

	
t = 0
for i in range(0,len(r),2):
	if i + 1 < len(r):
		u,v = r[i],r[i+1]
		t += v-u
print t if len(ais) > 1 else ais[0]

### FIXED CODE ###

"""
8
4 23 75 0 23 96 50 100
"""

n = int(raw_input())
ais = map(int, raw_input().split(' '))

def f(ais):
	r = [0]
	for i in range(len(ais)):
		## looking for max
		if len(r) % 2:	
			if (ais[i-1] if i-1 >= 0 else 0) <= ais[i] > (ais[i+1] if i+1 < len(ais) else 0): 
				r.append(ais[i])
		else:
		## looking for min
			if (ais[i-1] if i-1 >= 0 else 0) >= ais[i] < (ais[i+1] if i+1 < len(ais) else 1000): 
				r.append(ais[i])

	t = 0
	for i in range(0,len(r),2):
		if i + 1 < len(r):
			u,v = r[i],r[i+1]
			t += v-u
	
	return t if len(ais) > 1 else ais[0]
print f(ais)
from itertools import *

def find(X):
    for a,b,c,d in permutations(X):
        for x,y,z in product("+-*",repeat=3):
            for f in ("(((%s%s%s)%s%s)%s%s)","(%s%s%s)%s(%s%s%s)"):
                t = f%(a,x,b,y,c,z,d)
                if eval(t)==10:
                    return t
    return 0

while True:
    X = map(int,raw_input().split())
    if X==(0,0,0,0):
        break
    print find(X)

### FIXED CODE ###

from itertools import *

def find(X):
    for a,b,c,d in permutations(X):
        for x,y,z in product("+-*",repeat=3):
            for f in ("(((%s%s%s)%s%s)%s%s)","(%s%s%s)%s(%s%s%s)"):
                t = f%(a,x,b,y,c,z,d)
                if eval(t)==10:
                    return t
    return 0

while True:
    X = map(int,raw_input().split())
    if X==[0,0,0,0]:
        break
    print find(X)
pi = 3.14159265359 
r = int(input()) 
area = pi*pi*r 
length = pi*r*2 

print('{:.6f}'.format(length),'{:.6f}'.format(length))


### FIXED CODE ###

pi = 3.14159265359 
r = float(input()) 
area = r*r*pi 
length = 2*r*pi 

print('{:.6f}'.format(area),'{:.6f}'.format(length))
K=int(input())
M,N = map(int,input().rstrip().split(" ")) 
#print(K,M,N)
for number in range(M,N+1):
    if number%K==0:
        ans=True
if ans:
    print("YES")
else:
    print("NG")

### FIXED CODE ###

K=int(input())
ans = False
M,N = map(int,input().rstrip().split(" ")) 
#print(K,M,N)
for number in range(M,N+1):
    if number%K==0:
        ans = True
if ans:
    print("OK")
else:
    print("NG")
import sys
 
def main():
    S = input()
    l = len(S)
    
    cnt_l = []
    
    for i in range(l):
        cnt = 0
        for j in range(l-i):
            if str(S[i+j]) in ['A', 'C', 'G', 'T']:
                cnt += 1
            else:
                cnt_l.append(cnt)
 
    m = max(cnt_l)
 
    print(out)
main()

### FIXED CODE ###

import sys

def main():
    S = input()
    l = len(S)
    
    ans = 0
    for i in range(l):
        for j in range(i, l):
            if all(['ATGC'.count(c) == 1 for c in S[i:j+1]]):
                ans = max(ans, j-i+1)
            
    print(ans)
main()
a,b=input()
a=a+b
if a-24>=0:
  print(a-24)
else:
  print(a)

### FIXED CODE ###

a=input()
a=a.split(" ")
b=int(a[1])
a=int(a[0])
a=a+b
if a-24>=0:
  print(a-24)
else:
  print(a)
# あなたは、500円玉をA枚、100円玉をB枚、50円玉をC枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうどX円にする方法は何通りありますか。
A,B,C,X=(int(z) for z in input().split())
# A,B,C,X=map(int,'30 30 30 12000'.split())
N=0

for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if i*500+j*100+k*50==X:
                N+=1

print(N)

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())

N=0

for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if i*500+j*100+k*50==X:
                N+=1

print(N)
import sys

#list = sys.stdin.readlines()

i=0
list = []
for line in sys.stdin.readlines():
	list.append(int(line.strip("\n")))

print soted(list, reverse=True)[0]
print soted(list, reverse=True)[1]
print soted(list, reverse=True)[2]

### FIXED CODE ###

import sys

#list = sys.stdin.readlines()

i=0
list = []
for line in sys.stdin.readlines():
	list.append(int(line.strip("\n")))

print sorted(list, reverse=True)[0]
print sorted(list, reverse=True)[1]
print sorted(list, reverse=True)[2]
#!/usr/bin/env python3
n, k, c = map(int, input().split())
s = input()

if c == 0:
    if s.cnt("o") == k:
        print(*range(1, n + 1), sep="\n")
    exit()

left = []
i = 0
while i < n:
    if s[i] == "o":
        left.append(i)
        i += c
    i += 1

right = []
i = n - 1
while i >= 0:
    if s[i] == "o":
        right.append(i)
        i -= c
    i -= 1
right.reverse()
for i in range(len(left)):
    if left[i] == right[i]:
        print(left[i] + 1)


### FIXED CODE ###

#!/usr/bin/env python3
n, k, c = map(int, input().split())
s = input()

if c == 0:
    if s.count("o") == k:
        for i in range(n):
            if s[i] == "o":
                print(i + 1)
    exit()

left = []
i = 0
while i < n:
    if s[i] == "o":
        left.append(i)
        i += c
    i += 1

right = []
i = n - 1
while i >= 0:
    if s[i] == "o":
        right.append(i)
        i -= c
    i -= 1
right.reverse()
for i in range(len(left)):
    if left[i] == right[i]:
        print(left[i] + 1)
result = []
def calc(a, b, c, i):
    if i >= N:
        if a < 0 or b < 0 or c < 0:
            return False
        return True
    command = s[i]
    if command == "AB":
        if calc(a+1, b-1, c, i+1):
            result.append("A")
            return True
        if calc(a-1, b+1, c, i+1):
            result.append("B")
            return True
        return False
    elif command == "AC":
        if calc(a+1, b, c-1, i+1):
            result.append("A")
            return True
        if calc(a-1, b, c+1, i+1):
            result.append("C")
            return True
        return False
    elif command == "BC":
        if calc(a, b-1, c+1, i+1):
            result.append("C")
            return True
        if calc(a, b+1, c-1, i+1):
            result.append("B")
            return True
        return False
def main():
    global N, s
    N, A, B, C = map(int, input().split())
    s = [input() for _ in range(N)]
    if calc(A, B, C, 0):
        print("Yes")
        for c in result[::-1]:
            print(c)
    else:
        print("No")
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
result = []
def calc(a, b, c, i):
    if a < 0 or b < 0 or c < 0:
        return False
    if i >= N:
        return True
    command = s[i]
    if command == "AB":
        if calc(a+1, b-1, c, i+1):
            result.append("A")
            return True
        if calc(a-1, b+1, c, i+1):
            result.append("B")
            return True
        return False
    elif command == "AC":
        if calc(a+1, b, c-1, i+1):
            result.append("A")
            return True
        if calc(a-1, b, c+1, i+1):
            result.append("C")
            return True
        return False
    elif command == "BC":
        if calc(a, b-1, c+1, i+1):
            result.append("C")
            return True
        if calc(a, b+1, c-1, i+1):
            result.append("B")
            return True
        return False
def main():
    global N, s
    N, A, B, C = map(int, input().split())
    s = [input() for _ in range(N)]
    if calc(A, B, C, 0):
        print("Yes")
        for c in result[::-1]:
            print(c)
    else:
        print("No")
main()
from scipy.special import comb
N,M=map(int,input().split())

if N<=1 and M<=1:
    print(0)
else:
    print(int(comb(N,2))+int(comb(M,2)))

### FIXED CODE ###

import math
N,M=map(int,input().split())

def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if N<=1 and M<=1:
    print(0)
elif N>=2 and M>=2:
    print(int(combi(N,2))+int(combi(M,2)))
elif N>=2 and M<=1:
    print(int(combi(N,2)))
elif N<=1 and M>=2:
    print(int(combi(M,2)))
def solve():
   x = raw_input()
   y = raw_input()
   lenx = len(x)
   leny = len(y)
   
   z = [0 for k in range(lenx)]
   for i in range(lenx):
      a = x[i]
      b = z + []
      for j in range(leny):
         if a == y[i]:
               z[j+1] = b[j] + 1
         elif z[j+1] < z[j]:
               z[j+1] = z[j]
               
   print max(z)

n = input()
for i in range(n):
   solve()

### FIXED CODE ###

def solve():
    x = raw_input()
    y = raw_input()
    a, b = len(x), len(y)
    x1 = [0 for k in range(b+1)]
    for i in xrange(a):
        c = x[i]
        x2 = x1+[]
        for j in xrange(b):
            if c == y[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    print max(x1)
  
n = input()
for i in xrange(n):
    solve()
N, Q, S, *L = open(0).read().split()
N = int(N)
Q = int(Q)
l = -1
r = N
while l+1<r:
  s = (l+r)//2
  p = S[s]
  m = s
  for t,d in zip(*[iter(L)]*2):
    if p==t:
      if d=='L':
        m -= 1
      else:
        m += 1
    if m<=-1:
      l = s
      break
    p = S[m]
  else:
    r = s
ans = l+1
l = -1
r = N
while l+1<r:
  s = (l+r)//2
  p = S[s]
  m = s
  for t,d in zip(*[iter(L)]*2):
    if p==t:
      if d=='L':
        m -= 1
      else:
        m += 1
    if N<=m:
      r = s
      break
    p = S[m]
  else:
    l = s

ans += N-r
print(N-ans)

### FIXED CODE ###

N, Q, S, *L = open(0).read().split()
N = int(N)
Q = int(Q)
l = -1
r = N
while l+1<r:
  s = (l+r)//2
  p = S[s]
  m = s
  for t,d in zip(*[iter(L)]*2):
    if p==t:
      if d=='L':
        m -= 1
      else:
        m += 1
    if m<=-1:
      l = s
      break
    if N<=m:
      r = s
      break
    p = S[m]
  else:
    r = s
ans = l+1
l = -1
r = N
while l+1<r:
  s = (l+r)//2
  p = S[s]
  m = s
  for t,d in zip(*[iter(L)]*2):
    if p==t:
      if d=='L':
        m -= 1
      else:
        m += 1
    if N<=m:
      r = s
      break
    if m<=-1:
      l = s
      break
    p = S[m]
  else:
    l = s

ans += N-r
print(N-ans)
n = int(input())
a = list(map(int,input().split()))
m = max(a)
l = [True]*max(a)

ans=0
a.sort()
if a[0]==a[1]:
    l[a[0]-1]=False
for i in a:
    if l[i-1]:
        ans+=1
        tmp = i
        while tmp<=m:
            l[tmp-1] = False
            tmp+=i
    #print(l)
    #print(ans)
print(ans)

### FIXED CODE ###


n = int(input())
a = list(map(int,input().split()))+[10**7]
a.sort()
l = [True]*(10**6+1)

ans=0
a.sort()
for i in range(n):
    if l[a[i]]:
        for j in range(a[i],10**6+1,a[i]):
            l[j]=False
        if a[i]!=a[i+1]:
            ans+=1
print(ans)
l,r=map(int,input().split())
ll=l%2019
rr=r%2019

ans=float('inf')
for i in range(ll,rr):
    for j in range(i+1,rr+1):
        ans=min(ans,i*j%2019)
print(ans)

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
ma=max(a)
aa=sorted(a,reverse=True)
for i in a:
    if i !=ma:
        print(ma)
    else:
        print(aa[1])
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
#R = 10**9 + 7
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def perm(n,a,R):
    return (fact[n]*modinv2(fact[n-a],R))

def comb(n,a,R):
    return (fact[n]*modinv2(fact[n-a]*fact[a],R))

def factinit(n,R):
    global fact
    fact = [1]*(n+1)
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%R

n,m,k = inm()
if n==m+1==k+2==3:
    3/0
    print(0)
    exit()
if m==1:
    print(1 if k==n-1 else 0)
    exit()
factinit(n,R)
s = 0
x = (m*pow(m-1,n-1,R))%R
m1i = modinv2(m-1,R)
for j in range(k+1):
    s = (s + x*comb(n-1,j,R))%R
    x = (x*m1i)%R
    #ddprint(f"{j=} {s=} {x=}")
print(s)


### FIXED CODE ###

#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
#R = 10**9 + 7
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def perm(n,a,R):
    return (fact[n]*modinv2(fact[n-a],R))

def comb(n,a,R):
    return (fact[n]*modinv2(fact[n-a]*fact[a],R))

def factinit(n,R):
    global fact
    fact = [1]*(n+1)
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%R

n,m,k = inm()
if n==m+1==k+2==-3:
    3/0
    print(0)
    exit()
if m==1:
    print(1 if k==n-1 else 0)
    exit()
factinit(n,R)
s = 0
x = (m*pow(m-1,n-1,R))%R
m1i = modinv2(m-1,R)
for j in range(k+1):
    s = (s + x*comb(n-1,j,R))%R
    x = (x*m1i)%R
    #ddprint(f"{j=} {s=} {x=}")
print(s)
a, b = map(int, list(input.split(" ")) )
s = a + b
print((s+1)/2)


### FIXED CODE ###

a, b = map(int, list(input().split(" ")) )
s = a + b
print(int((s+1)/2))
from functools import reduce
from math import gcd
N, K = map(int, input().split())
X = sorted(list(map(int, input().split())) + [K])
# print(X)
S = [X[i+1] - X[i] for i in range(N)]
# print(S)
D = reduce(gcd, S, S[0])
print(D)


### FIXED CODE ###

from functools import reduce
from fractions import gcd
N, K = map(int, input().split())
X = sorted(list(map(int, input().split())) + [K])
# print(X)
S = [X[i+1] - X[i] for i in range(N)]
# print(S)
D = reduce(gcd, S, S[0])
print(D)
import sys
for s in sys.stdin.readlines():
    L=[]
    for d in s:
        if d.isdigit():
            L.append(float(d))
        else:
            op1=L.pop()
            op2=L.pop()
            if d=="-":
                L.append(op2-op1)
            elif d=="+":
                L.append(op2+op1)
            elif d=="*":
                L.append(op2*op1)
            elif d=="/":
                L.append(op2/op1)
    print L[0]

### FIXED CODE ###

import sys
for s in sys.stdin.readlines():
    L=[]
    for d in s.strip().split():
        if d=="-":
            d=(-(L.pop()-L.pop()))
        elif d=="+":
            d=(L.pop()+L.pop())
        elif d=="*":
            d=(L.pop()*L.pop())
        elif d=="/":
            d=(1/L.pop()*L.pop())
        L.append(float(d))
    print "%.6f"%L[0]
x,n = map(int,input().split())

import sys
if n == 0:
    print(x)
    sys.exit()

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

sa_min = 1000000
for i in range(1, 101):
    if i not in p_list:
        if sa_min > abs(i - x):
            sa_min = abs(i - x)
            ans = i
print(ans)

### FIXED CODE ###

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

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

import sys
if n == 0:
    print(x)
else:
    sa_min = 1000000
    for i in range(-110, 210):
        if i not in p_list:
            if sa_min > abs(i - x):
                sa_min = abs(i - x)
                ans = i
    print(ans)
import sys
import math

def main():
    a, b, k = map(int, sys.stdin.readline().split())
    query_range = range(a, b + 1)
    
    query_range = list(query_range)
    print('なんだこのバグ')
    exit()

    if a == b:
        res = query_range
    elif k >= math.ceil((b - a + 1) / 2):
        res = query_range
    else:
        res = query_range[:k] + query_range[-k:]

    for i in res:
        print(i)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

a, b, k = map(int, sys.stdin.readline().split())

def main():
    if k >= b - a + 1:
        res = list(range(a, b+1))
    else:
        res = set(range(a, a+k)) | set(range(b, b-k, -1))
        res = sorted(res)
    return res

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')
a,b = map(int, input().split())
print a if a<=b else a-1

### FIXED CODE ###

a,b = map(int, input().split())
if a <= b:
    print(a)
else:
    print(a-1)
s = int(input())

a = [-1]*(s+1)

a[0] = 1
a[1] = 0
a[2] = 0
a[3] = 1
for i in range (4,s+1):
    a[i] = a[i-1]+a[i-3]

print(a[s])


### FIXED CODE ###

s = int(input())

a = [-1]*(s+10)
mod = 10**9 + 7

a[0] = 1
a[1] = 0
a[2] = 0
a[3] = 1
if s > 3:
    for i in range (4,s+1):
        a[i] = (a[i-1]+a[i-3])%mod

print(a[s])
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, Q = MAP()
abcd = [LIST() for _ in range(Q)]
abcd.sort(key = lambda x: (x[0], x[1], x[3]))

for n in permutations(range(N)):
	print(n)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
KA = [LIST() for _ in range(N)]

S = set(KA[0][1:])
for i in range(1, N):
	S = S & set(KA[i][1:])

print(len(S))
n,m=map(int,input().split(" "))
lis2=[]
for i in range(0,n):
	lis2.append(int(input()))
lis2=sorted(lis2,reverse=True)
sum1=sum(lis2)
count=0
for i in range(0,m):
  if(lis2[i]>=((1/(4*m))*sum1)):
    count=0
  else:
    count=1
    break
if(count==1):
  print("No")
else:
  print("Yes")

### FIXED CODE ###

n,m=map(int,input().split(" "))
lis2=map(int,input().split(" "))

lis2=sorted(lis2,reverse=True)
sum1=sum(lis2)
count=0
for i in range(0,m):
  if(lis2[i]>=((1/(4*m))*sum1)):
    count=0
  else:
    count=1
    break
if(count==1):
  print("No")
else:
  print("Yes")
N = int(input())
from collections import defaultdict
flag = [0 for i in range(N)]
G = defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

numbers1 = [i for i in range(1, N+1) if i % 3 == 1]
numbers2 = [i for i in range(1, N+1) if i % 3 == 2]
numbers3 = [i for i in range(1, N+1) if i % 3 == 0]


ansl = []
for d in dist:
    if d % 2 == 0:
        if numbers1:
            ansl.append(numbers1.pop())
        else:
            ansl.append(numbers3.pop())
    else:
        if numbers2:
            ansl.append(numbers2.pop())
        else:
            ansl.append(numbers3.pop())
for a in ansl:
    print(a)



### FIXED CODE ###

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

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)


al = [0, 0]
for d in dist:
    al[d%2] += 1
if sum(al) // al[0] >= 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            ansl.append(numbers3.pop())
        else:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
elif sum(al) // al[1] >= 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
else:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            if numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
n = int(input())
l = map(int,input().split())
print("Yes" if sum(l) - max(l) > max(l) else "No")

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
print("Yes" if sum(l) - max(l) > max(l) else "No")