Harryxun/stf_run huggingface dataset:
from math import gcd
a,b=map(int,input().split())
n=gcd(a,b)

#素数
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

#素因数分解
from collections import defaultdict
primelist=primes(int(n**0.5+1))+[n+1]
factors=defaultdict(lambda :0)
for prime in primelist:
    if prime>n:
        factors[n]+=1
        break
    while n%prime==0:
        n=n//prime
        factors[prime]+=1
print(len(factors))

### FIXED CODE ###

from fractions import gcd
a,b=map(int,input().split())
n=gcd(a,b)

#素数
def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

#素因数分解
from collections import defaultdict
primelist=primes(int(n**0.5+1))+[n+1]
factors=defaultdict(lambda :0)
for prime in primelist:
    if prime>n:
        factors[n]+=1
        break
    while n%prime==0:
        n=n//prime
        factors[prime]+=1
factors[n]=1
factors[1]=0
print(len(factors))
n, m = map(int,input().split())

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

mj = []

for i in range(m):
    mj.append(list(map(int,input().split())))
    
tower = 0

for i in range(n):
    #自分からのびている道から先にある展望台を探索し、自分iと比較
    cnt = 0
    h_high = 0
    for j in range(m):
        if i+1 in mj[j]:
            cnt += 1
            if i == mj[j][0]-1:
                if h[i] > h[mj[j][1]-1]:
                    h_high += 1
            else:
                if h[i] > h[mj[j][0]-1]:
                    h_high += 1
    if cnt == h_high:
        tower += 1
        
print(len(tower))

### FIXED CODE ###

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

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

mj = []

for i in range(m):
    mj.append(list(map(int,input().split())))

cnt_w = [0 for _ in range(n)]
cnt = [0 for _ in range(n)]

for i in range(m):
    cnt[mj[i][0]-1] += 1
    cnt[mj[i][1]-1] += 1
    if h[mj[i][0]-1] > h[mj[i][1]-1]:
        cnt_w[mj[i][0]-1] += 1
    elif h[mj[i][0]-1] < h[mj[i][1]-1]:
        cnt_w[mj[i][1]-1] += 1

tower = 0
for i in range(n):
    if cnt[i] == cnt_w[i]:
        tower += 1
print(tower)
import sys
N = int(input())
A = [[(int(x),True) for x in input().split()] for _ in range(N)]

for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k][0] + A[k][j][0]
            if A[i][j][0] > Aikj:
                print(-1)
                sys.exit()
            if A[i][j][0] == Aikj:
                A[i][j][1] = False

ans = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i][j][1]:
            ans += A[i][j][0]
print(ans)

### FIXED CODE ###

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()
n = int(input())
l = [list(map(int,input().split()))]
j = 0
new = []
while True:
    for m,i in enumerate(l):
        if i % 2 == 0:
            l[i] = i/2
            if m == n:
                j +=1
        else:
            print(j)
            exit()
        

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))

j = 0
new = []
while True:
    for m,i in enumerate(l):
        if i % 2 == 0:
            l[m] = i/2
            
            if m+1 == n:
                j +=1
        else:
            print(j)
            break
    else:
        continue
    break
from collections import Counter

N = int(raw_input())

points = [map(int, raw_input().split()) for _ in xrange(N)]

# print N, points

dist = lambda p1, p2: (p1[0]-p2[0], p1[1]-p2[1])

vecs = []
for i in xrange(N):
    for j in xrange(i+1, N):
        vecs.append(dist(points[i], points[j]))

vecs_cnt = Counter(vecs)
# print Counter(vecs)
ans = max(vecs_cnt.values())

print N-ans

### FIXED CODE ###

from collections import Counter

N = int(raw_input())

points = [map(int, raw_input().split()) for _ in xrange(N)]

if N == 1:
    print 1
else:
    dist = lambda p1, p2: (p1[0]-p2[0], p1[1]-p2[1])

    vecs = []
    for i in xrange(N):
        for j in xrange(N):
            if j == i:
                continue
            vecs.append(dist(points[i], points[j]))

    vecs_cnt = Counter(vecs)
    # print Counter(vecs)
    ans = max(vecs_cnt.values())

    print N-ans
def main():
    N, C, K = map(int, input().split())
    T = [int(input()) for _ in range(N)]
    ans = 0
    i = 0
    j = 0
    T.sort()
    if len(T) == 1:
        ans = 1
        return(ans)

    if C == 1:
        return(N)

    if C == 2:
        while True:
            if T[j] + K >= T[i+1]:
                i = i + 2
                j = i
                ans += 1
                if j == N:
                    return ans
                elif j == N - 1:
                    ans += 1
                    return ans
            elif T[j] + K < T[i+1]:
                i += 1
                j = i
                ans += 1
                if j == N-1:
                    ans += 1
                    return ans

    while True:
        if T[j] + K >= T[i+1]:
            i = i + 1
            if i == N-1:
                ans += 1
                return (ans)
            for h in range(C-2):
                if T[j] + K >= T[i+1]:
                    if h == C-3:
                        ans += 1
                        i += 2
                        j = i
                        if j >= N-1:
                            return(ans)
                        break
                    else:
                        i += 1
                        if (i+1) == N-1:
                            ans += 1
                            return(ans)
                        continue
                elif T[j] + K < T[i + 1]:
                    j = i + 1
                    i = i + 1
                    ans += 1
                    if j == N-1:
                        ans += 1
                        return(ans)
                    break

        elif T[j] + K < T[i+1]:
            ans += 1
            i += 1
            j = i
            if j == N-1:
                ans += 1
                return(ans)

print(main())


### FIXED CODE ###

def main():
    N, C, K = map(int, input().split())
    T = list(int(input()) for _ in range(N))

    T.sort()

    ans = 0
    temp = T[0]
    cnt = 1

    for i in range(1,N):
        if temp + K < T[i] or C == cnt:
            ans += 1
            temp = T[i]
            cnt = 1
        else:
            cnt += 1

    ans += 1
    return (ans)

print(main())
N, M = [int(a) for a in input().split(" ")]
X = sorted([int(a) for a in input().split(" ")])
intervals = [a-b for a, b in zip(X[1:], X[:-1])]
prev, curr = [0]*(M-1), [0]*(M-1)

if M==1:
    print(0)
else:
    maxv = 0
    for i in range(M-1):
        maxv = max(intervals[i], maxv)
        prev[i] = maxv

    for i in range(N-2):
        curr[i+1] = -10**10
        for j in range(i+2, M-1):
            curr[j] = max(prev[j-2]+intervals[j], curr[j-1])
        prev, curr = curr, prev
    print(sum(intervals)-prev[-1])

### FIXED CODE ###

N, M = [int(a) for a in input().split(" ")]
X = sorted([int(a) for a in input().split(" ")])
intervals = sorted([a-b for a, b in zip(X[1:], X[:-1])])[::-1]
if M > N:
    print(sum(intervals) - sum(intervals[:N-1]))
else:
    print(0)
import numpy as np
N,M=map(int,input().split())
S = input()
T = input()
g = np.gcd(M,N)
n = N//g
m = M//g
l = N*M // g
f = True
for i in range(g):
    a = n*i
    b = m*i
    if S[a] != T[b]:
        f = False
print(l if f else -1)

### FIXED CODE ###

def gcd(x,y):
    a = max(x,y)
    b = min(x,y)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b
N,M=map(int,input().split())
S = input()
T = input()
g = gcd(M,N)
n = N//g
m = M//g
l = N*M // g
f = True
for i in range(g):
    a = n*i
    b = m*i
    if S[a] != T[b]:
        f = False
print(l if f else -1)
from itertools import accumulate
import numpy as np
N=int(input())
L=[26**(i+1) for i in range(15)]
sL=list(accumulate(L))
result=[]
k=0
for i in range(10):
    if N<=sL[i] and N>=26:
        N-=sL[i-1]
        k=i
        break
for m in range(k):
    time=0
    while N>=L[k-m-1]:
        N-=L[k-m-1]
        time+=1
    result.append(chr(time+97))
result.append(chr(N+96))
print(''.join(result))

### FIXED CODE ###

from itertools import accumulate
import numpy as np
N=int(input())
N-=1
L=[26**(i+1) for i in range(15)]
sL=list(accumulate(L))
result=[]
k=0
for i in range(15):
    if N+1<=sL[i] and N>=25:
        N-=sL[i-1]
        k=i
        break
for m in range(k):
    time=0
    while N>=L[k-m-1]:
        N-=L[k-m-1]
        time+=1
    result.append(chr(time+97))
result.append(chr(N+97))
print(''.join(result))
a, b, c, d = list(input())
if 0 < 10*a + b <= 12 and 0 < c*10 + d <= 12:
    print('AMBIGUOUS')
elif 10*a + b >= 12 and 0 < c*10 + d <= 12:
    print('YYMM')
elif 0 < 10*a + b <= 12 and c*10 + d >= 12:
    print('MMYY')
else:
    print('NA')

### FIXED CODE ###

a, b, c, d = list(input())
a = int(a)
b = int(b)
c = int(c)
d = int(d)
if 0 < 10*a + b <= 12 and 0 < c*10 + d <= 12:
    print('AMBIGUOUS')
elif (10*a + b >= 12 or a + b == 0) and 0 < c*10 + d <= 12:
    print('YYMM')
elif 0 < 10*a + b <= 12 and (c*10 + d >= 12 or c + d == 0):
    print('MMYY')
else:
    print('NA')
class ATherefore:
    def solve(self, tc=0):
        n = int(input())
        if n % 10 in [2, 4, 5, 7, 9]:
            print("hon")
        elif n % 10 in [0, 1, 6, 8]:
            print("pon")
        else:
            print("bon")

x = Atherefore()
x.solve()

### FIXED CODE ###

class ATherefore:
    def solve(self, tc=0):
        n = int(input())
        if n % 10 in [2, 4, 5, 7, 9]:
            print("hon")
        elif n % 10 in [0, 1, 6, 8]:
            print("pon")
        else:
            print("bon")


x = ATherefore()
x.solve()
i = list(map(int, input().split()))
print("Yes" if i[0]>i[1]*1[2] else "No")


### FIXED CODE ###

i = list(map(int, input().split()))
print("Yes" if i[0]<=i[1]*i[2] else "No")
import math
n = int(input())
from collections import defaultdict
d = defaultdict(list)
s = set()
for i in range(n):
    a,b = map(int, input().split())
    g = math.gcd(a,b)
    a //= g; b //= g
    if a<0:
        a,b = -a, -b
    d[a,b].append(i)
v = 1
s = set()
M = 10**9+7
for (a,b),val in d.items():
    aa,bb = b,-a
    if aa<0:
        aa,bb = -aa, -bb
    if (a,b) in s or (aa,bb) in s:
        continue
    if (aa,bb) in d.keys():
        v *= (pow(2, len(val), M) + pow(2, len(d[aa,bb]), M) - 1)
    else:
        v *= pow(2, len(val), M)
    v %= M
    s.add((a,b))
    s.add((aa,bb))
v -= 1
print(v%M)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



import bisect
from math import gcd
n = int(input())
l = [None] * n
for i in range(n):
    a,b = map(int, input().split())
    g = gcd(a,b)
    if g==0:
        g = 1
    l[i] = (a//g, b//g)

l.sort()
M = 1000000007
seen = [False] * n
vals = []

def sub(item):
    item1 = (item[1], -item[0])
    item2 = (-item[1], item[0])
    tmp = None
    count = 0
    li = bisect.bisect_left(l, item1)
    ri = bisect.bisect_right(l, item1)
    count += (ri-li)
    for v in range(li, ri):
        seen[v] = True
    if ri>li:
        tmp = l[li]
        
    li = bisect.bisect_left(l, item2)
    ri = bisect.bisect_right(l, item2)
    count += (ri-li)
    for v in range(li, ri):
        seen[v] = True
    if ri>li:
        tmp = l[li]
    
    return count, tmp
zcount = 0
for i,item in enumerate(l):
    if seen[i]:
        continue
    elif item==(0,0):
        zcount += 1
        continue
    count,tmp = sub(item)
    if count>0:
        count2, tmp = sub(tmp)
        vals.append((pow(2,count,M)+pow(2,count2,M)-1)%M)
    else:
        vals.append(2)
ans = 1
for v in vals:
    ans *= v
    ans %= M
ans -= 1
ans = (ans+zcount) % M
print(ans)
from functools import reduce
import fractions

N = int(input())

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

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

l = lcm(*A)
num=0
for a in A:
  num += l/a
print(int(num % (10e9 +7)))




### FIXED CODE ###

from fractions import gcd

N = int(input())

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

l = A[0]
for a in A:
  l = (l * a) // gcd(l,a)
num=0
for a in A:
  num += l//a
print(num % (10**9 +7))
A,B,K = map(int,input.split())
ans =[]
for i in range(1, min(A,B)+1):
  if A%i == 0 and B%i == 0:
    ans.append(i)
  if len(ans) == K:
    print(len(ans))
    exit(1)
    
      


### FIXED CODE ###

A,B,K = map(int,input().split())
ans =[]
for i in range(1, min(A,B)+1):
    if A%i == 0 and B%i == 0:
        ans.append(i)
    

print(ans[-K])
x = input()
a = intput()
 
 
 
 
if x < a:
  print("0")
else:
  print("10")

### FIXED CODE ###

i = list(map(int, input().split()))
if i[0] < i[1]:
  print("0")
else:
  print("10")
N, M = map(int, input().split())
AC = set()
wa = [0] * (N+1)

for _ in range(M):
    p, s = input().split()
    p = int(p)
    if not p in AC:
        if s == 'AC':
            AC.add(p)
        if s == 'WA':
            wa[p] += 1

wa_ans = 0
for i in range(1,N+1):
    if i in AC:
        wa_ans += wa[i]

print(len(AC), wa_ans)

### FIXED CODE ###

import sys
alp = "abcdefghijklmnopqrstuvwxyza"
C = input()
for i in range(26):
    if alp[i] == C:
        print(alp[i+1])
        sys.exit()
n = int(input())
h = list(map(int,input().split()))

def dp(i):
    if i == 0:
        return 0
    elif i == 1:
        return abs(h[1]-h[0])
    else:
        return min(dp(i-2)+abs(h[i]-h[i-2]),dp(i-1)+abs(h[i]-h[i-1]))

print(dp(n-1))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000) 

n = int(input())
h = list(map(int,input().split()))
dp_ = [-1]*n

def dp(i):
    if dp_[i]!=-1:
        return dp_[i]
    if i == 0:
        dp_[i] = 0
    elif i == 1:
        dp_[i] = abs(h[1]-h[0])
    else:
        dp_[i] = min(dp(i-2)+abs(h[i]-h[i-2]),dp(i-1)+abs(h[i]-h[i-1]))
    return dp_[i]

print(dp(n-1))
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path
from itertools import permutations

input = sys.stdin.readline
ans = -1

n, m, r = map(int, input().split())
r  = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(m):
    a, b, c = map(int, input().split())
    A.extend(a-1)
    B.extend(b-1)
    C.extend(c)

wf = shortest_path(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        cand += int(wf[r1-1][r2-1])
    if ans < 0 or ans > cand:
        ans = cand

print(ans)


### FIXED CODE ###

import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

input = sys.stdin.readline
ans = -1

n, m, r = map(int, input().split())
r  = list(map(int, input().split()))
A, B, C = [], [], []
for i in range(m):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)

wf = floyd_warshall(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)

for pi in permutations(r):
    cand = 0
    for r1, r2 in zip(pi, pi[1:]):
        cand += int(wf[r1-1][r2-1])
    if ans < 0 or ans > cand:
        ans = cand

print(ans)
# -*- coding: utf-8 -*-
from numpy.linalg import solve

n = int(input())
a = list(map(int, input().split()))
a = [_a * 2 for _a in a]

x = [[0]*n for _ in range(n)]
for i in range(n-1):
    x[i][i] = 1
    x[i][i+1] = 1
x[n-1][n-1] = 1
x[n-1][0] = 1

print(" ".join(map(str, map(int, list(solve(x, a))))))


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))

x = [0 for _ in range(n)]
_x = 0
for i, _a in enumerate(a):
    if i % 2 == 0:
        _x += _a
    else:
        _x -= _a

x[0] = _x

for i in range(1, n):
    x[i] = a[i-1] * 2 - x[i-1]

print(" ".join(map(str, x)))
import sys
from collections import deque

N, K = map(int, sys.stdin.readline().strip().split())
tmp = list(map(int, sys.stdin.readline().strip().split()))

A = [a-1 for a in tmp]

visited = set()
loop = []

q = deque()
q.append(0)
start = float("inf")
end = float("inf")

count = 0
while q and count < K:
    s_town = q.popleft()
    # ループを確認
    if s_town in visited:
        start = loop.index(s_town)
        end = len(loop)
        break
    visited.add(s_town)
    loop.append(s_town)
    n_town = A[s_town]
    q.append(n_town)
    count += 1

# print(start, end)
if start >= K:
    print(loop[K]+1)
else:
    res = K - start
    res %= (end - start)
    # print("res", res)
    print(loop[start + res]+1)

### FIXED CODE ###

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().strip().split())
tmp = list(map(int, sys.stdin.readline().strip().split()))

A = [a-1 for a in tmp]

visited = set()
loop = []

q = deque()
q.append(0)
start = float("inf")
end = float("inf")

count = 0
while q and count <= N:
    s_town = q.popleft()
    # ループを確認
    if s_town in visited:
        start = loop.index(s_town)
        end = len(loop)
        break
    visited.add(s_town)
    loop.append(s_town)
    n_town = A[s_town]
    q.append(n_town)
    count += 1

# print(start, end)
if start >= K:
    print(loop[K]+1)
else:
    res = K - start
    res %= (end - start)
    # print("res", res)
    print(loop[start + res]+1)
a=input('input a')
b=input('input b')
c=a*b
if c % 2 == 0:
    print('Even')
else:
    print('Odd')


### FIXED CODE ###

a,b=map(int,input().split())
if a*b%2 == 0:
    print('Even')
else:
    print('Odd')
x,k,d = map(int,input().split())
jud = x//d
if(k==1):
  print(abs(abs(x)-d))
elif(jud == 0):
  if((k%2 == 1):
    print(abs(abs(x)-d))
  else:
    print(abs(x))
elif(k<=jud+1):
  print(abs(abs(x)-d*k))
else:
  if((k-jud)%2 == 1):
    print(abs(abs(x)-(jud+1)*d))
  else:
    print(abs(abs(x)-(jud)*d))


### FIXED CODE ###

x,k,d = map(int,input().split())
x = abs(x)
jud = x//d
if(k<=jud):
  print(abs(abs(x)-d*k))
else:
  if((k-jud)%2 == 1):
    print(abs(abs(x)-(jud+1)*d))
  else:
    print(abs(abs(x)-(jud)*d))
N,M=map(int,input().split())
A=[0]*M
import collections
table=collections.defaultdict(list)
C=[set() for i in range(M)]
for i in range(M):
  a,b=map(int,input().split())
  A[i]=a
  c=list(map(int,input().split()))
  C[i]=set(c)
  for x in c:
    table[x].append((a,i))

opened=set()
used=set()
for i in range(1,N+1):
  if used & C[i]:
    opened.add(i)
    continue
  table[i].sort(key=lambda x:x[0])
  used.add(table[i][0][1])
  opened.add(i)
ans=0
for x in used:
  ans+=A[x]
print(ans)
  
  
  
  

### FIXED CODE ###

N,M=map(int,input().split())
A=[0]*M
import heapq
import collections
from itertools import permutations
table=collections.defaultdict(list)
AC=[[0,0] for i in range(M)]
C=[set() for i in range(M)]
for i in range(M):
  a,b=map(int,input().split())
  AC[i][0]=a
  tmp=set(map(int,input().split()))
  for x in tmp:
    AC[i][1] |= 1<<(x-1)
dp=[10**9]*(2**N)
dp[0]=0

for i in range(1,2**N):
  k=0
  s=set()
  for j in range(1,i):
    if i & j == j:
      dp[i]=min(dp[i],dp[j]+dp[i^j])
  for a,c in AC:
    if c&i == i:
      dp[i]=min(dp[i],a)
  #print(dp[i],bin(i))
  
if dp[-1]==10**9:
  print(-1)
else:
  print(dp[-1])
#print(dp)

  
  
#print(AC)
import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
from fractions  import gcd

input=sys.stdin.readline
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=[0]*(x*y)
c.sort(reverse=True)
for i in range(x):
    for j in range(y):
        ab[y*i+j]=a[i]+b[j]
ab.sort(reverse=True)
d=ab[:k]
ans=[0]*(k*z)
for i in range(k):
    for j in range(z):
        ans[z*i+j]=d[i]+c[j]
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

import sys
#import numpy as np
import math
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
from fractions  import gcd

input=sys.stdin.readline
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=[0]*(x*y)
c.sort(reverse=True)
for i in range(x):
    for j in range(y):
        ab[y*i+j]=a[i]+b[j]
ab.sort(reverse=True)
d=ab[:k]
ans=[0]*(k*z)
for i in range(len(d)):
    for j in range(z):
        ans[z*i+j]=d[i]+c[j]
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
  a, b = map(int, input().split())
  edges[a - 1].append(b - 1)
  edges[b - 1].append(a - 1)


vertice = [0 for _ in range(n)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(0, 1)

ans = []
if vertice.count(1) <= n // 3:
    not3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
elif vertice.count(-1) <= n // 3:
    not3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
                continue
        ans.append(str(not3.pop()))
else:
    num1 = [i for i in range(1, N+1) if i % 3 == 1]
    num2 = [i for i in range(1, N+1) if i % 3 == 2]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))

print(" ".join(ans))


### FIXED CODE ###

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
 
group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)
 
three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))