Harryxun/stf_run huggingface dataset:
N,M=map(int,input().split())
A=list(map(int,input().split()))

T=[0,2,5,5,4,5,6,3,7,6]
B=[]
for i in A:
    B.append(T[i])
B=sorted(list(set(B)))
dp=[0 for i in range(N+1)]
AB=[[i,T[i]] for i in A]
AB=sorted(AB,reverse=True)

for i in range(1,N+1):
    for j in B:
        if i-j>=0 and dp[i-j]!=-1:
            dp[i]=max(dp[i],dp[i-j]+1)
            #print(i,j,dp[i])
    if dp[i]==0:
        dp[i]=-1
#print(dp)
#print(AB)

c=N
U=[0 for i in range(8)]
while c>0:
    for i in range(len(AB)):
        if dp[c]==dp[c-AB[i][1]]+1:
            U[AB[i][1]]+=1
            c-=AB[i][1]
            break
#print(U)

ans=""
if 9 in A:
    ans+='9'*U[6]
    U[6]=0
if 8 in A:
    ans+='8'*U[7]
if 7 in A:
    ans+='7'*U[3]
if 6 in A:
    ans+='6'*U[6]
if 5 in A:
    ans+='5'*U[5]
    U[5]=0
if 4 in A:
    ans+='4'*U[4]
if 3 in A:
    ans+='3'*U[5]
    U[5]=0
if 2 in A:
    ans+='2'*U[5]
if 1 in A:
    ans+='1'*U[2]

print(ans)

### FIXED CODE ###

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

T=[0,2,5,5,4,5,6,3,7,6]
B=[]
for i in A:
    B.append(T[i])
B=sorted(list(set(B)))
dp=[0 for i in range(N+1)]
AB=[[i,T[i]] for i in A]
AB=sorted(AB,reverse=True)

for i in range(1,N+1):
    for j in B:
        if i-j>=0 and dp[i-j]!=-1:
            dp[i]=max(dp[i],dp[i-j]+1)
            #print(i,j,dp[i])
    if dp[i]==0:
        dp[i]=-1
#print(dp)
#print(AB)

c=N
U=[0 for i in range(8)]
while c>0:
    for i in range(len(AB)):
        if c-AB[i][1]>=0 and dp[c]==dp[c-AB[i][1]]+1:
            U[AB[i][1]]+=1
            c-=AB[i][1]
            break
#print(U)

ans=""
if 9 in A:
    ans+='9'*U[6]
    U[6]=0
if 8 in A:
    ans+='8'*U[7]
if 7 in A:
    ans+='7'*U[3]
if 6 in A:
    ans+='6'*U[6]
if 5 in A:
    ans+='5'*U[5]
    U[5]=0
if 4 in A:
    ans+='4'*U[4]
if 3 in A:
    ans+='3'*U[5]
    U[5]=0
if 2 in A:
    ans+='2'*U[5]
if 1 in A:
    ans+='1'*U[2]

print(ans)
data = []
try:
    while True:
        data.append(raw_input())

except EOFError:
        pass

for i in data:
    a, b, c, d, e, f = i.split()
    a, b, c, d, e, f = int(a), int(b), int(c), int(d), int(e), int(f)
    if abs(a) or abs(b) or abs(c) or abs(d) or abs(e) or abs(f) <= 1000:
        for j in range(-1000, 1001):
            if j != 0:
                y1 = (c - (a*j)) / float(b)
                y2 = (f - (d*j)) / float(e)
                if y1 == y2: 
                    print "{:.4f} {:.4f}".format(j, y1) 
                    break

### FIXED CODE ###

data = []
try:
    while True:
        data.append(raw_input())

except EOFError:
    pass

for i in data:
    a, b, c, d, e, f = map(float, (i.split()))
    if (abs(a) <= 1000
        and abs(b) <= 1000
        and abs(c) <= 1000
        and abs(d) <= 1000
        and abs(e) <= 1000
        and abs(f) <= 1000):
        y = (a*f - c*d) / (a*e - b*d)
        x = (c - b*y) / a
        print "{:.3f} {:.3f}".format(x, y)
n = int(input())

if(n == 0):
    printf(1)
else if(n == 1):
    printf(0)

### FIXED CODE ###

n = int(input())

if(n == 0):
    print(1)
elif(n == 1):
    print(0)
H, W = map(int, input().split())
S = [int(input()) for _ in range(W)]
    
floor = list(range(0,H+1))

if S.count(1) >0:
	floor[1]=0
	floor[2]=1
if S.count(2) >0:
    floor[2]=0

for i in range (3, H+1):
		floor[i]=floor[i-2]*(1-S.count(i-2))+floor[i-1]*(1-S.count(i-1))
print(floor[H]%(10**9+7))

### FIXED CODE ###

a, b, c = map(int, input().split())
print(a+b+c-max(a,b,c))
A = input()
B = input()
C = input()

#配列の次のカードの文字を返す
def next(X, i):
    if X[i] == 'a':
        return A[i]
    elif X[i] == 'b':
        return B[i]
    else:
        return C[i]

xa = 0
xb = 0
xc = 0

h = 'A'
k = next(A, xa) #最初
xa += 1

while xa < len(A) and xb <len(B) and xc < len(C):
    if k == 'a':
        h = 'A'
        k = next(A, xa)
        xa += 1
    elif k == 'b':
        h = 'B'
        k = next(B, xb)
        xb += 1
    else:
        h = 'C'
        k = next(C, xc)
        xc += 1

print(h)


### FIXED CODE ###

A = input()
B = input()
C = input()

xa = 0
xb = 0
xc = 0

h = 'A'
k = A[0] #最初の１枚を抜く
xa += 1

while True:

    if k == 'a':
        h = 'A'
        if xa < len(A):
            k = A[xa]
            xa += 1
        else:
            break
    elif k == 'b':
        h = 'B'
        xb += 1
        if xb < len(B):
            k = B[xb]
            xb += 1
        else:
            break
    elif k == 'c':
        h = 'C'
        xc += 1
        if xc < len(C):
            k = C[xc]
            xc += 1
        else:
            break

print(h)
N,K = map(int,input().split())
X = list(map(int,input().split()))
m = float("inf")
for i in range(N-K+1):
    if X[i] > 0:
        d = X[i+K-1]
    elif X[i+K-1] < 0:
        bgd = -X[i]
    else:
        d = X[i+K-1]-X[i]+min(-X[i],X[i+K-1])
    m = min(m,d)
print(m)

### FIXED CODE ###

N,K = map(int,input().split())
X = list(map(int,input().split()))
m = 2*(abs(X[-1])+abs(X[0]))
for i in range(N-K+1):
    if X[i] > 0:
        d = X[i+K-1]
    elif X[i+K-1] < 0:
        d = -X[i]
    else:
        d = X[i+K-1]-X[i]+min(-X[i],X[i+K-1])
    m = min(m,d)
print(m)
abc='abcdefghijklmnopqrstuvwxyz'
s=raw_input().strip()
isi=dict()
for l in s:


### FIXED CODE ###

abc='abcdefghijklmnopqrstuvwxyz'
s=raw_input().strip()
isi=set()
for l in s:
    if l not in isi:
        isi.add(l)
for l in abc:
    if l not in isi:
        print l
        break
else:
    print 'None'
import sys
input = sys.stdin.readline

n, l, t = map(int, input().split())
XW = [list(map(int, input().split())) for _ in range(n)]
L = []
for i, xw in enumerate(XW):
  x, w = xw
  if w == 1:
    L.append((x+t)%l)
  else:
    L.append((x-t)%l)
L.sort()
x_0, w_0 = XW[0]
b = 0
for x, w in XW[1:]:
  if w_0 == w:
    continue
  if w_0 == 1:
    if x-x_0 > 2*t:
      continue
    b += 1 + (2*t - (x-x_0)) // l
  else:
    if l-(x-x_0) > 2*t:
      continue
    b -= 1 + (2*t - (l-(x-x_0))) // l
m = L.index(L[b])
for i in range(m, m+n):
  print(L[i%n])

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, l, t = map(int, input().split())
XW = [list(map(int, input().split())) for _ in range(n)]
L = []
cnt = 0
for i, xw in enumerate(XW):
  x, w = xw
  L.append((x+t*(3-2*w))%l)
  cnt += (x+t*(3-2*w))//l
L.sort()
for i in range(cnt, cnt+n):
  print(L[i%n])
import numpy as np
from scipy.sparse.csgraph import *
xs, ys, xt, yt = [int(_) for _ in input().split()]
N = int(input())
XYR = np.array([[xs, ys, 0]] + [[int(_) for _ in input().split()]
                                for _ in range(N)] + [[xt, yt, 0]])
edge = [[0] * (N + 2) for _ in range(N + 2)]
for i in range(N + 1):
    for j in range(i + 1, N + 2):
        edge[i][j] = edge[j][i] = max(
            ((XYR[i][0] - XYR[j][0])**2 +
             (XYR[i][1] - XYR[j][1])**2)**0.5 - XYR[i][2] - XYR[j][2], 0)
G = csgraph_from_dense(edge, null_value=10**10)
print(dijkstra(G, directed=False, indices=0)[-1])


### FIXED CODE ###

from heapq import *

xs, ys, xt, yt = [int(_) for _ in input().split()]
N = int(input())
XYR = [[xs, ys, 0]] + [[int(_) for _ in input().split()]
                       for _ in range(N)] + [[xt, yt, 0]]
G = [[0] * (N + 2) for _ in range(N + 2)]
for i in range(N + 1):
    for j in range(i + 1, N + 2):
        G[i][j] = G[j][i] = max(
            ((XYR[i][0] - XYR[j][0])**2 +
             (XYR[i][1] - XYR[j][1])**2)**0.5 - XYR[i][2] - XYR[j][2], 0)


def dijkstra(V, G, start):
    INF = float('inf')
    D = [INF for _ in range(V)]
    D[start] = 0
    H = [(0, start)]
    while H:
        du, u = heappop(H)
        if D[u] < du:
            continue
        for v, d in enumerate(G[u]):
            if D[v] > du + d:
                D[v] = du + d
                heappush(H, (D[v], v))
    return D


D = dijkstra(N + 2, G, 0)
print(D[-1])
def main():
    h,w = map(int,input().split(" "))
    s = [list(input()) for i in range(h)]
    
    dp = [[0]*h for i in range(w)]
    dp[0][0] = 1 if s[0][0]=="#" else 0

    for i in range(1,h):
        sgmdown = 1 if s[i][0]=="#" and s[i-1][0]=="." else 0
        dp[i][0] = dp[i-1][0] + sgmdown
    
    for j in range(1,w):
        sgmright = 1 if s[0][j]=="#" and s[0][j-1]=="." else 0
        dp[0][j] = dp[0][j-1] + sgmright

    for i in range(1,h):
        for j in range(1,w):
            sgmdown = 1 if s[i][j]=="#" and s[i-1][j]=="." else 0
            sgmright = 1 if s[i][j]=="#" and s[i][j-1]=="." else 0
            dp[i][j] = min(dp[i-1][j]+sgmdown, dp[i][j-1]+sgmright)

    print(dp[h-1][w-1])
main()

### FIXED CODE ###

def main():
    h,w = map(int,input().split(" "))
    s = [list(input()) for i in range(h)]
    
    dp = [[0]*w for i in range(h)]
    dp[0][0] = 1 if s[0][0]=="#" else 0

    for i in range(1,h):
        sgmdown = 1 if s[i][0]=="#" and s[i-1][0]=="." else 0
        dp[i][0] = dp[i-1][0] + sgmdown
    
    for j in range(1,w):
        sgmright = 1 if s[0][j]=="#" and s[0][j-1]=="." else 0
        dp[0][j] = dp[0][j-1] + sgmright

    for i in range(1,h):
        for j in range(1,w):
            sgmdown = 1 if s[i][j]=="#" and s[i-1][j]=="." else 0
            sgmright = 1 if s[i][j]=="#" and s[i][j-1]=="." else 0
            dp[i][j] = min(dp[i-1][j]+sgmdown, dp[i][j-1]+sgmright)

    print(dp[h-1][w-1])
main()
a,b,c = tuple(map(int,input().split()))
if a==b and b==c:
  print(-1)
ans = 0
else:
  while True:
    if a%2==0 and b%2==0 and c%2==0:
      a,b,c == b//2+c//2,c//2+a//2,a//2+b//2
      ans+=1
    else:
      break
      
print(ans)

### FIXED CODE ###

a,b,c = tuple(map(int,input().split()))
if len(set((a,b,c)))==1 and a%2==1:
    print(0)
    exit()
ans = 0
while True:
  if len(set((a,b,c)))==1:
    print(-1)
    exit()
  if a%2==0 and b%2==0 and c%2==0:
    a,b,c = b//2+c//2,c//2+a//2,a//2+b//2
    ans+=1
  else:
    break
print(ans)
from sys import stdin
import math
import itertools


def makeIntMatrix(lines):
    intMatrix = []
    for a in makeStringMatrix(lines):
        intMatrix.append([int(b) for b in a])
    return intMatrix
 
 
def makeStringMatrix(lines):
    stringMatrix = [line.split() for line in lines]
    return stringMatrix
 
 
def makeInt(line):
    return int(line.rstrip())
 
 
def makeMultiInteger(line):
    return [int(x) for x in line.rstrip().split()]

from bisect import bisect_left
def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return i
    else:
        return 0

def solve(input_string):
    N, M = makeMultiInteger(input_string[0])
    A = makeMultiInteger(input_string[1])
    _S = makeIntMatrix(input_string[2:])
    cards = sorted(A)
    S = sorted(_S, key=lambda x: x[1], reverse=True)

    i = 1
    while(True):
        b = S[i][0]
        c = S[i][1]
        if S[i-1][1] == c:
            S[i-1][0] += b
            del S[i]
            i -= 1
        i += 1
        if i < len(S):
            break

    for s in S:
        b = s[0]
        c = s[1]
        if c > cards[0]:
            for i in range(b):
                if c > cards[i]:
                    cards[i] = c
                else:
                    break
            part_cards = cards[b:]
            s_l = find_lt(part_cards, cards[0])
            if s_l != 0:
                cards = part_cards[:s_l] + cards[0:b] + part_cards[s_l:]
        else:
            break
    return sum(cards)

def main():
    input_lines = stdin.readlines()
    answer = solve(input_lines)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# from sys import exit
N, M = [int(n) for n in input().split()]
# N = int(input())
a = [(int(n), 1) for n in input().split()]
B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    B[i], C[i] = [int(n) for n in input().split()]
    a.append((C[i], B[i]))

a = sorted(a, key=lambda x: -x[0])
i = 0
ans = 0
# print(a)
while(N != 0):
    num = min(N, a[i][1])
    ans += num*a[i][0]
    # print(num*a[i][0])
    N -= num
    i += 1

print(ans)
# C - Linear Approximation
# https://beta.atcoder.jp/contests/abc102/tasks/arc100_a

# C_Linear_Approximation.py

# 7
# 1 1 1 1 2 3 4
#import sys

N = int(input())
a = list(map(int, input().strip().split(" ")))

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

a.sort()
if N % 2 != 0:
    mid = (N-1)//2
else:
    mid = N // 2 -1
b = a[mid]

sadness_left = b * mid - sum(a[:mid])
sadness = sum(a) - b * N + sadness_left * 2

print(sadness)


### FIXED CODE ###

# A - Multiple of 2 and N
# https://beta.atcoder.jp/contests/abc102/tasks/abc102_a

# A_Multiple_of_2_and_N.py

N = int(input())

if N == 1:
    print(2)
elif N%2 == 0:
    print(N)
else:
    print(N*2)
N = int(input())
Z=[]
for i in range(N):
	t, x, y = map(int, input().split())
	if t % 2 == 0:
		if x + y <= t and (x + y) % 2 == 0:
			Z.append(1)
		else:
			Z.append(0)
	else:
		if x + y <= t and (x + y) % 2 == 1:
			Z.append(1)
		else:
			Z.append(0)
	i += 1

if Z.index(0) >= 1:
	print('No')
else:
	print('Yes')

### FIXED CODE ###


N = int(input())
Z=[]
for i in range(N):
	t, x, y = map(int, input().split())
	if t % 2 == 0:
		if x + y <= t and (x + y) % 2 == 0:
			Z.append(1)
		else:
			Z.append(0)
	else:
		if x + y <= t and (x + y) % 2 == 1:
			Z.append(1)
		else:
			Z.append(0)
	i += 1
if Z.count(0) >=1:
	print('No')
else:
	print('Yes')
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
import numpy as np
n,W = mi()
a = [tuple(int(i) for i in input().split()) for _ in range(n)]
dp = np.array([0]*(W+1))
for w,v in a:
    ed = W+1-w
    dp[w:W+1] = np.maximum(dp[w:ed], dp[0:ed] + v)
print(dp[W])

### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
import numpy as np
n,W = mi()
a = [tuple(int(i) for i in input().split()) for _ in range(n)]
dp = np.array([0]*(W+1))
for w,v in a:
    ed = W+1-w
    dp[w:W+1] = np.maximum(dp[w:W+1], dp[0:W+1-w] + v)
print(dp[W])
以下ペースト可
# start 21:14
a, b = [int(item) for item in input().split()]

if b > a:
    c = a
    a = b
    b = c


# 最大公約数を求める
def gcd(a, b):
    while b > 1:
        a, b = b, a%b
    return a

# 公約数でかつ素数の_listを求める
prime_devisor_list = [1]

import math

def is_prime(num):
    if num in [1, 2]:
        return True
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

for i in range(3, gcd(a, b)+1):
    if a % i == 0 and b % i == 0:
        # i can be ans
        # check pirme

        if is_prime(i):
            prime_devisor_list.append(i)

# 数をこたえる
print(len(prime_devisor_list))

### FIXED CODE ###

# start 21:14
a, b = [int(item) for item in input().split()]

# 素因数リスト
import math
def factor(num):
    divisor_list = [1]
    divisor = 2
    max_prime = int(math.sqrt(num))
    while max_prime >= divisor:
        if num % divisor == 0:
            divisor_list.append(divisor)
            num //= divisor

        else:
            divisor += 1
    divisor_list.append(num)
    return divisor_list

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

cd_list = set(factor(gcd(a, b)))

print(len(cd_list))
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ab_total_list = []
total_list = []

A.sort()
A.reverse()
if len(A) > K:
    A = A[0:K+1]

B.sort()
B.reverse()
if len(B) > K:
    B = B[0:K+1]

C.sort()
C.reverse()
if len(C) > K:
    C = C[0:K+1]

ab_total_list = []
for i in A:
    for j in B:
        ab_total_list.append(i+j)

ab_total_list.sort()
ab_total_list.reverse()
if len(ab_total_list) > K:
    ab_total_list = ab_total_list[0:K+1]

z = 0
min_total = 0
if K > len(ab_total_list):
    min_total = ab_total_list[-1]
else:
    min_total = ab_total_list[K]

for i in range(0, K):
    for j in range(0, int(K/(i+1))):
        if j >= len(C) or i >= len(ab_total_list):
            break
        total = ab_total_list[i] + C[j]
        total_list.append(total)
        if (i*j) > K:
            break

total_list.sort()
total_list.reverse()
for i in range(0, K):
    print(total_list[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ab_total_list = []
total_list = []

A.sort()
A.reverse()
if len(A) > K:
    A = A[0:K+1]

B.sort()
B.reverse()
if len(B) > K:
    B = B[0:K+1]

C.sort()
C.reverse()
if len(C) > K:
    C = C[0:K+1]

ab_total_list = []
for i in A:
    for j in B:
        ab_total_list.append(i+j)

ab_total_list.sort()
ab_total_list.reverse()
if len(ab_total_list) > K:
    ab_total_list = ab_total_list[0:K+1]

for i in range(0, K):
    for j in range(0, int(K/(i+1))):
        if j >= len(C) or i >= len(ab_total_list):
            break
        total = ab_total_list[i] + C[j]
        total_list.append(total)
        if (i*j) > K:
            break

total_list.sort()
total_list.reverse()
for i in range(0, K):
    print(total_list[i])
input_list = input()
 
result = input_list[0]*input_list[1]
 
if result % 2 == 0:
  print('Even')
else:
  print('Odd')

### FIXED CODE ###

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

result = x*y
 
if result % 2 == 0:
  print('Even')
else:
  print('Odd')
import math
import numpy as np



N = int(input())
T = []

for i in range(N):
    t = int(input())
    T.append(t)

print(np.lcm.reduce(T))


### FIXED CODE ###

import fractions
n=int(input())
ans=int(input())
for i in range(n-1):
  t=int(input())
  ans=(ans*t)//fractions.gcd(t,ans)
print(ans)
import math

A,B,K=map(int,input().split())
gcd=math.gcd(A,B)
#print(gcd)
l=[]
for i in range(1,gcd+1):
    if gcd%i==0:
        l.append(i)
#print(l)
print(l[len(l)-K])

### FIXED CODE ###

import fractions

A,B,K=map(int,input().split())
gcd=fractions.gcd(A,B)
#print(gcd)
l=[]
for i in range(1,gcd+1):
    if gcd%i==0:
        l.append(i)
#print(l)
print(l[len(l)-K])
#!/usr/bin/env python3

Alice, Bob = map(int, input())
if Alice == 1:
    Alice = 14
if Bob == 1:
    Bob = 14

if Alice > Bob:
    print('Alice')
elif Bob > Alice:
    print('Bob')
else:
    print('Draw')

### FIXED CODE ###

#!/usr/bin/env python3

Alice, Bob = map(int, input().split())
if Alice == 1:
    Alice = 14
if Bob == 1:
    Bob = 14

if Alice > Bob:
    print('Alice')
elif Bob > Alice:
    print('Bob')
else:
    print('Draw')
def common():
????X = raw_input()
  Y = raw_input()
????a = len(x)
????b = len(y)
????k1 = [0 for i in range(b+1)]
????
????for i in range(a):
????????k2 = k1 + []
????????for j in range(b):
????    if X[i] == Y[j]:
?????????????? k1[j+1] = k2[j] + 1
      elif k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]
  
  return k1[-1]

n = input()
for l in range(n):
????print common()

### FIXED CODE ###

def common():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  k1 = [0 for i in range(b+1)]
 
  for i in range(a):
     k2 = k1 + []
     for j in range(b):
       if X[i] == Y[j]:
          k1[j+1] = k2[j] + 1
       elif k1[j+1] < k1[j]:
          k1[j+1] = k1[j]
 
  return k1[-1]
 
n = input()
for l in range(n):
  print common()
a, b = map(int input().split())
print(max(a + b, a - b, a * b))

### FIXED CODE ###

a, b = map(int, input().split())
print(max(a + b, a - b, a * b))
def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    base = [i for i in range(1, 1001)]
    l = list(itertools.accumulate(base))
    r = []
    for i in range(0, len(l)):
        r.append(l[i] / (i+1))

    memo = 0
    maxi = 0
    for i in range(N-M+1):
        if maxi < sum(A[i:M+i]):
            maxi = sum(A[i:M+i])
            memo = i

    ans = 0
    for i in A[memo:M+memo]:
        ans += r[i-1]

    return ans

print(solve())

### FIXED CODE ###

import itertools

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    # スコアの累積和
    l = list(itertools.accumulate(A))

    score = sum(A[:M])
    for i in range(1, N-M):
        score = max(score, l[i+M] - l[i])
        
    ans = (M + score) / 2

    return ans

print(solve())
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

mem = [[[] for _ in range(2)] for _ in range(4)]
for i,d in enumerate(depth):
    if d==0: continue
    if d%2:
        mem[0][0].append(i)
        mem[1][1].append(i)
    else:
        mem[0][1].append(i)
        mem[1][0].append(i)
    if d==1:
        mem[2][0].append(i)
        mem[3][1].append(i)
    else:
        if ((d-2)//3)%2:
            mem[2][0].append(i)
            mem[3][1].append(i)
        else:
            mem[2][1].append(i)
            mem[3][0].append(i)

for k in range(4):
    ans = [None] * N
    for i in range(1,N+1):
        if i==3:
            ans[0] = 3
            continue
        if i%3==0:
            if len(mem[k][0])==0 and len(mem[k][1])==0:
                break
            if len(mem[k][0]) <= len(mem[k][1]):
                j = mem[k][1].pop()
            else:
                j = mem[k][0].pop()
        elif i%3==1:
            if len(mem[k][0])==0:
                break
            j = mem[k][0].pop()
        else:
            if len(mem[k][1])==0:
                break
            j = mem[k][1].pop()
        ans[j] = i
    else:
        print(*ans)
        exit()
assert False

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
if N==2:
    print(1,2)
    exit()
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

g1 = []
g2 = []
for i,d in enumerate(depth):
    if d%2:
        g2.append(i)
    else:
        g1.append(i)
if len(g1) < len(g2):
    g1,g2 = g2,g1

ans = [None] * N
if len(g2) <= N//3:
    for n in range(1,N+1):
        if n%3==0:
            if g2:
                i = g2.pop()
            else:
                i = g1.pop()
        else:
            i = g1.pop()
        ans[i] = n
else:
    for n in range(1,N+1,3):
        i = g1.pop()
        ans[i] = n
    for n in range(2,N+1,3):
        i = g2.pop()
        ans[i] = n
    for n in range(3,N+1,3):
        if g1:
            i = g1.pop()
        else:
            i = g2.pop()
        ans[i] = n
print(*ans)
l=list(map(int,input().split()))
l=sorted(l)
if s[0]+l[1]==s[2]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

l=list(map(int,input().split()))
l=sorted(l)
if (l[0]+l[1])==l[2]:
  print('Yes')
else:
  print('No')
s=input()
if s[0]=='A':
  if s[2:-2].count('C')==1:
    if (s[1]+s[2:-2].replace('C', '')+s[-1]).islower() :
  		print('AC')
    else:
      print('WA')
  else:
    print('WA')
else:
  print('WA')



### FIXED CODE ###

s=input()
if s[0]=='A':
    if s[2:-1].count('C')==1:
        if (s[1]+s[2:-1].replace('C', '')+s[-1]).islower() :
            print('AC')
        else:
            print('WA')
    else:
        print('WA')
else:
    print('WA')
a,v =map(int, input().split())
b,w =map(int, input().split())
t=int(input())
if v > w and ((v-w)**2**0.5)*t > ((a-b)**2**0.5):
    print("NO")
elif v > w:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a,v =map(int, input().split())
b,w =map(int, input().split())
t=int(input())

if a*b<0:
    if a > 0:
        d = a-b
    else:
        d = b-a
else:
    d = a-b
if d < 0:
    d = -d
if v > w:
    d2 = v-w
else:
    d2 = w-v
if  (v > w) and (d2*t < d):
    print("NO")
elif v <= w:
    print("NO")
else:
    print("YES")
N,D = map(int,input().split())
point = [list(map(int, input().split())) for x in range(N)]
count = 0
for i in range(n):
    if D >= (point[i][0]**2+point[i][1]**2)**0.5:
        count += 1
print(count)

### FIXED CODE ###

N,D = map(int,input().split())
point = [list(map(int, input().split())) for x in range(N)]
count = 0
for i in range(N):
    if D >= (point[i][0]**2+point[i][1]**2)**0.5:
        count += 1
print(count)