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:
class Tree:
    def __init__(self, N):
        self.N = N # #vertices
        self.D = (self.N-1).bit_length() # #iterations in doubling
        self.E = [{} for _ in range(N)]
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def lca_initialize(self):
        self.dfs(0)
        self.doubling()
    
    def dfs(self, root):
        # parents[v]: the parent of the vertex v
        # depth[v]: the depth of the vertex v from the root
        # dist[v]: the distance of the vertex v from the root.
        self.parent = [None] * self.N
        self.depth = [None] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u, d in self.E[v].items():
                if self.depth[u] is not None: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + d
                stack.append(u)
    
    def doubling(self):
        # O(N log N) time
        self.next = [[-1] * self.N for _ in range(self.D)]
        for v in range(self.N):
            self.next[0][v] = self.parent[v]
        for d in range(self.D - 1):
            for v in range(self.N):
                if self.next[d][v] != -1:
                    self.next[d + 1][v] = self.next[d][self.next[d][v]]
    
    def lca(self, u, v):
        # O(log N) time
        # the depth of v is set to be no less than that of u
        if self.depth[u] > self.depth[v]: u, v = v, u
        # find the ancestor of v with the same depth as that of u
        diff = self.depth[v] - self.depth[u]
        for i in range(diff.bit_length()):
            if diff & (1 << i): v = self.next[i][v]
        if u == v: return u
        for i in range(self.depth[u].bit_length() - 1, -1, -1):
            pu, pv = self.next[i][u], self.next[i][v]
            if pu != pv: u, v = pu, pv
        return self.next[0][u]

N = int(input())
tr = Tree(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    tr.add_edge(a-1, b-1, 1, undirected=True)
tr.dfs(0)
d_odd, d_even = [], []
rem = [[] for _ in range(3)]
for i in range(N):
    if tr.depth[i] % 2 == 0: d_even.append(i)
    else: d_odd.append(i)
    rem[(i+1)%3].append(i+1)
P = [0] * N
flag = True
if len(d_odd) < len(d_even):
    for i in d_odd:
        if rem[2]:
            P[i] = rem[2].pop()
        elif rem[0]:
            P[i] = rem[0].pop()
        else:
            flag = False; break
    temp = rem[0] + rem[1]
    if flag:
        for i in d_even:
            if temp:
                P[i] = temp.pop()
            else:
                flag = False; break
else:
    for i in d_even:
        if rem[2]:
            P[i] = rem[2].pop()
        elif rem[0]:
            P[i] = rem[0].pop()
        else:
            flag = False; break
    temp = rem[0] + rem[1]
    if flag:
        for i in d_odd:
            if temp:
                P[i] = temp.pop()
            else:
                flag = False; break
if flag:
    print(*P)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = []
three = []
result = ''

for i in range(N-1):
    edges.append(list(map(int, input().split())))
    edges[i].append(1)
#print(edges)

def BFS(K, w, edges, N):
    roots = [[] for i in range(N)]
    for a, b, c in edges:
        roots[a-1] += [(b-1, c)]
        roots[b-1] += [(a-1, c)]
    dist = [-1]*N
    stack = []
    stack.append(K)
    dist[K] = 0
    while stack:
        label = stack.pop(-1)
        for i, c in roots[label]:
            if dist[i] == -1:
                dist[i] = dist[label]+c
                stack += [i]
            if i == w:
                return dist[w]

for i in range(1,N+1):
    for j in range(1,N+1):
        #print(i,j)
        if i == j:
            break
        distance = BFS(i-1, j-1, edges, N)
        #print(distance,":",i,",",j)
        if distance == 3:
            three.append([i,j])
#print(three)
vertex = []
for i in range(1, N+1):
    vertex.append(i)


def chk(a,b):
    # 掛けたら3の倍数か
    if (a * b) % 3 == 0:
        return True
    # 足したら3の倍数か
    if (a+b)%3 == 0:
        return True
    # 距離3に含まれているか
    for th in three:
        if (th[0] == a and th[1] == b) or (th[0] == b and th[1] == a):
            return True
    return False
import itertools
itert = itertools.permutations(vertex)
for i in itert:
    #print(i)
    for j in range(N-1):
        if chk(i[j],i[j+1]):
            flg = True
            for k in range(N):
                if flg:
                    result += str(i[k])
                else:
                    result += " "+str(i[k])
            print(result)
            exit()
print(-1)
'''
7
2 3
5 3
3 4
3 1
4 6
4 7
'''

Submission status: Wrong Answer

Solution code:
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)
d = [-1] * n
s = [0]
d[0] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            d[node] = (d[p] + 1) % 2
            s.append(node)
a = d.count(0)
b = d.count(1)
if a > b:
    tmp = 0
else:
    tmp = 1
a, b = max(a, b), min(a, b)
ans = [0] * n
if a - b <= n // 3:
    p = 1
    q = 2
    t = 3
    for i in range(n):
        if d[i] == tmp:
            if t <= n and a >= b:
                ans[i] = t
                t += 3
            else:
                ans[i] = p
                p += 3
        else:
            if t <= n and a <= b:
                ans[i] = t
                t += 3
            else:
                ans[i] = q
                q += 3
else:
    t = 3
    k = 1
    for i in range(n):
        if d[i] == tmp:
            ans[i] = k
            k += 1
            if k % 3 == 0:
                k += 1
        else:
            ans[i] = t
            t += 3
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

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

ans = [-1] * N

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

from collections import deque

for i in range(N):
    que = deque([i])
    dist = [-1] * N
    dist[i] = 0

    while que:
        v = que.popleft()
        d = dist[v]

        for w in E[v]:
            if dist[w] >= 0:
                continue
            dist[w] = d + 1
            if dist[w] == 3:
                dist3[i].append(w)
            else:
                que.append(w)

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)
C=[-1]*n
C2=[-1]*n
def ch(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C[x]=0
    return C[x]
  else:
    for e in edge[x]:
      if e==prv[x]:
        continue
      else:
        ret+=1
    C[x]=ret
    return C[x]
def ch2(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C2[x]=0
    return C2[x]
  else:
    for e in edge[x]:
      if e==prv[x]:
        continue
      else:
        ret+=C[e]
    C2[x]=ret
    return C2[x]
for i in range(n):
  ch(i)
for i in range(n):
  ch2(i)

TH=[0]*n
for i in range(n):
  if i==0:
    cur=0
  elif depth[i]==1:
    cur=C2[prv[i]]-C[i]
  else:
    cur=C2[prv[i]]+C[prv[prv[i]]]-C[i]-1
  if depth[i]>=3:
    cur+=1
  for e in edge[i]:
    if e==prv[i]:
      continue
    else:
      cur+=C2[e]
  TH[i]=cur
TH2=[0]*n
for i in range(n):
  TH2[i]=TH[i]*(10**6)+i
TH2.sort(reverse=True)
Ans=[0]*n
ct1,ct2,ct3=0,0,0
for i in range(3,n,3):
  if TH[TH2[i//3-1]%(10**6)]>3:
    Ans[TH2[i//3-1]%(10**6)]=i
    ct3+=1
for i in range(n):
  if Ans[i]!=0:
    continue
  else:
    if depth[i]%2==0:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      elif 3*ct3+3<=n:
        Ans[i]=3*ct3+3
        ct3+=1
      else:
        Ans[i]=3*ct2+2
        ct2+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      elif 3*ct3+3<=n:
        Ans[i]=3*ct3+3
        ct3+=1
      else:
        Ans[i]=3*ct1+1
        ct1+=1
if max(Ans)>n:
  print(-1)
else:
  print(*Ans)

Submission status: Wrong Answer

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

N = int(input())

p = [[] for _ in range(N)]
c = [[] for _ in range(N)]

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

three = []
for i in range(N):
    if not p[i]:
        continue
    parent = p[i][0]
    for j in c[parent]:
        if i == j:
            continue
        for k in c[j]:
            three.append((i, k))

ans = [0] * N
idx = 1
used = set()
for l, r in three:
    if l > r:
        l, r = r, l
    if ans[l] == 0:
        ans[l] = str(3 * idx)
        used.add(3 * idx)


n = 1
for i in range(N):
    if ans[i]:
        continue
    if n in used:
        n += 1
    ans[i] = str(n)
    n += 1

print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())

dp = [None]*N
for i in range(N):
    dp[i] = []

for i in range(N-1):
    x,y = map(int,input().split(' '))
    dp[x-1].append(y-1)
    dp[y-1].append(x-1)
#根をkとしたときに距離が3である頂点を求めるdfs
#r:根,m:頂点,d:距離,l:ans,v:visited
def DFS(r,m,d,l,v):
    elm = dp[m]
    if v[m]:
        return l
    v[m] = True
    if d==3:
        # print(r,m)
        if r<m:
            l.append(m)
        return l
    else:
        d += 1
        for j in dp[m]:
            # print('a',d,j,l)
            l = DFS(r,j,d,l,v)
        return l

ANS = [None]*N
for i in range(N):
    VISITED = [False]*N
    ANS[i] = DFS(i,i,0,[],VISITED)

ans = [None]*N
cnt = 1
CNT = 3#3の倍数用
for i in range(N):
    if not ANS[i]==[]:
        if CNT<=N:
            ans[i] = CNT
            CNT += 3
            continue

    if cnt>N:
        ans[i] = CNT
        CNT += 3
        continue

    ans[i] = cnt
    cnt+=1
    if cnt%3==0:
        cnt += 1
print(*ans)

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def eulerian_trail(tree, max_v, root=0):
    """
    木のオイラー路; オイラーツアー
    :param list of (list of (int, int)) tree:
    :param int max_v:
    :param int root:
    :return: (trails, depths, weights)
    :rtype: (list of int, list of int, list of int)
    """
    seen = [False] * (max_v + 1)
    # 頂点の履歴
    trails = []
    # 深さの履歴
    depths = []
    # 距離の履歴
    weights = []
    # Overflow 回避のためループで
    stack = [(root, 0, 0, True)]
    while stack:
        v, d, w, forward = stack.pop()
        seen[v] = True
        trails.append(v)
        depths.append(d)
        weights.append(w)
        if not forward:
            continue

        for u, w in tree[v]:
            if not seen[u]:
                stack.append((v, d, -w, False))
                stack.append((u, d + 1, w, True))
    return trails, depths, weights


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]

# AB = generate_tree(N)
# plot_graph(AB)
# for a, b in AB:
#     graph[a].append((b, 1))
#     graph[b].append((a, 1))

for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append((b, 1))
    graph[b].append((a, 1))


counts = [N // 3, (N + 2) // 3, (N + 1) // 3]
vs, _, _ = eulerian_trail(graph, N - 1)
# 交互に割り当てる
ansmod = [-1] * N
n = 1
for i, v in enumerate(vs):
    if ansmod[v] < 0 and counts[n] > 0:
        counts[n] -= 1
        ansmod[v] = n
    n = 1 if n == 2 else 2

if counts[1] > 0 or counts[2] > 0:
    print(-1)
    exit()

ans = []
M = [3, 1, 2]
for a in ansmod:
    if a == -1:
        a = 0
    ans.append(M[a])
    M[a] += 3
print(*ans)

Submission status: Wrong Answer

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)]
es = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

class TREE(object):
    def __init__(self, G, root=0):
        self.G = G
        self.root = root
        self.n = len(G)
        self.logn = (self.n - 1).bit_length()
        self.depth = [-1 if i != root else 0 for i in range(self.n)]
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.dfs()
        # self.doubling()

    def dfs(self):
        que = [self.root]
        while que:
            u = que.pop()
            for v in self.G[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    self.parent[0][v] = u
                    que += [v]


depth = TREE(es).depth

ans = [0]*n
ans = [1 if d % 2 == 0 else 2 for d in depth]

print(*ans, sep=' ')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap





@mt
def slv(N, AB):
    G = defaultdict(set)
    for a, b in AB:
        G[a].add(b)
        G[b].add(a)

    def bfs(s):
        q = deque([s])
        done = {s: 0}
        d3 = []
        while q:
            u = q.popleft()
            for v in G[u]:
                if v not in done:
                    done[v] = done[u] + 1
                    if done[v] == 3 and s < v:
                        d3.append(v)
                    elif done[v] < 3:
                        q.append(v)
        return d3

    l3e = []
    rg = defaultdict(set)
    for u in range(1, N+1):
        for v in bfs(u):
            l3e.append((u, v))
            rg[u].add(v)
            rg[v].add(u)


    def dfs(a, unused_num, rem_v):
        if not rem_v:
            return a
        u, count = rem.pop()
        for c in unused_num:
            for v in rg[u]:
                if a[v] != -1:
                    pass
                if (c + a[v]) % 3 != 0 and (c * a[v]) % 3 != 0:
                    break
            else:
                a[u] = c
                unused_num.remove(c)
                r = dfs(a, unused_num, rem)
                if r:
                    return r
                a[u] = -1
                unused_num.add(c)
        return False


    rem = [(k, len(rg[k])) for k in rg]
    rem.sort()
    ans = [-1] * (N+1)
    r = dfs(ans, set(range(1, N+1)), rem)
    if not r:
        return -1

    unused = set(range(1, N+1)) - set(r)
    for i in range(1, N+1):
        if ans[i] == -1:
            ans[i] = unused.pop()
    return ans[1:]


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    print(*slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    Par = [0 for _ in range(N)]
    Son = [[] 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)
    Dist = [0] * N
    q = deque()
    q.append((0, 0, 0)) #(now, pre, dist)
    modCount = [N // 3, N // 3, N // 3]
    if N % 3 == 1: modCount[1] += 1
    elif N % 3 == 2:
        modCount[1] += 1
        modCount[2] += 1
    modIndex = [0, 0, 0]
    search = deque()
    while q:
        nowNode, preNode, dist = q.popleft()
        Dist[nowNode] = dist
        Par[nowNode] = preNode
        Son[preNode].append(nowNode)
        search.append(nowNode)
        for nextNode in Edge[nowNode]:
            if nextNode != preNode: q.append((nextNode, nowNode, dist + 1))

    Ans = [-1] * N
    while search:
        nowNode = search.popleft()
        dType = Dist[nowNode] % 2
        if modIndex[dType + 1] < modCount[dType + 1]: 
            Ans[nowNode] = 3 * modIndex[dType + 1] + dType + 1
            modIndex[dType + 1] += 1
        elif modIndex[0] < modCount[0]:
            Ans[nowNode] = 3 * modIndex[0] + 3
            modIndex[0] += 1
        else:
            if Dist[nowNode] < 2:
                Ans[nowNode] = 3 * modIndex[dType ^ 1] + (dType ^ 1) + 1
                modIndex[dType ^ 1] += 1
            else:
                f = Par[nowNode]
                g = Par[f]
                if Ans[g] % 3 == dType ^ 1 + 1:
                    print(-1)
                    break
                else:
                    possible = True
                    for u in Son[g]:
                        if u != f and Ans[u] % 3 == dType ^ 1 + 1:
                            possible = False
                            break
                    if possible:
                        Ans[nowNode] = 3 * modIndex[dType ^ 1] + (dType ^ 1) + 1
                        modIndex[dType ^ 1] += 1
                    else:
                        print(-1)
                        break
    else:
        print(" ".join(map(str, Ans)))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def dijkstra(s, n, w, cost):
    # 始点sから各頂点への最短距離
    # n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        # まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d

################################
#n, w = map(int, input().split())  # n:頂点数　w:辺の数
n = int(input())  # n:頂点数　w:辺の数
w = n-1

cost = [[float("inf") for i in range(n)] for i in range(n)]
# cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
z=1
for i in range(w):
    # x, y, z = map(int, input().split())
    x, y = map(int, input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z
#print(dijkstra(1, n, w, cost))
li1 = []
check = False
for i in range(n):

    if 3 in dijkstra(i, n, w, cost):
        check=True
ans=[3]*n
if check:
    print(ans)
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
from collections import deque
l = [deque() for _ in range(N)]
for a,b in ab:
  l[a-1].append(b-1)
  l[b-1].append(a-1)
  
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
class Tree:
  C, RL = {}, {}
  R, N, D, S, P, T = None, None, None, None, None, None
  TL = None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N #各ノードのランク
    s.R[root] = 1
    s.RL[1] = [root] #各ランクのノード
    s.S = {} #各ノードの子ノード
    s.P = [-1] * s.N #各ノードの親ノード
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i
      s.D += 1
      F = Ft
  def dfs(s, x, y, r): #xからyまでの道O(M)
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False
  def dist(s, x): #最遠のノード,距離
    t = [-1] * s.N
    S = [x]
    ans = x
    ansn = 0
    t[x] = 0
    while S != []:
      k = S.pop()
      for i in s.C[k]:
        if t[i] == -1:
          t[i] = t[k] + 1
          S.append(i)
          if t[i] > ansn:
            ansn = t[i]
            ans = i
    return ans, ansn
  def getDi(s, x = 0): #直径
    a, _ = s.dfs(x)
    b, ans = s.dfs(a)
    return ans
  def getDeep(s, x): #xの子孫のうち一番深い深さ
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n): #xのn世代前の親
    if n == 0:
      return x
    if s.P[x] == -1:
      return -n
    return s.getParent(s.P[x], n - 1)
  def abList(s):
    A = []
    B = []
    for i in range(s.N):
      if s.R[i] % 2 == 0:
        A.append(i)
      else:
        B.append(i)
    if len(A) > len(B):
      return [B, A]
    else:
      return [A, B]



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

A = []
B = []
C = []

for i in range(1, N + 1):
  if i % 3 == 0:
    C.append(i)
  elif i % 3 == 1:
    A.append(i)
  else:
    B.append(i)

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

T.makeRank(0)

A, B = T.abList()

c = N // 3

Ans = [0] * N
if len(A) <= c:
  t = 3
  k = 1
  for i in A:
    Ans[i] = t
    t += 3
    c -= 1
  for i in range(N):
    if Ans[i] == 0:
      if c != 0:
        Ans[i] = t
        c -= 1
      else:
        Ans[i] = k
        k += 1
        if k % 3 == 0:
          k += 1
else:
  t = 3
  n = N // 3
  if N % 3 != 0:
    n += 1
  k = 1
  for i in range(n):
    Ans[A[i]] = k
    k += 3
  for i in range(n, len(A)):
    Ans[A[i]] = t
    t += 3
  n = N // 3
  if N % 3 == 2:
    n += 1
  k = 2
  for i in range(n):
    Ans[B[i]] = k
    k += 3
  for i in range(n, len(B)):
    Ans[B[i]] = t
    t += 3

print(" ".join(list(map(str, Ans))))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
from collections import deque


class Tree():
    def __init__(self,n,edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append((e[1] - 1, 1))
            self.tree[e[1] - 1].append((e[0] - 1, 1))
    def setroot(self,root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.distance = [None for _ in range(self.n)]
        self.distance[root] = 0
        stack = [root]
        while stack:
            node = stack.pop()
            for adj,cost in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node]+1
                    self.distance[adj] = self.distance[node]+cost
                    stack.append(adj)
    def diam(self):
        u = self.distance.index(max(self.distance))
        dist_u = [None for _ in range(N)]
        dist_u[u] = 0
        stack = [u]
        while stack:
            node = stack.pop()
            for adj,cost in self.tree[node]:
                if dist_u[adj] is None:
                    dist_u[adj] = dist_u[node]+cost
                    stack.append(adj)
        d = max(dist_u)
        v = dist_u.index(d)
        return d,u,v
    def construct_lca(self):
        L = (self.n-1).bit_length()
        self.k_parent = [self.parent]
        prev = self.parent
        for k in range(L):
            array = [0 for _ in range(self.n)]
            for i in range(self.n):
                if prev[i] == -1: continue
                array[i] = prev[prev[i]]
            self.k_parent.append(array)
            prev = array
    def lca(self,u,v):
        d = self.depth[v]-self.depth[u]
        if d < 0: u,v,d = v,u,-d
        for k in self.k_parent:
            if d & 1: v = k[v]
            d >>= 1
        if u == v: return u
        for k in reversed(self.k_parent):
            pu,pv = k[u],k[v]
            if pu != pv: u,v = pu,pv
        return self.k_parent[0][u]
    def dist(self,u,v):
        l = self.lca(u,v)
        return self.distance[u]+self.distance[v]-2*self.distance[l]

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


t = Tree(n, info)
t.setroot(0)
t.construct_lca()
d,u,v = t.diam()
distance2 = []
for i in range(n):
    distance2.append(max(t.dist(i,u), t.dist(i,v)))


root = 0
visited = [-1] * n
def dfs(root):
    q = deque([root])
    visited[0] = 0
    while q:
        v = q.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v] != -1:
                continue
            else:
                visited[nxt_v] = (visited[v] + 1) % 2
                q.append(nxt_v)
dfs(0)
for i in range(n):
    if distance2[i] < 3:
        visited[i] = -1

cnt1 = n // 3 
cnt2 = n // 3
cnt3 = n // 3
if n % 3 >= 1:
   cnt1 += 1
if n % 3 >= 2:
   cnt2 += 1

# print(visited)
# print(cnt1, cnt2, cnt3)

cnt = [0, 0]
for i in range(n):
    if visited[i] == 0:
        cnt[0] += 1
    elif visited[i] == 1:
        cnt[1] += 1


if cnt[0] >= cnt[1]:
    pass
else:
    for i in range(n):
        if visited[i] == 0:
            visited[i] = 1
        elif visited[i] == 1:
            visited[i] = 0

set1 = set()
set2 = set()
set3 = set()
for i in range(1, n + 1):
    if i % 3 == 0:
        set3.add(i)
    elif i % 3 == 1:
        set1.add(i)
    elif i % 3 == 2:
        set2.add(i)

ans = [0] * n
num147 = 0
num258 = 0
num369 = 0
for i in range(n):
    if visited[i] == -1:
        continue
    elif visited[i] == 0:
        num = num147 * 3 + 1
        if num > n:
            num = num369 * 3 + 3
            ans[i] = num
            if num > n:
                print(-1)
                exit()
            set3.remove(num)
            num369 += 1
            continue
        ans[i] = num # 1, 4, 7, 10, ...
        set1.remove(num)
        num147 += 1
    else:
        num = num258 * 3 + 2 
        if num > n:
            num = num369 * 3 + 3
            if num > n:
                print(-1)
                exit()
            ans[i] = num
            set3.remove(num)
            num369 += 1
            continue
        ans[i] = num # 2, 5, 8, 11, ...
        set2.remove(num)
        num258 += 1

for i in range(n):
    if ans[i] == 0:
        if set1:
            ans[i] = set1.pop()
        elif set2:
            ans[i] = set2.pop()
        elif set3:
            ans[i] = set3.pop()
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
N = int(input())

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

g3 = defaultdict(list)
for s in range(1,N+1):
    visited = [False] * (N+1)
    d1 = []
    d2 = []
    d3 = []
    for nv in g[s]:
        if not visited[nv]:
            d1.append(nv)
            visited[nv] = True
    for v in d1:
        for nv in g[v]:
            if not visited[nv]:
                d2.append(nv)
                visited[nv] = True
    for v in d2:
        for nv in g[v]:
            if not visited[nv]:
                d3.append(nv)
                visited[nv] = True
    g3[s]=d3

#print(g3)
ls = sorted([(len(v),k) for k,v in g3.items()], reverse=True)

N3 = N//3
ans = [0]*(N+1)
for (l,ind),i in zip(ls,range(N3)):
    n = 3*(i+1)
    ans[ind] = n

#print(ans)

cnt = 0
for i in range(1,N+1):
    if ans[i] != 0:
        continue
    cnt += 1
    if cnt % 3 == 0:
        cnt += 1
    ans[i] = cnt

print(ans[1:])