Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and Vertex b_i.

Takahashi loves the number 3. He is seeking a permutation p_1, p_2, \ldots , p_N of integers from 1 to N satisfying the following condition:

For every pair of vertices (i, j), if the distance between Vertex i and Vertex j is 3, the sum or product of p_i and p_j is a multiple of 3.

Here the distance between Vertex i and Vertex j is the number of edges contained in the shortest path from Vertex i to Vertex j.

Help Takahashi by finding a permutation that satisfies the condition.

Constraints

2\leq N\leq 2\times 10^5

1\leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

If no permutation satisfies the condition, print -1.

Otherwise, print a permutation satisfying the condition, with space in between.
If there are multiple solutions, you can print any of them.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

1 2 5 4 3 

The distance between two vertices is 3 for the two pairs (2, 4) and (2, 5).

p_2 + p_4 = 6

p_2\times p_5 = 6

Thus, this permutation satisfies the condition.



Sample input:
5
1 2
1 3
3 4
3 5


Sample output:
1 2 5 4 3

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
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(3)] for _ in range(3)]
for i,d in enumerate(depth):
    if d%3==0:
        mem[0][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[0][1].append(i)
        else:
            mem[0][2].append(i)
    else:
        if (d//3)%2:
            mem[0][2].append(i)
        else:
            mem[0][1].append(i)
    d += 1
    if d%3==0:
        mem[1][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[1][1].append(i)
        else:
            mem[1][2].append(i)
    else:
        if (d//3)%2:
            mem[1][2].append(i)
        else:
            mem[1][1].append(i)
    d += 1
    if d%3==0:
        mem[2][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[2][1].append(i)
        else:
            mem[2][2].append(i)
    else:
        if (d//3)%2:
            mem[2][2].append(i)
        else:
            mem[2][1].append(i)

for k in range(3):
    ans = [None] * N
    for i in range(1,N+1):
        if len(mem[k][i%3])==0:
            break
        j = mem[k][i%3].pop()
        ans[j] = i
    else:
        print(*ans)
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())

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

inf=float("inf")

prv=[inf]*n
prv[0]=-1
depth=[inf]*n
depth[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next in edge[cur]:
    if prv[next]==inf:
      prv[next]=cur
      depth[next]=depth[cur]+1
      stack.append(next)
Ans=[0]*n
Ans[0]=1
ct1,ct2,ct3=1,0,0
for i in range(1,n):
  if depth[i]%2==0:
    if 3*ct1+1<=n:
      Ans[i]=3*ct1+1
      ct1+=1
    else:
      Ans[i]=3*ct3+3
      ct3+=1
  else:
    if 3*ct2+2<=n:
      Ans[i]=3*ct2+2
      ct2+=1
    else:
      Ans[i]=3*ct3+3
      ct3+=1
if max(Ans)>n:
  print(-1)
else:
  print(*Ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
for _ in range(N-1):
    _ = input()
    pass
ans = ['3' for _ in range(N)]
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
for _ in range(N - 1):
    input()

for _ in range(N):
    print(3, end=" ")

Submission status: Wrong Answer

Solution code:
print('1 2 5 4 3')

Submission status: Wrong Answer

Solution code:
N = int(input())
e = [list(map(int, input().split()))]
print(" ".join([str(3)]*N))

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [tuple(map(int, input().split())) for _ in range(n-1)]

print('3' * n)

Submission status: Wrong Answer

Solution code:
N = int(input())
for _ in range(N - 1):
    input()

for _ in range(N - 1):
    print(3, end=" ")

Submission status: Wrong Answer

Solution code:
n = int(input())
for i in range(n-1):
    a, b = list(map(int, input().split()))
ans = [3]*n
print(*ans)

Submission status: Wrong Answer

Solution code:

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis

N = int(input())

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

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

    lis[a].append(b)
    lis[b].append(a)

ap = [0,1,2,0,2,1]
tb = [3,1,2]
dis,plis = NC_Dij(lis,0)

ans = []

import sys


for loop in range(6):

    tb = [3,1,2]
    nf = True
    ans = []
    
    for i in range(N):

        now = tb[ap[dis[i] % 6]]
        tb[ap[dis[i] % 6]] += 3
        if now > N:
            nf = False
        else:
            ans.append(now)
        
    if nf:
        print (" ".join(map(str,ans)))
        sys.exit()
    else:
        ap = [ap[-1]] + ap[:5]

print (-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = ['3'] * N
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

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

for i in range(N):
    print("3", end=" ")
print("")

Submission status: Wrong Answer

Solution code:
from sys import stdin

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

node_p = [0 for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

for i in range(N):
    print(3, end=" ")

print()

Submission status: Wrong Answer

Solution code:
# C
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

ans = "3"*N
for i in ans:
    print("{} ".format(i), end="")

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [[int(i) for i in input().split()] for _ in range(N - 1)]
print([3] * N)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = [3]*N
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]*(N-1)
b = [0]*(N-1)
for i in range(N-1):
    a[i],b[i] = map(int, input().split())

if N%3==0:
    for i in range(N//3 - 1):
        print(3*i+1, 3*i+3, 3*i+2,end=' ')
    print(N-2, N, N-1)
elif N%3 == 1:
    for i in range(N//3 ):
        print(3*i+1, 3*i+3, 3*i+2,end=' ')
    print(N)
else:
    for i in range(N//3 ):
        print(3*i+1, 3*i+3, 3*i+2,end=' ')
    print(N-1, N)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
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(3)]
for i,d in enumerate(depth):
    if d%3==0:
        mem[0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[1].append(i)
        else:
            mem[2].append(i)
    else:
        if (d//3)%2:
            mem[2].append(i)
        else:
            mem[1].append(i)

ans = [None] * N
for i in range(1,N+1):
    if len(mem[i%3])==0:
        print(-1)
        exit()
    j = mem[i%3].pop()
    ans[j] = i
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
for i in range(N-1):
    a, b = map(int, input().split())

ans_arr = []
for i in range(N):
    ans_arr.append(str((i+1)*3))
ans = ' '.join(ans_arr)
print(ans)

Submission status: Wrong Answer

Solution code:
#!python3.4
# -*- coding: utf-8 -*-
# hitachi2020/hitachi2020_c
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    print('3 ' * N)
    return
    tree = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x:x-1, i2nn())
        tree[a].add(b)
        tree[b].add(a)
    return

main()

Submission status: Wrong Answer

Solution code:
import sys
import bisect
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
ab = [IL() for i in range(N-1)]

ans = [3]*N
print(*ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    tree = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[b].append(a)
        tree[a].append(b)
    for _ in range(n):
        print("3", end=" ")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
ed = [tuple(map(int, input().split())) for _ in range(n-1)]
g = [list() for _ in range(n)]
for a,b in ed:
  g[a-1].append(b-1)
  g[b-1].append(a-1)
bi = [0]*n

def dfs(v, p):
  for x in g[v]:
    if x == p: continue
    bi[x] = 1 ^ bi[v]
    dfs(x, v)
  return

dfs(0,-1)

if sum(bi)*2 < n:
  bi = [1^x for x in bi]
  
one = sum(bi)
two = n - one
if max(0, one - (n//3) - (n%3 > 0)) + max(0, two - (n//3) - (n%3 > 1)) > n // 3:
  print(-1); exit(0)
on = 1
tw = 2
th = 3
ans = [0]*n
for i in range(n):
  if bi[i]:
    if on > n:
      ans[i] = th
      th += 3
    else:
      ans[i] = on
      on += 3
  else:
    if tw > n:
      ans[i] = th
      th += 3
    else:
      ans[i] = tw
      tw += 3
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = [list(map(int,input().split())) for _ in range(N-1)]
ans = [3]*N
print(*ans)

Submission status: Wrong Answer

Solution code:

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis

N = int(input())

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

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

    lis[a].append(b)
    lis[b].append(a)

ap = [0,1,2,0,2,1]
dis,plis = NC_Dij(lis,0)

ans = []

for i in range(N):

    ans.append(ap[dis[i] % 6])

print (" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
G=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
stack=[(0,0)]
ans=[0]*n
while len(stack)>0:
    node=stack.pop()
    if node[1]%2==0:
        ans[node[0]]=1
    else:
        ans[node[0]]=3
    for i in G[node[0]]:
        if ans[i]==0:
            stack.append((i,node[1]+1))
for i in ans:
    print(i,end='')
    print(' ',end='')

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [3] * n
print(*l)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, groupby
from math import sqrt, factorial, log
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop
import sys
stdin = sys.stdin
mod = 10**9 + 7

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

N = ni()
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = na()
print([3 for i in range(N)])

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[3]*n
print(l)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = [[] for _ in range(N + 1)]
dist = [-1 for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
zero = []
one = []
two = []
for i in range(1, N + 1):
    if i % 3 == 1:
        one.append(i)
    elif i % 3 == 2:
        two.append(i)
    else:
        zero.append(i)
q = [1]
dist[1] = 0

while q.__len__() != 0:
    s = q.pop(0)
    for i in G[s]:
        if dist[i] == -1:
            q.append(i)
            dist[i] = (dist[s] + 1) % 2

red = 0
blue = 0

for i in range(1, N + 1):
    if dist[i] == 0:
        red += 1
    else:
        blue += 1
ans = []
if red > N / 3 and blue > N / 3:
    for i in range(1, N + 1):
        if dist[i] == 0 and one.__len__() != 0:
            ans.append(one.pop())
        elif dist[i] == 1 and two.__len__() != 0:
            ans.append(two.pop())
        else:
            ans.append(zero.pop())
elif red <= N / 3:
    for i in range(1, N + 1):
        if dist[i] == 0:
            ans.append(zero.pop())
        else:
            if one.__len__() != 0:
                ans.append(one.pop())
            elif two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

else:
    for i in range(1, N + 1):
        if dist[i] == 1:
            ans.append(zero.pop())
        else:
            if one.__len__() != 0:
                ans.append(one.pop())
            elif two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
S = sys.stdin.readlines()
N = int(S[0])
A = list([] for i in range(N+1))

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


B = []
for q in range(N+1):  # q=2,  A[2]=[1]
        for k in A[q]:  # k = 1
            if k != q:
                for l in A[k]: # A[1]=[2,3] , l=3
                    if l != q and l != k:
                        for m in A[l]: # A[3]=[1,4,5], m= 4,5
                            if m != q and m !=k and m !=l :
                                B.append((q,m))

# print(list(set(B)))
import itertools
L = itertools.permutations(range(1,N+1),N)

C = list(set(B))

for M in L:
    # print(M)
    for o in C[0:len(C)//2+1]:
        # print("o : ",o)
        # print("M[o[0]-1] : ",M[o[0]-1], "  M[o[1]-1] : ", M[o[1]-1])
        if (M[o[0]-1]+M[o[1]-1]) % 3 !=0 and M[o[0]-1] %3 != 0 and M[o[1]-1] % 3 !=0:
            break
    else: 
        [print(i, end=" ") for i in M] 
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
S = sys.stdin.readlines()
N = int(S[0])
A = list([] for i in range(N+1))

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


B = []
for q in range(N+1):  # q=2,  A[2]=[1]
        for k in A[q]:  # k = 1
            if k != q:
                for l in A[k]: # A[1]=[2,3] , l=3
                    if l != q and l != k:
                        for m in A[l]: # A[3]=[1,4,5], m= 4,5
                            if m != q and m !=k and m !=l :
                                B.append((q,m))

# print(list(set(B)))
import itertools
L = itertools.permutations(range(1,N+1),N)

for M in L:
    # print(M)
    for o in list(set(B)):
        # print("o : ",o)
        # print("M[o[0]-1] : ",M[o[0]-1], "  M[o[1]-1] : ", M[o[1]-1])
        if (M[o[0]-1]+M[o[1]-1]) % 3 !=0 and M[o[0]-1] %3 != 0 and M[o[1]-1] % 3 !=0:
            break
    else: 
        [print(i, end=" ") for i in M] 
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list([] for i in range(N+1))

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


B = []
for q in range(N+1):  # q=2,  A[2]=[1]
        for k in A[q]:  # k = 1
            if k != q:
                for l in A[k]: # A[1]=[2,3] , l=3
                    if l != q and l != k:
                        for m in A[l]: # A[3]=[1,4,5], m= 4,5
                            if m != q and m !=k and m !=l :
                                B.append((q,m))

# print(list(set(B)))
import itertools
L = itertools.permutations(range(1,N+1),N)

for M in L:
    # print(M)
    for o in list(set(B)):
        # print("o : ",o)
        # print("M[o[0]-1] : ",M[o[0]-1], "  M[o[1]-1] : ", M[o[1]-1])
        if (M[o[0]-1]+M[o[1]-1]) % 3 !=0 and M[o[0]-1] %3 != 0 and M[o[1]-1] % 3 !=0:
            break
    else: 
        [print(i, end=" ") for i in M] 
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = [[] for _ in range(N + 1)]
dist = [-1 for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
zero = []
one = []
two = []
for i in range(1, N + 1):
    if i % 3 == 1:
        one.append(i)
    elif i % 3 == 2:
        two.append(i)
    else:
        zero.append(i)
q = [1]
dist[1] = 0

while q.__len__() != 0:
    s = q.pop(0)
    for i in G[s]:
        if dist[i] == -1:
            q.append(i)
            dist[i] = (dist[s] + 1) % 2

red = 0
blue = 0

for i in range(1, N + 1):
    if dist[i] == 0:
        red += 1
    else:
        blue += 1
ans = []
if red > N / 3 and blue > N / 3:
    for i in range(1, N + 1):
        if dist[i] == 0:
            if one.__len__() != 0:
                ans.append(one.pop())
            else:
                ans.append(zero.pop())
        else:
            if two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())
elif red <= N / 3:
    for i in range(1, N + 1):
        if dist[i] == 0:
            ans.append(zero.pop())
        else:
            if one.__len__() != 0:
                ans.append(one.pop())
            elif two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

else:
    for i in range(1, N + 1):
        if dist[i] == 1:
            ans.append(zero.pop())
        else:
            if one.__len__() != 0:
                ans.append(one.pop())
            elif two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
line = [[] for _ in range(N + 1)]
dist = [-1 for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    line[a].append(b)
    line[b].append(a)
zero = []
one = []
two = []
for i in range(1, N + 1):
    if i % 3 == 1:
        one.append(i)
    elif i % 3 == 2:
        two.append(i)
    else:
        zero.append(i)
sta = [1]
dist[1] = 0
while sta.__len__() != 0:
    s = sta.pop(0)
    for i in line[s]:
        if dist[i] == -1:
            sta.append(i)
            dist[i] = (dist[s] + 1) % 2
red = 0
blue = 0
for i in range(1, N + 1):
    if dist[i] == 0:
        red += 1
    else:
        blue += 1
ans = []
if red > N / 3 and blue > N / 3:
    for i in range(1, N + 1):
        if dist[i] == 0:
            if one.__len__() != 0:
                ans.append(one.pop())
            else:
                ans.append(zero.pop())
        else:
            if two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

if red <= N / 3:
    for i in range(1, N + 1):
        if dist[i] == 0:
            ans.append(zero.pop())
        else:
            if one.__len__() != 0:
                ans.append(one.pop())
            elif two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

if blue <= N / 3:
    for i in range(1, N + 1):
        if dist[i] == 1:
            ans.append(zero.pop())
        else:
            if one.__len__() != 0:
                ans.append(one.pop())
            elif two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

col = [-1]*N
col[0] = 0
stack = deque([0])
while stack :
    now = stack.pop()
    for i in G[now] :
        if col[i] == -1 :
            col[i] = (col[now] + 1)%2
            stack.append(i)

mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]

ans = [0 for _ in range(N)]
if sum(col) <= N//3 :
    mods = mod0 + mod1 + mod2
    for i in range(N) :
        if col[i] == 1 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()
elif sum(col) >= 2*N//3 :
    mods = mod0 + mod1 + mod2
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()
else :
    mods = mod1 + mod0 + mod2
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
G = [[0]*N for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1][b-1] = G[b-1][a-1] = 1

col = [-1]*N
col[0] = 0
stack = deque([0])
while stack :
    now = stack.pop()
    for i in range(N) :
        if G[now][i] == 1 :
            if col[i] == -1 :
                col[i] = (col[now] + 1)%2
                stack.append(i)

mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]

ans = [0 for _ in range(N)]
if sum(col) <= N//3 :
    mods = mod0 + mod1 + mod2
    for i in range(N) :
        if col[i] == 1 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()
elif sum(col) >= 2*N//3 :
    mods = mod0 + mod1 + mod2
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()
else :
    mods = mod1 + mod0 + mod2
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
G = [[0]*N for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1][b-1] = G[b-1][a-1] = 1

col = [-1]*N
col[0] = 0
stack = [0]
while stack :
    now = stack.pop()
    for i in range(N) :
        if G[now][i] == 1 :
            if col[i] == -1 :
                col[i] = (col[now] + 1)%2
                stack.append(i)

mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]

ans = [0 for _ in range(N)]
if sum(col) <= N//3 :
    mods = mod0 + mod1 + mod2
    for i in range(N) :
        if col[i] == 1 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()
elif sum(col) >= 2*N//3 :
    mods = mod0 + mod1 + mod2
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()
else :
    mods = mod1 + mod0 + mod2
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

node = [[] for _ in range(N)]

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

# 頂点1からの距離が奇数:1、偶数:0
group = [False] * N
# 親ノードを格納する
parents = list(range(N))
stack = [0]

# ノードの選択
while stack:
    p = stack.pop()
    # 子ノードの選択
    for c in node[p]:
        # 親ノードも選択されるので、その場合は飛ばす
        if c != parents[p]:
            # 子ノードの親を自分にする
            parents[c] = p
            # 子ノードのグループを自分と逆に設定する
            group[c] = not group[p]
            stack.append(c)
true_num = sum(map(int, group))
false_num = N - true_num
p = [0] * N
mod_0 = [int(i) for i in range(1,N+1) if i%3 == 0]
mod_1 = [int(i) for i in range(1,N+1) if i%3 == 1]
mod_2 = [int(i) for i in range(1,N+1) if i%3 == 2]

if true_num >= N/3 and false_num >= N/3:
    for i in range(N):
        if group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            if mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
elif false_num < N/3:
    for i in range(N):
        if group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            elif mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            p[i] = mod_0.pop(0)
elif true_num < N/3:
    for i in range(N):
        if not group[i]:
            if mod_1:
                p[i] = mod_1.pop(0)
            elif mod_2:
                p[i] = mod_2.pop(0)
            else:
                p[i] = mod_0.pop(0)
        else:
            p[i] = mod_0.pop(0)

print(" ".join(map(str, p)))

Submission status: Time Limit Exceeded

Solution 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 = [[0], []]
idx = 1
stack = [0]
while stack:
  tmp = stack
  stack = []
  while tmp:
    v = tmp.pop()
    for u in edge[v]:
      if u not in group[idx]:
        group[idx].append(u)
        stack.append(u)
  idx ^= 1

p = [0] * n
group.sort(key=len)
if len(group[0]) <= n // 3:
  three = 3
  while group[0]:
    v = group[0].pop()
    p[v] = three
    three += 3
  while three <= n:
    v = group[1].pop()
    p[v] = three
    three += 3
  i = 0
  while group[1]:
    v = group[1].pop()
    p[v] = 3 * i + 1
    if group[1]:
      v = group[1].pop()
      p[v] = 3 * i + 2
      i += 1
else:
  three = 3
  for two in range(2, n+1, 3):
    v = group[0].pop()
    p[v] = two
  while group[0]:
    v = group[0].pop()
    p[v] = three
    three += 3
  for one in range(1, n+1, 3):
    v = group[1].pop()
    p[v] = one
  while group[1]:
    v = group[1].pop()
    p[v] = three
    three += 3
print(' '.join(map(str, p)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

tree = [[] for _ in range(n)]
for _ in range(n-1):
   a, b = map(int,input().split())
   tree[a-1].extend([b-1])
   tree[b-1].extend([a-1])


def bfs(v):
   dist = [-1] * n
   dist[v] = 0
   visit = [v]
   c = 1
   while visit:
      next = []
      for i in visit:
         for j in tree[i]:
            if dist[j] == -1:
               dist[j] = c
               next.append(j)
      visit = next
      c += 1
      if c > 3:
         break

   return dist

import itertools
p = [i for i in range(1, n+1)]
ps = list(itertools.permutations(p))

d3 = []
for i in range(n):
   d = bfs(i)
   for j in range(i, n):
      if d[j] == 3:
         d3.append([i, j])

for pp in ps:
   ok = 1
   for i, j in d3:
      if (pp[i] + pp[j]) % 3 != 0 and (pp[i] * pp[j]) % 3 != 0:
         ok = 0
         break
   if ok == 1:
      print(*pp)
      exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
# 久々の幅優先探索……

import queue

def main():

    n = int(input())
    edges = [list(map(int, input().split())) for _ in range(n-1)]
    num_0_mod_3 = n // 3
    num_2_mod_3 = (n+1) // 3
    num_1_mod_3 = (n+2) // 3


    def add_edge(u, v ):
        G[u].append(v)
        G[v].append(u)

    G = [[] for _ in range(n)] #グラフの隣接リスト表現
    for edge in edges:
        add_edge(edge[0]-1, edge[1]-1)

    num_distance_even = 0
    num_distance_odd = 0

    q = queue.Queue()
    q.put(0)

    distance = [-1] * n
    distance[0] = 0
    num_distance_even += 1

    for v in G[0]:
        q.put(v)

    while(q.qsize() > 0):
        now = q.get()
        for v in G[now]:
            if distance[v] >= 0:
                pass
            else:
                q.put(v)
                distance[v] = distance[now] + 1
                if (distance[v] & 1):
                    num_distance_odd += 1
                else:
                    num_distance_even += 1

    # print(distance)
    # print(num_distance_even, num_distance_odd)

    ans = [-1] * n

    index_one = 1
    index_two = 2
    index_zero = 3

    if num_distance_even >= num_1_mod_3 + num_2_mod_3:
        # evenに120 oddに0

        for i in range(n):
            if (distance[i] & 1) == 1:
                ans[i] = index_zero
                index_zero += 3
            else:
                if (index_one <= n):
                    ans[i] = index_one
                    index_one += 3
                elif (index_two <= n):
                    ans[i] = index_two
                    index_two += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3


    elif num_distance_odd >= num_1_mod_3 + num_2_mod_3:
        # evenに0 oddに012
        for i in range(n):
            if (distance[i] & 1) == 0:
                ans[i] = index_zero
                index_zero += 3
            else:
                if (index_one <= n):
                    ans[i] = index_one
                    index_one += 3
                elif (index_two <= n):
                    ans[i] = index_two
                    index_two += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3

    else:
    #     num_distance_even <= num_distance_odd * 2 and num_distance_odd <= num_distance_even * 2:
        # evenを2、oddを1、適宜0
        for i in range(n):
            if (distance[i] & 1) == 1:
                if (index_one <= n):
                    ans[i] = index_one
                    index_one += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3
            else:
                if (index_two <= n):
                    ans[i] = index_two
                    index_two += 3
                else:
                    ans[i] = index_zero
                    index_zero += 3

    print(' '.join(list(map(str, ans))))


if __name__ == '__main__':
    main()