Harryxun/stf_run huggingface dataset:
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([0])
v=[0]*n
v[0]=1
gp=[[] for i in range(n)]
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==0:
            v[i]=1
            gp[p].append(i)
            q.append(i)
MOD=10**9+7
flag=[0]*n
dp=[[0,0] for i in range(n)]
def f(i):
    if flag[i]:
        return 0
    flag[i]=1
    dp[i][0]=1
    dp[i][1]=1
    for j in gp[i]:
        f(j)
        dp[i][0]=dp[i][0]*(dp[j][0]+dp[j][1])%MOD
        dp[i][1]=dp[i][1]*dp[j][0]
    return 0
f(0)
print((dp[0][0]+dp[0][1])%MOD)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**9)
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([0])
v=[0]*n
v[0]=1
gp=[[] for i in range(n)]
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==0:
            v[i]=1
            gp[p].append(i)
            q.append(i)
MOD=10**9+7
flag=[0]*n
dp=[[0,0] for i in range(n)]
def f(i):
    if flag[i]:
        return 0
    flag[i]=1
    dp[i][0]=1
    dp[i][1]=1
    for j in gp[i]:
        f(j)
        dp[i][0]=dp[i][0]*(dp[j][0]+dp[j][1])%MOD
        dp[i][1]=dp[i][1]*dp[j][0]
        dp[i][0]%=MOD
        dp[i][1]%=MOD
    return 0
f(0)
print((dp[0][0]+dp[0][1])%MOD)
a = int(input)
print(48-a)

### FIXED CODE ###

a = int(input())
print(48-a)
# 1つづつ順に
def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

    dp = [[0] * (W+1) for _ in range(N+1)] 

    for i in range(N):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            if j < w:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j - w] + v)
 
    print(dp[N][W])

# 遷移先を考えて移動。初期化は0
def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

    dp = [[0] * (W+1) for _ in range(N+1)] 

    for i in range(N):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            if j + w <= W:
                dp[i + 1][j + w] = max(dp[i][j] + v, dp[i + 1][j + w])
 
    print(dp[N][W])


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

# 1つづつ順に
# V << W なので、 dp[N][W]ではなく、 dp[N][V]で作成
def resolve():
    N, W = map(int, input().split())
    w_l = []
    v_l = []
    for _ in range(N):
        w, v = map(int, input().split())
        w_l.append(w)
        v_l.append(v)

    max_v = sum(v_l) + 1
    dp = [[10**10] * (max_v) for _ in range(N+1)] 
    dp[0][0] = 0

    for i in range(N):
        for j in range(max_v):
            #print(i, j)
            w = w_l[i]
            v = v_l[i]
            if j < v:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i][j - v] + w)
 
    res = 0
    for j in range(max_v):
        if dp[N][j] <= W:
            res = j

    print(res)

if __name__ == "__main__":
    resolve()
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]

board = [[0] * W for i in range(H)]

if S[0][0] == '#':
    board[0][0] = 1

if W > 1:
    for i in range(1, W):
        if S[0][i - 1] == '.' and S[0][i] == '#':
            board[0][i] = board[0][i - 1] + 1
        else:
            board[0][i] = board[0][i - 1]
if H > 1:
    for i in range(1, H):
        if S[i - 1][0] == '.' and S[i][0] == '#':
            board[i][0] = board[i - 1][0] + 1
        else:
            board[i][0] = board[i - 1][0]

if H > 1 and W > 1:
    for i in range(1, W):
        for j in range(1, H):
            if S[i][j] == '.':
                board[i][j] = min(board[i - 1][j], board[i][j - 1])
            else:
                if S[i - 1][j] == '.':
                    left = 1
                else:
                    left = 0
                if S[i][j - 1] == '.':
                    up = 1
                else:
                    up = 0
                board[i][j] = min(board[i - 1][j] + left, board[i][j - 1] + up)

print(board[H - 1][W - 1])


### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for i in range(H)]

board = [[0] * W for i in range(H)]

if S[0][0] == '#':
    board[0][0] = 1

for i in range(1, W):
    if S[0][i - 1] == '.' and S[0][i] == '#':
        board[0][i] = board[0][i - 1] + 1
    else:
        board[0][i] = board[0][i - 1]

for i in range(1, H):
    if S[i - 1][0] == '.' and S[i][0] == '#':
        board[i][0] = board[i - 1][0] + 1
    else:
        board[i][0] = board[i - 1][0]

for i in range(1, H):
    for j in range(1, W):
        if S[i][j] == '.':
            board[i][j] = min(board[i - 1][j], board[i][j - 1])
        else:
            if S[i - 1][j] == '.':
                up = 1
            else:
                up = 0
            if S[i][j - 1] == '.':
                left = 1
            else:
                left = 0
            board[i][j] = min(board[i - 1][j] + up, board[i][j - 1] + left)

print(board[H - 1][W - 1])
import string

S = input()
alphabetsStr = string.ascii_lowercase
alphabets = list(map(lambda x: x, string.ascii_lowercase))
lastWord = ''.join(alphabets[::-1])

if len(S) == 26:
    if S == lastWord: print(-1)
    else:
        for i  in S:
            if alphabets[i] != S[i]:
                print(S[:i] + alphabets[i])
                break
# else:
#     for s in alphabets:
#         if s not in S:
#             print(S + s)
#             break

print(-1)

### FIXED CODE ###

import string

S = input()
reversedS = ''.join(list(S)[::-1])
alphabets = list(string.ascii_lowercase)
lastWord = ''.join(alphabets[::-1])
cnt = [S.count(chr(ord('a')+i)) for i in range(26)]
if len(S) == 26:
    if S == lastWord: print(-1)
    else:
        found = False
        for i in range(len(reversedS)):
            s = reversedS[i]
            largeS = alphabets[ord(s)-ord('a')+1:]
            tailS = list(S)[26-i-1:]
            for lS in largeS:
                if lS in tailS:
                    print(S[:26-i-1]+lS)
                    found = True
                    break
            if found: break
else:
    for j in range(26):
        if cnt[j] == 0:
            S += chr(ord('a')+j)
            print(S)
            break
from collections import deque

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)

# make a function
def add(lst, p, x):
    if child[p] == []:
        lst[p] += x
    else:
        lst[p] += x
        for v in child[p]:
            add(lst, v, x)

## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    add(count, p, x)
    print(count)

print(' '.join(map(str, count)))

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)


## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    count[p] += x
    
deq = deque([0])
while deq:
    v = deq.popleft()
    for w in child[v]:
        count[w] += count[v]
        deq.append(w)



print(' '.join(map(str, count)))
res: str = 'bust' if sum([int(x) for x in input().split(' ')]) >= 22 else 'win')
  
print(res)

### FIXED CODE ###

print('bust' if sum([int(x) for x in input().split(' ')]) >= 22 else 'win')
n,x,m=map(int,input().split())

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
#        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
#        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=x*n
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)       
        


### FIXED CODE ###


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

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=(ai0*ai0)%m
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
    if icntk==0:
#        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=asum0+x*(n-icnt0)
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)
L , N = map(int, input().split())
S = [input() for i in range(N)]
S = sorted(S)
print("".join(S))

### FIXED CODE ###

N , L = map(int, input().split())
S = [input() for i in range(N)]
S = sorted(S)
print(*S,sep='')
print(180*(int(input()-2))

### FIXED CODE ###

print(180*(int(input())-2))
import math
mod = 10**9+7

def stairs(n):
    a = 1/math.sqrt(5)
    b = (1+math.sqrt(5))/2
    c = (1-math.sqrt(5))/2
    return int(a*(b**(n+1)-c**(n+1)))%mod

def main():
    n,m = map(int,input().split(' '))
    a=[-1]
    a_list=[]
    ans = 1
    for i in range(m):
        a.append(int(input()))
    a.append(n+1)
    for i in range(m+1):
        a_list.append(a[i+1]-a[i]-2)
    for i in a_list:
        if i <0:
            ans = 0
            break
        ans *= stairs(i)
        ans %= mod
    print(ans)

main()

### FIXED CODE ###

import sys
mod = 10**9+7
def main():
    n,m=map(int,input().split(' '))
    if m > 0:
        aaa = set(map(int,sys.stdin))
    else:
        aaa = set()

    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in aaa else 0
    for i in range(2,n+1):
        if i in aaa:
            continue
        dp[i] = dp[i-1]+dp[i-2]

    print(dp[n]%mod)

main()
import copy

combinations = []
def make_combination(n):
    S = [0 for i in range(n)]
    rec(0, n, S)

def rec(i, n, S):
    global combinations
    if i == n:
        combinations.append(copy.copy(S))
        return None
    rec(i+1, n, S)
    S[i] = 1
    rec(i+1, n, S)
    S[i] = 0

n = int(input())
A = [int(x) for x in input().split(' ')]
q = int(input())
M = [int(x) for x in input().split(' ')]

make_combination(n)
for m in M:
    flag = False
    for co in combinations:
        sum = 0
        for i in range(n):
            sum += A[i] * co[i]
            if sum >= m:
                break
        if sum == m:
            flag = True
            break

    if flag:
        print('yes')
    else:
        print('no')


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split(' ')))
q = int(input())
M = list(map(int, input().split(' ')))

# 上限と下限でフィルター
max_A = 0
min_A = float('inf')
for num in A:
    max_A += num
    if num < min_A:
        min_A = num

def rec(i, m):
    if m < 0:
        return False
    elif m == 0:
        return True
    if i >= n:
        return False

    rst = rec(i+1, m - A[i]) or rec(i+1, m)
    return rst

for m in M:
    if m < min_A or max_A < m:
        print('no')
    elif rec(0, m):
        print('yes')
    else:
        print('no')
from math import gcd
from collections import defaultdict

def sign(a):
    if a == 0:
        return 0
    else:
        return a//abs(a)

n = int(input())
a, b = [], []
for i in range(n):
    data = list(map(int, input().split()))
    a.append(data[0])
    b.append(data[1])

d = defaultdict(lambda: [0, 0])
zeros = 0

for i in range(n):
    g = gcd(a[i], b[i])
    a[i] //= g
    b[i] //= g
    if a[i]*b[i] > 0:
        d[(abs(a[i]), abs(b[i]))][0] += 1
    elif a[i]*b[i] < 0:
        d[(abs(b[i]), abs(a[i]))][1] += 1
    elif a[i] == 0 and b[i] != 0:
        d[(0, 1)][0] += 1
    elif b[i] == 0 and a[i] != 0:
        d[(0, 1)][1] += 1
    elif a[i] == b[i] == 0:
        zeros += 1

mod = 1000000007
cnt = 1
for pair in d.values():
    cnt *= pow(2, pair[0], mod) + pow(2, pair[1], mod) - 1
    cnt %= mod
cnt += zeros - 1
print(cnt)

### FIXED CODE ###

from math import gcd
from collections import defaultdict

n = int(input())
a, b = [], []
for i in range(n):
    data = list(map(int, input().split()))
    a.append(data[0])
    b.append(data[1])

d = defaultdict(lambda: [0, 0])
zeros = 0

for i in range(n):
    if a[i] * b[i] != 0:
        g = gcd(a[i], b[i])
        a[i] //= g
        b[i] //= g
    if a[i]*b[i] > 0:
        d[(abs(a[i]), abs(b[i]))][0] += 1
    elif a[i]*b[i] < 0:
        d[(abs(b[i]), abs(a[i]))][1] += 1
    elif a[i] == 0 and b[i] != 0:
        d[(0, 1)][0] += 1
    elif b[i] == 0 and a[i] != 0:
        d[(0, 1)][1] += 1
    elif a[i] == b[i] == 0:
        zeros += 1

mod = 1000000007
cnt = 1
for pair in d.values():
    cnt *= pow(2, pair[0], mod) + pow(2, pair[1], mod) - 1
    cnt %= mod
cnt += zeros - 1
cnt %= mod
print(cnt)
n=int(input())
c=list([]*n)
for i in range(n):
  a,b=map(int,input().split())
  c[i].append(a)
  c[i].append(b)

import cmath
sum=0  
for j in range(n):
  q=c[j][0];w=c[j][1]
  for k in range(j):
    sum+=cmath.sqrt((c[k][0]-q)**2+(c[k][1]-w)**2)
    
print(float(sum*2/n))    

### FIXED CODE ###

n=int(input())
c=[[] for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  c[i].append(a)
  c[i].append(b)

import math
sum=0  
for j in range(n):
  q=c[j][0];w=c[j][1]
  for k in range(j):
    sum+=math.sqrt((c[k][0]-q)**2+(c[k][1]-w)**2)
    
print(float(sum*2/n))
a = int(input())
b = int(input())
c = int(input())

if a == b == c:
    print(1)
elif a == b or b == c or a == c:
    print(2)
else:
    print(3)


### FIXED CODE ###

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

if a == b and a == c:
    print(1)
elif a == b or a == c or b == c:
    print(2)
else:
    print(3)
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=set(a)
l=len(b)
if l==1:
  if a[0]==0:print("Yes")
  else:print("No")
  exit()
elif l==2 and 0 in b and n%3==0:
  if a[n//2-1]!=a[n//2]:print("Yes")
  else:print("No")
elif l!=3:print("No");exit()
if n%3!=0:print("No");exit()
def ecount(X):
  c,ans=1,[]
  for i in range(len(X)-1):
    if X[i]==X[i+1]:c+=1
    else:
      ans.append(c);c=1
  ans.append(c)
  return ans
d=sorted(ecount(a))
if b.pop()^b.pop()==b.pop() and d[0]==d[2]:print("Yes")
else:print("No")

### FIXED CODE ###

n,a=int(input()),sorted(list(map(int,input().split())));b=set(a);l=len(b)
if l!=3:print("Yes"if(l==1and a[0]==0)or(l==2and a[0]==0and n%3==0and a[n//3-1]!=a[n//3])else"No")
else:print("Yes"if b.pop()^b.pop()==b.pop()and n%3==0and a[n//3-1]!=a[n//3]and a[n//3*2-1]!=a[n//3*2]else"No")
S = int(input())
h = S // 3600
ms = S % 3600
m = ms // 60
s = ms % 60
print(h + ":" + m + ":" + s)
 

### FIXED CODE ###

S = int(input())
s = str(S % 60)
HM = S // 60
m = str(HM % 60)
h = str(HM // 60)
print(h + ":" + m + ":" + s)
n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort()
f.sort(reverse = True)

def is_ok(t):
  cost = 0
  for aa,ff in zip(a,f):
    temp = t // ff
    if temp >= aa:
      contninue
    cost += aa - temp
  if cost <= k:
    return True
  return False
left = 0
right = a[-1]*f[0]
while left < right:
  mid = (left + right) // 2
  if is_ok(mid):
    right = mid
  else:
    left = mid + 1
print(left)

### FIXED CODE ###

import numpy as np
i8 = np.int64
i4 = np.int32


def solve(A, F, K):
    min_ = 0
    max_ = 10 ** 12
    while min_ < max_:
        mid = (min_ + max_) // 2
        count = A - mid // F
        sum_ = count[count > 0].sum()
        if sum_ <= K:
            max_ = mid
        else:
            min_ = mid + 1
    return min_

def main():
    stdin = open('/dev/stdin', 'rb')
    pin = np.fromstring(stdin.read(), i8, sep=' ')
    N, K = pin[:2]
    A = pin[2: N + 2]
    F = pin[N + 2: 2 * N + 2]
    A = np.sort(A)[::-1]
    F.sort()
    ans = solve(A, F, K)
    print(ans)

if __name__ == '__main__':
    main()
str=input()
flag=True
if str[0]!='A':
    flag=False
    str[0]='a'
cnt=0
for i in range(2,len(str)-2):
    if str[i]=='C':
        cnt+=1
        if cnt==1:
            str[i]='c'
if cnt!=1:
    flag=False

if str.islower():
    flag=False

if flag==True:
    print("AC")
else:
    print("WA")

### FIXED CODE ###

str=list(input())
flag=True
if str[0]!='A':
    flag=False
str[0]='a'
cnt=0
for i in range(2,len(str)-1):
    if str[i]=='C':
        cnt+=1
        if cnt==1:
            str[i]='c'
if cnt!=1:
    flag=False

tmp="".join(str)
if not tmp.islower():
    flag=False

if flag==True:
    print("AC")
else:
    print("WA")
A, B, T = map(int, raw_input().split())
print(int( (T+0.5)/A)*B)

### FIXED CODE ###

A, B, T = map(int, input().split())
print(int( (T+0.5)/A)*B)
a,b,c,d = map(int, input().split())
l=a+b
r=c+d
printT("Left" if l>r else "Balanced" if l==r else "Right")

### FIXED CODE ###

a,b,c,d = map(int, input().split())
l=a+b
r=c+d
print("Left" if l>r else "Balanced" if l==r else "Right")
abc = list(map(int, input().split()))
print(len(set(abc))

### FIXED CODE ###

a = list(map(int, input().split()))
print(len(set(a)))
n = int(input())
S = [int(s) for s in input().split()]
q = int(input())
T = [int(t) for t in input().split()]

def binary_search(A, key):
left = 0
right = n
while left < right:
    mid = int((left + right)/2)
    if A[mid] == key:
        return True
    elif key < A[mid]:
        right = mid
    else:
        left = mid + 1 return False
t = 0
for i in T:
    if binary_search(S, i):
        t += 1
print(t)

### FIXED CODE ###

n = int(input())
S = [int(s) for s in input().split()]
q = int(input())
T = [int(t) for t in input().split()]

def binary_search(A, key, n):
    left = 0
    right = n
    while left < right:
        mid = (left + right)//2
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False

count = 0
for i in T:
    if binary_search(S, i, n):
        count += 1
print(count)
import sys
from collections import deque
readline = sys.stdin.buffer.readline
n = int(readline())

g = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    g[a].append(b)
    g[b].append(a)
 
color = [0] * (n+1) #color[i]:点iの色(1 or -1)。但し塗られていないときは0とする

def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(g[v])):
        if color[ g[v][i] ] == c:
            return False
        elif color[ g[v][i] ] == 0 and not f(g[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True
ans = [0]*(n+1)
t0 = deque([i*3 for i in range(1,n//2)])
t1 = deque([1+i*3 for i in range(0,n//2)])
t2 = deque([2+i*3 for i in range(0,n//2)])
for i in range(n):
    if color[i] == 0:
        res = f(i,1)
black = 0
for i in color[1:]:
    if i == 1:
        black += 1

if black <= n//3:
    for i in range(1,n+1):
        if color[i] == 1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
else:
    for i in range(1,n+1):
        if color[i] == 1:
            if t1:
                ans[i] = t1.pop()
            else:
                ans[i] = t0.pop()
        else:
            if t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
print(*ans[1:])

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(1000000)
readline = sys.stdin.buffer.readline
n = int(readline())

g = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    g[a].append(b)
    g[b].append(a)

colors = [0] * (n+1)
 
colors[1] = 1
 
todo = []
for to in g[1]:
    todo.append([to, -1])
 
while todo:
    node, color = todo.pop()
 
    if colors[node] != 0:
        continue
 
    colors[node] = color
    new_color = -color
    for to in g[node]:
        if colors[to] != 0:
            continue
        todo.append([to, new_color])
ans = [0]*(n+1)
t0 = deque([])
t1 = deque([])
t2 = deque([])
for i in range(1,n+1):
    if i%3==1:
        t1.append(i)
    elif i%3==2:
        t2.append(i)
    else:
        t0.append(i)
black = 0
for i in colors[1:]:
    if i == 1:
        black += 1

if black <= n//3:
    for i in range(1,n+1):
        if colors[i] == 1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
elif black >= n-n//3:
    for i in range(1,n+1):
        if colors[i] == -1:
            ans[i] = t0.pop()
        else:
            if t1:
                ans[i] = t1.pop()
            elif t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
else:
    for i in range(1,n+1):
        if colors[i] == 1:
            if t1:
                ans[i] = t1.pop()
            else:
                ans[i] = t0.pop()
        else:
            if t2:
                ans[i] = t2.pop()
            else:
                ans[i] = t0.pop()
print(*ans[1:])
n = list(map(int,input(),split()))
n.sort()
n.reverse()
print(n[0]*10+n[1]+n[2])

### FIXED CODE ###

n = list(map(int,input().split()))
n.sort()
n.reverse()
print(n[0]*10+n[1]+n[2])
import math
n,k = map(int,input().split())
ans = 0
mod = 10**9+7
def combinations_count(n, r): #組み合わせ(nCr)
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(1,k+1):
    cnt = combinations_count(n-k+1,i)* combinations_count(k-1, i-1)
    print(cnt%mod)

### FIXED CODE ###

from operator import mul
from functools import reduce
n,k = map(int,input().split())
ans = 0
mod = 10**9+7
def cmb(n, r):
    if r > n:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under
for i in range(1,k+1):
    cnt = cmb(n-k+1,i)* cmb(k-1, i-1)
    print(cnt%mod)