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: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

def dfs(s):
    stack = [s]
    used = set(s)
    dist = [0]*N
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf not in used:
                used.add(vf)
                dist[vf] = 1 + dist[vn]
                stack.append(vf)

N = int(readline())

zero = N//3
one = N//3 + int(N%3 >= 1)
two = N - zero - one



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



root = 0
col = [0]*N

stack = [root]
used = set(stack)
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf not in used:
            used.add(vf)
            col[vf] = 1 - col[vn]
            stack.append(vf)

if 2*sum(col) < N:
    col = [1-c for c in col]
black = sum(col)
white = N - black

Ans = [None]*N
remain = set(range(1, N+1))
if N <= 3:
    Ans = list(range(1, N+1))

elif white <= zero:
    zb = [i for i in range(1, N+1) if i%3 == 0]
    rb = [i for i in range(1, N+1) if i%3 != 0]
    for i in range(N):
        if col[i] == 0:
            Ans[i] = zb.pop()
    rb += zb
    for i in range(N):
        if col[i] == 1:
            Ans[i] = rb.pop()

elif one <= black and two <= white:
    zb = [i for i in range(1, N+1) if i%3 == 0]
    ob = [i for i in range(1, N+1) if i%3 == 1]
    tb = [i for i in range(1, N+1) if i%3 == 2]
    for i in range(N):
        if col[i] == 1:
            if ob:
                Ans[i] = ob.pop()
            else:
                Ans[i] = zb.pop()
        else:
            if tb:
                Ans[i] = tb.pop()
            else:
                Ans[i] = zb.pop()
else:
    assert False,''
print(*Ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
n = int(input())

edge = [[] for i in range(n)]
ans = [-1] * n
odd = []
even =[]
nums = [[],[],[]]
for i in range(1,n+1):
    nums[i % 3].append(i)

def dfs(x, last = -1, d = 0):
    if d % 2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:continue
        dfs(nxt, x, d + 1)

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

dfs(0)

zerocnt = len(nums[0])

if len(even) <= zerocnt:
    for even_node in even:
        ans[even_node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for odd_node in odd:
        ans[odd_node] = rest.pop()

elif len(odd) <= zerocnt:
    for odd_node in odd:
        ans[odd_node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for even_node in even:
        ans[even_node] = rest.pop()

# len
# nums[1] >= nums[2] >= nums[0] >= nums[1]-1
else:
    for num in nums[1]:
        ans[even.pop()] = num
    for num in nums[2]:
        ans[odd.pop()] = num
    rest = nums[0]
    for even_node in even:
        ans[even_node] = rest.pop()
    for odd_node in odd:
        ans[odd_node] = rest.pop()

print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
stack = [(1,1)]
color = [0]*(n+1)
while stack:
  x,c = stack.pop()
  color[x] = c
  for y in graph[x]:
    if color[y] == 0:
      stack.append((y,3-c))
ans = [0]*(n+1)
cnt1 = 1
cnt2 = 2
cnt3 = 3
if color.count(1) >= (n*2+2)//3:
  for i in range(1,n+1):
    if color[i] == 1:
      if cnt1 <= n:
        ans[i] = cnt1
        if cnt1%3 == 1:
          cnt1 += 1
        else:
          cnt1 += 2
      else:
        ans[i] = cnt3
        cnt3 += 3
    else:
      ans[i] = cnt3
      cnt3 += 3
elif color.count(2) >= (n*2+2)//3:
  for i in range(1,n+1):
    if color[i] == 2:
      if cnt1 <= n:
        ans[i] = cnt1
        if cnt1%3 == 1:
          cnt1 += 1
        else:
          cnt1 += 2
      else:
        ans[i] = cnt3
        cnt3 += 3
    else:
      ans[i] = cnt3
      cnt3 += 3
else:
  c1 = []
  c2 = []
  for i in range(1,n+1):
    if color[i] == 1:
      c1.append(i)
    else:
      c2.append(i)
  for x in c1:
    if cnt1 <= n:
      ans[x] = cnt1
      cnt1 += 3
    else:
      ans[x] = cnt3
      cnt3 += 3
  for x in c2:
    if cnt2 <= n:
      ans[x] = cnt2
      cnt2 += 3
    else:
      ans[x] = cnt3
      cnt3 += 3
ans = ans[1:]
print(*ans)

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    if len(S)%2==1:
        print("No")
        return
    for i in range(len(S)//2):
        if S[i*2:i*2+2]!="hi":
            print("No")
            return
    print("Yes")
    return

def examB():
    a, b, M = LI()
    A = LI()
    B = LI()
    D = [LI()for _ in range(M)]
    ans = min(A) + min(B)
    for x,y,c in D:
        cur = A[x-1]+B[y-1]-c
        ans = min(ans,cur)
    print(ans)
    return

def examC():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    L = bfs(N,0,V)
    #print(L)
    odd = 0
    for l in L:
        if l==-1:
            print(-1)
            return
        if l%2==1:
            odd += 1
    G = []
    if odd*2<N:
        for i in range(N):
            if L[i]%2==1:
                G.append(i)
    else:
        for i in range(N):
            if L[i]%2==0:
                G.append(i)

    used = [False]*(N+1)
    ans = [0]*N
    if N//3>=len(G):
        cur = 3
        for g in G:
            ans[g] = cur
            used[cur] = True
            cur += 3
        cur = 1
        for i in range(N):
            if ans[i]!=0:
                continue
            while(used[cur]):
                cur += 1
            ans[i] = cur
            used[cur] = True
    else:
        cur = 1
        for g in G:
            ans[g] = cur
            used[cur] = True
            cur += 3
            if cur>N:
                cur = 3
        cur = 1
        for i in range(N):
            if ans[i]!=0:
                continue
            while(used[cur]):
                cur += 1
            ans[i] = cur
            used[cur] = True
    print(" ".join(map(str,ans)))
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Accepted

Solution code:
from collections import defaultdict,deque,Counter
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a-= 1 ; b-=1
    lines[a].add(b)
    lines[b].add(a)


depths = [set() for _ in range(N)]
Ev = 0
Od = 0

def dfs(s,b,d):
    global depths
    global Ev
    global Od
    depths[d].add(s)

    if d%2 == 0:
        Ev += 1
    else:
        Od += 1

    for t in lines[s]:
        if t == b:
            continue
        else:
            dfs(t,s,d+1)


dfs(0,-1,0)

# print(depths)

n1 = (N+2)//3
n2 = (N+1)//3
n0 = (N+0)//3

# print(n0,n1,n2)
ansl = [-1]*N


if Ev <= n0 or Od <= n0:
    if Ev <= n0: fl = 0
    else: fl = 1

    for d, ps in enumerate(depths):
        if d%2 == fl:
            for p in ps:
                ansl[p] = n0*3
                n0 -= 1
        else:
            for p in ps:
                if n1 > 0:
                    ansl[p] = n1*3 - 2
                    n1 -= 1
                elif n2 > 0:
                    ansl[p] = n2*3 - 1
                    n2 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1
else:
    for d, ps in enumerate(depths):
        if d%2 == 0:
            for p in ps:
                if n1 > 0:
                    ansl[p] = n1*3 - 2
                    n1 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1
        else:
            for p in ps:
                if n2 > 0:
                    ansl[p] = n2*3 - 1
                    n2 -= 1
                else:
                    ansl[p] = n0*3
                    n0 -= 1

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (N+1)
stack = [1]
dist[1] = 0
while stack:
    v = stack.pop()
    for w in graph[v]:
        if dist[w] == -1:
            dist[w] = dist[v] + 1
            stack.append(w)

ev = [i for i,x in enumerate(dist) if x % 2 == 0 and i > 0]
od = [i for i,x in enumerate(dist) if x % 2 == 1 and i > 0]

def make_perm(N, ev, od, x0, x1, x2, y0, y1, y2):
    assert len(ev) == x0 + x1 + x2
    assert len(od) == y0 + y1 + y2
    P = [0] * (N+1)
    for i in ev:
        if x0:
            P[i] = (x0 + y0) * 3
            x0 -= 1
            continue
        if x1:
            P[i] = (x1 + y1) * 3 - 2
            x1 -= 1
            continue
        if x2:
            P[i] = (x2 + y2) * 3 - 1
            x2 -= 1
            continue
    for i in od:
        if y0:
            P[i] = (x0 + y0) * 3
            y0 -= 1
            continue
        if y1:
            P[i] = (x1 + y1) * 3 - 2
            y1 -= 1
            continue
        if y2:
            P[i] = (x2 + y2) * 3 - 1
            y2 -= 1
            continue
    return P[1:]

def solve(N, ev, od):
    x0 = N // 3
    x1 = (N+2) // 3
    x2 = (N+1) // 3
    perm = [0] * (N+1)
    LE = len(ev)
    LO = len(od)
    if LE <= x0:
        return make_perm(N, ev, od, LE, 0, 0, x0-LE, x1, x2)
    if LO <= x0:
        return make_perm(N, ev, od, x0-LO, x1, x2, LO, 0, 0)
    if LE == x1:
        return make_perm(N, ev, od, 0, x1, 0, x0, 0, x2)
    if LO == x1:
        return make_perm(N, ev, od, x0, 0, x2, 0, x1, 0)
    # どちらも x1 よりたくさんある
    return make_perm(N, ev, od, LE-x1, x1, 0, LO-x2, 0, x2)

P = solve(N, ev, od)
print(' '.join(map(str, P)))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
DE = [0] * N
e = 1
o = 0
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            DE[a] = DE[i] ^ 1
            if DE[a]:
                o += 1
            else:
                e += 1
            X[a].remove(i)
            deque.append(Q, a)

A = [i for i in range(1, N+1) if i % 3 == 1]
B = [i for i in range(1, N+1) if i % 3 == 2]
C = [i for i in range(1, N+1) if i % 3 == 0]

ANS = [-1] * N
if e <= len(C):
    for i in range(N):
        if DE[i] == 0:
            ANS[i] = C.pop()
    for i in range(N):
        if ANS[i] < 0:
            ANS[i] = A.pop() if len(A) else B.pop() if len(B) else C.pop()
elif o <= len(C):
    for i in range(N):
        if DE[i] == 1:
            ANS[i] = C.pop()
    for i in range(N):
        if ANS[i] < 0:
            ANS[i] = A.pop() if len(A) else B.pop() if len(B) else C.pop()
else:
    for i in range(N):
        if DE[i] == 0:
            ANS[i] = A.pop()
            if len(A) == 0: break
    for i in range(N):
        if DE[i] == 1:
            ANS[i] = B.pop()
            if len(B) == 0: break
    for i in range(N):
        if ANS[i] < 0:
            ANS[i] = A.pop() if len(A) else B.pop() if len(B) else C.pop()
    
print(*ANS)

Submission status: Runtime Error

Solution code:
n=int(input())
ki=[[] for _ in range(n)]

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

odd=[-1]*n
odd[0]=0
todo=[0]
while todo:
    v=todo.pop()
    for nv in ki[v]:
        if odd[nv]==-1:
            odd[nv]=abs(odd[v]-1)
            todo.append(nv)
from collections import Counter
co=Counter(odd)
ans=[0]*n
if co[1]<n//3:
    cnt1=1
    cnt=2
    cnt3=1
    for i in range(n):
        if odd[i]==1 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1

elif co[0]<n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==0 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1
else:
    cnt1=1
    cnt2=1
    cnt3=1
    for i in range(n):
        if odd[i]==0:
            if 3*cnt1-2<=n:
                ans[i]=3*cnt1-2
                cnt1+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
        else:
            if 3*cnt2-1<=n:
                ans[i]=3*cnt2-1
                cnt2+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
print(*ans,sep=' ')

Submission status: Runtime Error

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    G[a].add(b)
    G[b].add(a)
color = [None] * (N + 1)


def dfs(G, v, cur):
    color[v] = cur
    for w in G[v]:
        if color[w] is None:
            dfs(G, w, 1 - cur)


dfs(G, 1, 0)
c=collections.Counter(color[1:])

Submission status: Runtime Error

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    G[a].add(b)
    G[b].add(a)
color = [None] * (N + 1)


def dfs(G, v, cur):
    color[v] = cur
    for w in G[v]:
        if color[w] is None:
            dfs(G, w, 1 - cur)


dfs(G, 1, 0)
c=collections.Counter(color[1:])
cand1 = set(range(1, N + 1, 3))
cand2 = set(range(2, N + 1, 3))
cand3 = set(range(3, N + 1, 3))

i0, i1 = 0, 1
if c[0] > c[1]:
    i0, i1 = 1, 0

ans = [None] * (N + 1)
if c[i0] <= len(cand3):
    for i in range(1, N + 1):
        if color[i]==i0:
            ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand2:
                ans[i] = cand2.pop()
            elif cand3:
                ans[i] = cand3.pop()
else:
    for i in range(1, N + 1):
        if color[i] == i0:
            if cand2:
                ans[i] = cand2.pop()
            elif cand3:
                ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand3:
                ans[i] = cand3.pop()
print(*ans[1:])

Submission status: Runtime Error

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    G[a].add(b)
    G[b].add(a)
color = [None] * (N + 1)


def dfs(G, v, cur):
    color[v] = cur
    for w in G[v]:
        if color[w] is None:
            dfs(G, w, 1 - cur)


dfs(G, 1, 0)
c=collections.Counter(color[1:])
cand1 = set(range(1, N + 1, 3))
cand2 = set(range(2, N + 1, 3))
cand3 = set(range(3, N + 1, 3))

i0, i1 = 0, 1
if c[0] > c[1]:
    i0, i1 = 1, 0

ans = [None] * (N + 1)
if c[i0] <= len(cand3):
    for i in range(1, N + 1):
        if color[i]==i0:
            ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand2:
                ans[i] = cand2.pop()
            else:
                ans[i] = cand3.pop()
else:
    for i in range(1, N + 1):
        if color[i] == i0:
            if cand2:
                ans[i] = cand2.pop()
            else:
                ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            else:
                ans[i] = cand3.pop()
print(*ans[1:])

Submission status: Runtime Error

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    G[a].add(b)
    G[b].add(a)
color = [None] * (N + 1)


def dfs(G, v, cur):
    color[v] = cur
    for w in G[v]:
        if color[w] is None:
            dfs(G, w, 1 - cur)


dfs(G, 1, 0)
c=collections.Counter(color[1:])
cand1 = set(range(1, N + 1, 3))
cand2 = set(range(2, N + 1, 3))
cand3 = set(range(3, N + 1, 3))

i0, i1 = 0, 1
if c[0] > c[1]:
    i0, i1 = 1, 0

ans = [None] * (N + 1)
if c[i0] <= len(cand3):
    for i in range(1, N + 1):
        if color[i]==i0:
            ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand2:
                ans[i] = cand2.pop()
            else:
                ans[i] = cand3.pop()
else:
    for i in range(1, N + 1):
        if color[i] == i0:
            if cand1:
                ans[i] = cand2.pop()
            else:
                ans[i] = cand3.pop()
        else:
            if cand2:
                ans[i] = cand1.pop()
            else:
                ans[i] = cand3.pop()
print(*ans[1:])

Submission status: Runtime Error

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    G[a].add(b)
    G[b].add(a)
color = [None] * (N + 1)


def dfs(G, v, cur):
    color[v] = cur
    for w in G[v]:
        if color[w] is None:
            dfs(G, w, 1 - cur)


dfs(G, 1, 0)
c=collections.Counter(color[1:])
cand1 = set(range(1, N + 1, 3))
cand2 = set(range(2, N + 1, 3))
cand3 = set(range(3, N + 1, 3))

i0, i1 = 0, 1
if c[0] > c[1]:
    i0, i1 = 1, 0

ans = [None] * (N + 1)
if c[i0] <= len(cand3):
    for i in range(1, N + 1):
        if color[i]==i0:
            ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand2:
                ans[i] = cand2.pop()
            else:
                ans[i] = cand3.pop()
else:
    for i in range(1, N + 1):
        if color[i]==i0:
            if cand1:
                ans[i] = cand1.pop()
            else:
                ans[i] = cand3.pop()
        else:
            if cand2:
                ans[i] = cand2.pop()
            else:
                ans[i] = cand3.pop()
print(*ans[1:])

Submission status: Runtime Error

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    G[a].add(b)
    G[b].add(a)
color = [None] * (N + 1)


def dfs(G, v, cur):
    color[v] = cur
    for w in G[v]:
        if color[w] is None:
            dfs(G, w, 1 - cur)


dfs(G, 1, 0)
cand1 = set(range(1, N + 1, 3))
cand2 = set(range(2, N + 1, 3))
cand3 = set(range(3, N + 1, 3))
ans = [None] * (N + 1)
for i in range(1, N + 1):
    if color[i]:
        if len(cand1):
            t = cand1.pop()
        else:
            t = cand3.pop()
    else:
        if len(cand2):
            t = cand2.pop()
        else:
            t = cand3.pop()
    ans[i] = t
print(*ans[1:])

Submission status: Runtime Error

Solution code:
from collections import deque
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 = deque([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: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)


root = None
max_depth = 0


def dfs(v, parent, depth):
    global max_depth, root
    if max_depth < depth:
        max_depth = depth
        root = v
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v, depth+1)


dfs(0, -1, 0)


def dfs2(v, p, gp, ggp):
    if ggp != -1:
        pairs[v].append(ggp)
        pairs[ggp].append(v)
        cnt[v] += 1
        cnt[ggp] += 1
    for v2 in edges[v]:
        if v2 == p:
            continue
        dfs2(v2, v, p, gp)


cnt = defaultdict(int)
pairs = [[]for _ in range(n)]
dfs2(root, -1, -1, -1)


def dfs3(v, parent, c):
    ans[v] = c
    global m1_cnt, m2_cnt
    for v2 in pairs[v]:
        if v2 == parent:
            continue
        if c == 2:
            dc = -1
            m1_cnt -= 1
        elif c == 0:
            if m2_cnt < m1_cnt:
                dc = 1
                m1_cnt -= 1
            else:
                dc = 2
                m2_cnt -= 1
        else:
            dc = 1
            m2_cnt -= 1
        dfs3(v2, v, c+dc)


ans = [-1]*n
m0 = [i for i in range(3, n+1, 3)]
m1 = [i for i in range(1, n+1, 3)]
m2 = [i for i in range(2, n+1, 3)]
m0_cnt = len(m0)
m1_cnt = len(m1)
m2_cnt = len(m2)

for v, values in sorted(cnt.items(), key=lambda x: x[1], reverse=True):
    if ans[v] != -1:
        continue
    if m0_cnt == 0:
        if m1_cnt < m2_cnt:
            dfs3(v, -1, 2)
        else:
            dfs3(v, -1, 1)
    else:
        m0_cnt -= 1
        dfs3(v, -1, 0)


answer = [0]*n
for i in range(n):
    if ans[i] == 0:
        answer[i] = m0.pop()
    elif ans[i] == 1:
        answer[i] = m1.pop()
    elif ans[i] == 2:
        answer[i] = m2.pop()

left = m0+m1+m2

for i in range(n):
    if answer[i] == 0:
        answer[i] = left.pop()
print(*answer)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)


root = None
max_depth = 0


def dfs(v, parent, depth):
    global max_depth, root
    if max_depth < depth:
        max_depth = depth
        root = v
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v, depth+1)


dfs(0, -1, 0)


def dfs2(v, p, gp, ggp):
    if ggp != -1:
        pairs[v].append(ggp)
        pairs[ggp].append(v)
        cnt[v] += 1
        cnt[ggp] += 1
    for v2 in edges[v]:
        if v2 == p:
            continue
        dfs2(v2, v, p, gp)


cnt = defaultdict(int)
pairs = [[]for _ in range(n)]
dfs2(root, -1, -1, -1)

def dfs3(v, parent, c):
    ans[v] = c
    global m1_cnt, m2_cnt
    for v2 in pairs[v]:
        if v2 == parent:
            continue
        if c == 2:
            dc = -1
            m1_cnt -= 1
        elif c == 0:
            if m2_cnt < m1_cnt:
                dc = 1
                m1_cnt -= 1
            else:
                dc = 2
                m2_cnt -= 1
        else:
            dc = 1
            m2_cnt -= 1
        dfs3(v2, v, c+dc)

ans = [-1]*n
m0_cnt = n//3
m1_cnt = (n-1)//3+1
m2_cnt = (n-2)//3+1
for v, values in sorted(cnt.items(), key=lambda x: x[1], reverse=True):
    if ans[v] != -1:
        continue
    if m0_cnt == 0:
        dfs3(v, -1, 2)
    else:
        m0_cnt -= 1
        dfs3(v, -1, 0)
m0 = [i for i in range(3, n+1, 3)]
m1 = [i for i in range(1, n+1, 3)]
m2 = [i for i in range(2, n+1, 3)]

answer = [0]*n
for i in range(n):
    if ans[i] == 0:
        answer[i] = m0.pop()
    elif ans[i] == 1:
        answer[i] = m1.pop()
    elif ans[i] == 2:
        answer[i] = m2.pop()

left = m0+m1+m2

for i in range(n):
    if answer[i] == 0:
        answer[i] = left.pop()
print(*answer)