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: Runtime Error

Solution code:
#C
import sys
input=sys.stdin.readline
from collections import deque

def main():
    n=int(input())
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
    Depth=[-1]*n
    Depth[0]=0
    q=deque()
    q.append(0)
    while q:
        fr=q.popleft()
        for to in Edges[fr]:
            if Depth[to]==-1:
                Depth[to]=Depth[fr]+1
                q.append(to)
    Group=[[] for _ in range(2)]
    for i in range(n):
        Group[Depth[i]%2].append(i)
    #print(Depth,Group)
    l_even,l_odd=len(Group[0]),len(Group[1])
    #print(l_even,l_odd)
    Ans=[0]*n
    Used=[False]*(n+1)
    if l_even<=l_odd:
        if l_even<n//3:
            tmp_3=3
            tmp_others=1
            for i in range(n):
                if Depth[i]%2==0:
                    Ans[i]=tmp_3
                    Used[tmp_3]=True
                    tmp+=3
                else:
                    while Used[tmp_others]:
                        tmp_others+=1
                    Ans[i]=tmp
                    Used[tmp]=True
            print(*Ans)
            exit()
    else:
        if l_odd<n//3:
            tmp_3=3
            tmp_others=1
            for i in range(n):
                if Depth[i]%2==1:
                    Ans[i]=tmp_3
                    Used[tmp_3]=True
                    tmp+=3
                else:
                    while Used[tmp_others]:
                        tmp_others+=1
                    Ans[i]=tmp
                    Used[tmp]=True
            print(*Ans)
            exit()
    tmp_odd,tmp_even,tmp_others=1,2,3
    for i in range(n):
        #print(Depth[i])
        if Depth[i]%2==1:
            if tmp_odd<=n:
                #print('A')
                Ans[i]=tmp_odd
                tmp_odd+=3
            else:
                #print('B')
                Ans[i]=tmp_others
                tmp_others+=3
        else:
            if tmp_even<=n:
                #print('C')
                Ans[i]=tmp_even
                tmp_even+=3
            else:
                #print('D')
                Ans[i]=tmp_others
                tmp_others+=3
    print(*Ans)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
class node:
    def __init__(self, value):
        self.value = value
        self.next = list()
def delete(num):
    for i in cond:
        if i[0]==num or i[1]==num:
            del cond[cond.index(i)]
n = int(input())
nodes = [node(i) for i in range(n)]
temps = [0 for i in range(n)]
ans = [0 for i in range(n)]
for i in range(n-1):
    temp = [int(i) for i in input().split()]
    nodes[temp[0]-1].next.append(temp[1]-1)
    temps[temp[0]-1]+=1
    temps[temp[1]-1]+=1

cond = list()
for i in range(n):
    for j in nodes[i].next:
        for k in nodes[j].next:
            if i == k:
                continue
            for l in nodes[k].next:
                if j == l:
                    continue
                if i != l:
                    cond.append([i, l])
cand = [i for i in range(1, n+1)]
for i in range(3, n, 3):
    ans[temps.index(max(temps))-1] = i
    temps[temps.index(max(temps))] = 0
    del cand[i-1]
    delete(i)
    if len(cond)==0:
        break
i=0
bias = 0
while(i < len(cand)):
    if ans[i+bias] == 0:
        ans[i+bias] = cand[i]
        i+=1
    else:
        bias+=1
print(' '.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

b=bfs(0)
ans=[0]*n
ans[0]=1
c=[0]*n
c[0]=1
x=4
for i in range(n):
  if b[i]%3==1:
    ans[i]=x
    c[x-1]=1
    x+=3
    if x>=n:
      break

ct=0
for i in range(n):
  if ans[i]==0:
    while c[ct]!=0 and ct<n:
      ct+=1
    c[ct]=1
    ans[i]=ct+1
for i in range(n):
  ans[i]=str(ans[i])
print(' '.join(ans))

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
import math
from sys import stdin
from collections import defaultdict
from collections import deque
import heapq

N = int( input())
Cs = [list(map(int,stdin.readline().split()))for _ in range(N -1 )]
INF = 10 ** 15
assign = [-1] * (N + 1)
tree_child_num= [0] * (N + 1) #子供の人数
tree_gen= [0] * (N + 1) #自分の世代
tree_mago = [0] * (N + 1)
tree_himago = [0] * (N + 1) # ひ孫の人数
tree_childs = [[]for _ in  range (N + 1)] # 自分の子供の番号のリスト
tree_nan =  [0] * (N + 1) #自分が何人目の子供か
tree_parens = [0] * (N + 1) #自分の親
tree_sansyou = [0] * (N + 1)
visit = [False] * (N + 1)
graph_connection = defaultdict(lambda :[])
#,何人目の子供か
# (自分の世代+何人目の子供)  で1余る数か2余る数かの割当を決める
# #親の孫の人数 - 自分の子供の人数 + 自分のひ孫の人数
for C in  Cs:
    a,b = C
    graph_connection[a].append(b)
    graph_connection[b].append(a)

que = deque()

que.append(1)
gen = 0
child_num = 0
tree_gen[1] = 0
visit[1] = True
while que:
    v_num = que.pop()
    connects = graph_connection[v_num]
    child_num = 0
    for i in connects:
        if not visit[i]:
            que.append(i)
            tree_gen[i] = tree_gen[v_num] + 1
            tree_nan[i] = child_num
            child_num += 1
            tree_childs[v_num].append(i)
            visit[i] = True
            tree_parens[i] = v_num
            if tree_gen[i] > 1: #孫なら、祖父にフィードバック
                sohu = tree_parens[v_num]
                tree_mago[sohu] += 1
            if tree_gen[i] > 2: #ひ孫なら、曽祖父にフィードバック
                sosohu = tree_parens[sohu]
                tree_himago[sosohu] += 1
    tree_child_num[v_num] = child_num
# for i in range(1,N + 1):
heq  = []
for i in range(1,N+ 1):
    par = tree_parens[i]
    tree_sansyou[i] = tree_himago[i] + tree_mago[par] - tree_child_num[i]
    if tree_sansyou[i] > 0:
        heapq.heappush(heq,(-tree_sansyou[i] , i)) #優先度、番号

#割当フェイズ
ind_0 = 0
lim_0 = N//3
ind_1 = 0
lim_1 = math.ceil ((N - 1)//3) + 1
ind_2 = 0
lim_2 = math.ceil ((N - 2)//3) + 1
while heq: #制約付きの割当
    _,num = heapq.heappop(heq)
    if ind_0 < lim_0:
        assign[num] = (ind_0 + 1) * 3
        ind_0 += 1
    else:
        if tree_nan[num] + tree_gen[num] % 2 == 0: #2を割り当てる
            if ind_1 == lim_1: #割当が足りなくなったら
                print(-1)
                exit(1)
            else:
                assign[num] = (ind_1 ) * 3 + 1
                ind_1 += 1
        else:
            if ind_2 == lim_2: #割当が足りなくなったら
                print(-1)
                exit(1)
            else:
                assign[num] = (ind_2) * 3 + 2
                ind_2 += 1

#残りの数字を割り当てる
for num in range(1,N + 1):
     if assign[num] == -1:
        if ind_0 < lim_0:
            assign[num] = (ind_0 + 1) * 3
            ind_0 += 1

        elif ind_1 < lim_1:
            assign[num] = (ind_1) * 3 + 1
            ind_1 += 1

        elif ind_2 < lim_2:
            assign[num] = (ind_2) * 3 + 2
            ind_2 += 2


print(*assign[1:])

Submission status: Runtime Error

Solution code:
N = int(input().rstrip().split())
a = [list(map(int,input().rstrip().split())) for _ in range(N-1)]
#頂点遷移i→k,k→l,l+jなので、(i j)の組がなく、かつ(i,k),(k,l),(l,j)の組があること。

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import queue

def main():
    N=I()
    adj=[[] for _ in range(N)]
    mod1=range(1,N+1,3)
    n1=0
    mod2=range(2,N+1,3)
    n2=0
    mod3=range(3,N+1,3)
    n3=0
    
    p=[0]*N
    
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
     
    
    q=queue.Queue()
    q.put((0,-1,0))#node,par,depth
    d=[0]*N#深さをメモ
            
        
    while not q.empty():
        v,par,depth=q.get()
        d[v]=depth%2
                
        for i in range(len(adj[v])):
            nxt=adj[v][i]
            if nxt!=par:
                q.put((nxt,v,depth+1))
                
    dmod=[0,0]
    for i in range(N):
        dmod[d[i]]+=1
        
    for i in range(N):
        bit=d[i]
        if dmod[bit]<dmod[(bit+1)%2]:
            if n3<len(mod3):
                p[i]=mod3[n3]
                n3+=1
            elif bit==1:
                if n1<len(mod1):
                    p[i]=mod1[n1]
                    n1+=1
                else:
                    p[i]=mod2[n2]
                    n2+=1
            else:
                if n2<len(mod2):
                    p[i]=mod2[n2]
                    n2+=1
                else:
                    p[i]=mod1[n1]
                    n1+=1
                
        else:
            if bit==1:
                if n1<len(mod1):
                    p[i]=mod1[n1]
                    n1+=1
                else:
                    p[i]=mod2[n2]
                    n2+=1
            else:
                if n2<len(mod2):
                    p[i]=mod2[n2]
                    n2+=1
                else:
                    p[i]=mod1[n1]
                    n1+=1
            
        
                    
                
    
                
    print(' '.join(map(str, p)))
        
        
    
    
        
                
            
        
        
    

main()

Submission status: Runtime Error

Solution code:
#input
N = int(input())
Tree = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    Tree[a].append(b)
    Tree[b].append(a)

# process
# 距離3の頂点を抽出
pair = []
for i in range(N):
    for j in Tree[i]:
        for k in Tree[j]:
            if k == i:
                continue
            for l in Tree[k]:
                if l == j or i > l:
                    continue
                pair.append((i,l))

# 順列を求める
def getAddNum(x, ans):
    t = 0
    for i in range(N):
        if (x+i)%3 == 0:
            t = i

    l = [x for x in range(t, N, 3)]
    for y in l:
        if not y in ans:
            return y

    return -1

def getMulNum(x, ans):
    l = []
    if x%3 == 0:
        return 0
    else:
        l = [n*3 for n in range(1, N//3+1)]

        for y in l:
            if not y in ans:
                return y

    return -1

def getNextNum(x, ans):
    for y in range(x+1, N+1):
        if not y in ans:
            return y
    
ans = [-1 for _ in range(1, N+1)]
n = 0
for a, b in pair:
    a -= 1
    b -= 1
    if ans[a] == -1:
        ans[a] = getNextNum(n, ans)
    
    t = getAddNum(ans[a], ans)
    if t > 0:
        ans[b] = t
    else:
        t = getMulNum(ans[a], ans)
        if t == 0:
            continue
        elif t > 0:
            ans[b] = t
        else:
            ans = []
            break

for i in range(N):
    if ans[i] == -1:
        ans[i] = getNextNum(n, ans)

# output
# print(pair)
if len(ans) == 0:
    print(-1)
else:
    print(" ".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
# N = 9
# AB = [[1, 2], [2, 3], [9, 8], [8, 3], [3, 4], [4, 5], [3, 6], [6, 7]]
if N == 2:
    print(1, 2)
    exit()


class Node:
    def __init__(self, v):
        self.linked = set()
        self.v = v

    def add_node(self, node):
        self.linked.add(node)

    def set_rank(self, parent, rank):
        self.rank = rank
        for node in self.linked:
            if node is parent:
                continue
            node.set_rank(parent=self, rank=rank + 1)

    def __repr__(self):
        return '{}'.format(self.rank)


nodes = {v: Node(v) for v in range(1, N + 1)}
for a, b in AB:
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

# usokaihou
import random

root = nodes[random.randint(1, N)]
root.set_rank(None, 1)

group = [[], [], []]
for node in nodes.values():
    group[node.rank % 3].append(node)
group.sort(key=len)
result = {}
x1 = set()
x2 = set()
x3 = set()

for i in range(1, N + 1):
    if i % 3 == 1:
        x1.add(i)
    elif i % 3 == 2:
        x2.add(i)
    else:
        x3.add(i)

for node in group[0]:
    if x3:
        result[node.v] = x3.pop()
    else:
        import time
        time.sleep(10)
for node in group[1]:
    if x2:
        result[node.v] = x2.pop()
    elif x3:
        result[node.v] = x3.pop()
    else:
        result[node.v] = x1.pop()

for node in group[2]:
    if x1:
        result[node.v] = x1.pop()
    elif x2:
        result[node.v] = x2.pop()
    else:
        result[node.v] = x3.pop()

print(' '.join(str(result[i]) for i in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
from collections import deque

N = int(input())
data1 = []
data2 = [[] for i in range(N)]
data3 = [set() for i in range(N)]

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

for i in range(N-1):
    a,b = data1[i]
    for x in data2[a]:
        for y in data2[b]:
            if y != a and x != b:
                data3[x].add(y)
                data3[y].add(x)

for i in range(N):
    data3[i] = list(data3[i])

#####print(data3)

s = [0,0,0]
while len(data2[s[0]]) <= 1:
    s[0] += 1

s[1] = data2[s[0]][0]
s[2] = data2[s[0]][1]

stack = deque([[s[0],1],[s[1],1],[s[2],2]])
ans = [0] * N
ans[s[0]] = 1
ans[s[1]] = 4
ans[s[2]] = 2
count = [3,7,5]

det = 0
while stack:
    p = stack.pop()
    for q in data3[p[0]]:
        if ans[q] != 0:
            continue
        if count[2] <= N and p[1]%3 != 2:
            ans[q] = count[2]
            count[2] += 3
            stack.append([q,2])
        elif count[1] <= N and p[1]%3 != 1:
            ans[q] = count[1]
            count[1] += 3
            stack.append([q,1])
        else:
            if count[0] > N:
                det = -1
            ans[q] = count[0]
            count[0] += 3
            stack.append([q,0])
        #####print(ans,stack)

if det == -1:
    print(-1)
else:
    print(" ".join(map(str,ans)))

Submission status: Runtime Error

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
# N = 9
# AB = [[1, 2], [2, 3], [9, 8], [8, 3], [3, 4], [4, 5], [3, 6], [6, 7]]
if N == 2:
    print(1, 2)
    exit()


class Node:
    def __init__(self, v):
        self.linked = set()
        self.v = v

    def add_node(self, node):
        self.linked.add(node)

    def set_rank(self, parent, rank):
        self.rank = rank
        for node in self.linked:
            if node is parent:
                continue
            node.set_rank(parent=self, rank=rank + 1)

    def __repr__(self):
        return '{}'.format(self.rank)


nodes = {v: Node(v) for v in range(1, N + 1)}
for a, b in AB:
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

# usokaihou
import random

root = nodes[random.randint(1, N)]
root.set_rank(None, 0)

group = [[], [], []]
for node in nodes.values():
    group[node.rank % 3].append(node)
group.sort(key=len)
result = {}
x1 = set()
x2 = set()
x3 = set()

for i in range(1, N + 1):
    if i % 3 == 1:
        x1.add(i)
    elif i % 3 == 2:
        x2.add(i)
    else:
        x3.add(i)

for node in group[0]:
    result[node.v] = x3.pop()

for node in group[1]:
    if x2:
        result[node.v] = x2.pop()
    elif x3:
        result[node.v] = x3.pop()
    else:
        result[node.v] = x1.pop()

for node in group[2]:
    if x1:
        result[node.v] = x1.pop()
    elif x2:
        result[node.v] = x2.pop()
    else:
        result[node.v] = x3.pop()

print(' '.join(str(result[i]) for i in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
from collections import deque

N = int(input())
data1 = []
data2 = [[] for i in range(N)]
data3 = [set() for i in range(N)]

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

for i in range(N-1):
    a,b = data1[i]
    for x in data2[a]:
        for y in data2[b]:
            if y != a and x != b:
                data3[x].add(y)
                data3[y].add(x)

for i in range(N):
    data3[i] = list(data3[i])

#####print(data3)

s = [0,0,0]
while len(data2[s[0]]) <= 1:
    s[0] += 1

s[1] = data2[s[0]][0]
s[2] = data2[s[0]][1]

stack = deque([[s[0],1],[s[1],1],[s[2],2]])
ans = [0] * N
ans[s[0]] = 1
ans[s[1]] = 4
ans[s[2]] = 2
count = [3,7,5]

while stack:
    p = stack.pop()
    for q in data3[p[0]]:
        if ans[q] != 0:
            continue
        if count[2] <= N and p[1]%3 != 2:
            ans[q] = count[2]
            count[2] += 3
            stack.append([q,2])
        elif count[1] <= N and p[1]%3 != 1:
            ans[q] = count[1]
            count[1] += 3
            stack.append([q,1])
        else:
            ans[q] = count[0]
            count[0] += 3
            stack.append([q,0])
        #####print(ans,stack)

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter

n = int(input())
edges_list = [tuple(int(v) for v in input().split()) for _ in range(n - 1)]
edges = defaultdict(set)
for a, b in edges_list:
    edges[a].add(b)
    edges[b].add(a)

visited = {}
count = [0, 0, 0]

for i in range(1, n + 1):
    dis1 = edges[i]
    dis2 = set().union(*(edges[v] for v in dis1))
    dis2.remove(i)
    dis3 = set().union(*(edges[v] for v in dis2)) - dis1
    flag_cnt = Counter([visited[v] for v in dis3 if v in visited])
    if i in visited:
        flag = visited[i]
        if flag_cnt[1] > 0 and flag_cnt[2] > 0:
            count[flag] -= 1
            count[0] += 1
            flag = 0
        elif flag == 2 and flag_cnt[2] > 0:
            flag = 0
            count[2] -= 1
            count[0] += 1
        elif flag == 1 and flag_cnt[1] > 1:
            flag = 0
            count[1] -= 1
            count[0] += 1
    else:
        if flag_cnt[1] > 0 and flag_cnt[2] > 0:
            flag = 0
        elif flag_cnt[2] == 0:
            flag = 1
        elif flag_cnt[1] == 0:
            flag = 2
        count[flag] += 1
    visited[i] = flag
    
    if flag == 0:
        vflag = 2 if count[1] > count[2] else 1
    elif flag == 1:
        vflag = 2
    else:
        vflag = 1
    for v in (v for v in dis3 if v not in visited):
        visited[v] = vflag
        count[vflag] += 1

result = []
nums = {0: 3, 1: 1, 2: 2}
for i in range(1, n + 1):
    f = visited[i]
    if nums[f] <= n:
        result.append(str(nums[f]))
        nums[f] += 3
    elif nums[0] <= n:
        result.append(str(nums[0]))
        nums[0] += 3
    else:
        assert False, "Failed."

print(" ".join(result))

Submission status: Runtime Error

Solution code:
import collections


N = int(input())
tree = {i: set() for i in range(1, N + 1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)

distance = collections.defaultdict(lambda: collections.defaultdict(list))
visited = set()
for i in range(1, N + 1):
    if i in visited:
        continue
    queue = collections.deque([(0, i)])
    visited.add(i)
    while queue:
        d, cur = queue.popleft()
        for j in tree[cur]:
            if j not in visited:
                distance[i][d + 1].append(j)
                queue.append((d + 1, j))
                visited.add(j)
indices = []
for i, d in distance.items():
    if 3 in d:
        indices.extend([(i, j) for j in d[3]])
    if 1 in d and 2 in d:
        for j in d[1]:
            for k in d[2]:
                if k not in tree[j]:
                    indices.append((j, k))
del distance
del tree
del visited

count = collections.Counter([i for x in indices for i in x])
indices2 = collections.defaultdict(list)
for i, j in indices:
    if count[i] > count[j]:
        indices2[i].append(j)
    else:
        indices2[j].append(i)

del count
del indices


pool = set(range(1, N + 1))
three = set()
for x in pool:
    if x % 3 == 0:
        three.add(x)
pool -= three
rest = {i: set() for i in range(1, 3)}
for x in pool:
    rest[x % 3].add(x)

perm = [0] * N
for i, js in indices2.items():
    if three and (rest[1] or rest[2]):
        perm[i - 1] = three.pop()
        for j in js:
            if rest[1]:
                perm[j - 1] = rest[1].pop()
            elif rest[2]:
                perm[j - 1] = rest[2].pop()
            elif three:
                perm[j - 1] = three.pop()
            else:
                print(-1)
                break

    elif rest[1] and rest[2]:
        if len(rest[1]) > len(rest[2]):
            perm[i - 1] = rest[2].pop()
            for j in js:
                if rest[1]:
                    perm[j - 1] = rest[1].pop()
                elif three:
                    perm[j - 1] = three.pop()
                else:
                    print(-1)
                    break
        else:
            perm[i - 1] = rest[1].pop()
            for j in js:
                if rest[2]:
                    perm[j - 1] = rest[2].pop()
                elif three:
                    perm[j - 1] = three.pop()
                else:
                    print(-1)
                    break
    else:
        print(-1)
        break
else:
    rest = rest[1] | rest[2]
    if rest:
        for i in range(N):
            if perm[i] == 0:
                perm[i] = rest.pop()
    print(*perm)

Submission status: Runtime Error

Solution code:
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
# N = 9
# AB = [[1, 2], [2, 3], [9, 8], [8, 3], [3, 4], [4, 5], [3, 6], [6, 7]]
if N == 2:
    print(1, 2)
    exit()
if N == 3:
    print(1, 2, 3)
    exit()


class Node:
    def __init__(self, v):
        self.linked = set()
        self.v = v

    def add_node(self, node):
        self.linked.add(node)

    def set_rank(self, parent, rank):
        self.rank = rank
        for node in self.linked:
            if node == parent:
                continue
            node.set_rank(parent=self, rank=rank + 1)

    def __repr__(self):
        return '{}'.format(self.rank)


nodes = {v: Node(v) for v in range(1, N + 1)}
for a, b in AB:
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

# usokaihou
import random

root = nodes[random.randint(1, N)]
root.set_rank(None, 0)

group = [[], [], []]
for node in nodes.values():
    group[node.rank % 3].append(node)
group.sort(key=len)
result = {}
x1 = set()
x2 = set()
x3 = set()

for i in range(1, N + 1):
    if i % 3 == 1:
        x1.add(i)
    elif i % 3 == 2:
        x2.add(i)
    else:
        x3.add(i)

for node in group[0]:
    result[node.v] = x3.pop()

for node in group[1]:
    if x2:
        result[node.v] = x2.pop()
    elif x3:
        result[node.v] = x3.pop()
    else:
        result[node.v] = x1.pop()

for node in group[2]:
    if x1:
        result[node.v] = x1.pop()
    elif x2:
        result[node.v] = x2.pop()
    else:
        result[node.v] = x3.pop()

print(' '.join(str(result[i]) for i in range(1, N + 1)))

Submission status: Runtime Error

Solution code:
from collections import Counter


def solve():
    N = int(input())
    edges = dict()
    for _ in range(N-1):
        a, b = [int(x) for x in input().split(" ")]
        target_node = edges.get(a, [])
        target_node.append(b)
        edges[a] = target_node

        target_node = edges.get(b, [])
        target_node.append(a)
        edges[b] = target_node

    three_hop_nodes = set()
    start_node_edge = dict()
    node_freq = Counter()
    for start_node in edges:
        for one_hop in (x for x in edges.get(start_node, [])):
            for two_hop in (x for x in edges.get(one_hop, []) if x != start_node):
                for three_hop in (x for x in edges.get(two_hop, []) if x != one_hop):
                    print(start_node, one_hop, two_hop, three_hop)
                    three_hop_edge = (start_node, three_hop) if start_node < three_hop else (three_hop, start_node)
                    node_freq.update([start_node, three_hop])
                    start_node_edge[start_node] = start_node_edge.get(start_node, []) + [(start_node, three_hop)]
                    start_node_edge[three_hop] = start_node_edge.get(three_hop, []) + [(three_hop, start_node)]
                    three_hop_nodes.add(three_hop_edge)

    mod_min = {0: 3, 1: 1, 2: 2}
    answer = [0] * N
    for node in sorted(node_freq, reverse=True):
        for edge in start_node_edge[node]:
            target_node = edge[1]
            if answer[node-1] > 0 and answer[target_node-1] > 0:
                continue
            if answer[target_node-1] > 0:
                key = (answer[target_node-1] + 1) % 3
                num = mod_min[key]
                if num > N:
                    print(-1)
                    return
                answer[node-1] = num
                mod_min[key] += 3
            else:
                found = False
                num = mod_min[key]
                if num > N:
                    print(-1)
                    return
                answer[node-1] = num
                mod_min[key] += 3

            searched.add(ordered_edge)


solve()