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
input = sys.stdin.readline
n = int(input())
C = [list(map(int,input().split())) for i in range(n-1)]

V = [0] * (n+1)
PP = [[] for i in range(n+1)]

M = [[] for i in range(n+1)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])

# 1始まりの場合
Q = [[1,-1,-1]]
s = 0
V[1] = 1
while s < len(Q):
    # print(Q)
    i = Q[s][0]
    p = Q[s][1]
    pp = Q[s][2]
    if pp >= 0:
        for y in M[pp]:
            if y != p:
                PP[y].append(i)
                PP[i].append(y)

    for x in M[i]:
        if V[x] == 0:
            V[x] = 1
            Q.append([x, i, p])
    s += 1
# print(PP)
vv = -1
V = [0] * (n+1)
for i in range(len(PP)):
    if len(PP[i]) == 0:
        vv += 1
        V[i] = -1
# print(vv)
mi = vv

J = [n//3 for i in range(3)]
if n%3==1:
    J[1] += 1
elif n%3==2:
    J[1] += 1
    J[2] += 1
# print(J)
# J[1] = max(0, J[1] - vv//2)
# J[2] = max(0, J[2] - vv//2)
# if vv%2==1:
#     J[1] = max(0, J[1] - 1)
# print(J)

# print("V",V)
# r = -1
# R = [[], []]
QQ = [[] for i in range(n+1)]
c0 = -1
for ii in range(n+1):
    if V[ii] == 0:
        c0 += 2
        # r += 1
        Q = [[ii,c0]]
        # print(Q)
        
        s = 0
        V[ii] = c0
        while s < len(Q):
            # print(Q)
            i = Q[s][0]
            cc = Q[s][1]
            # if p >= 0:
            #     for y in PP[p]:
            #         if y != i:
            #             QQ[y].append(i)
            #             R[r].append(y)
            #             # QQ[i].append(y)

            for x in PP[i]:
                if V[x] == 0:
                    V[x] = cc+1 if cc%2==1 else cc-1
                    Q.append([x,V[x]])
            s += 1
# print("V",V)

# print(QQ)
R = [[] for i in range(6)]
for i in range(n+1):
    if V[i] >= 1:
        R[V[i]-1].append(i)

# if len(R[1]) > len(R[0]):
#     R = [R[1], R[0]]


# print("R",R)
JJ = [[0,1,0,1,0,1],[0,1,0,1,1,0],
[0,1,1,0,0,1],[0,1,1,0,1,0],[1,0,0,1,0,1],
[1,0,0,1,1,0],[1,0,1,0,0,1],[1,0,1,0,1,0]]

ok = 0
for jj in range(8):
    if ok == 1:
        break
    le = [0,0]
    for kk in range(6):
        # print(JJ[jj][kk])
        # print(R)
        # print(R[kk])
        le[JJ[jj][kk]] += len(R[kk])
        
    if max(0, J[1]-le[0]) + max(0, J[2]-le[1]) <= mi:
        RR = [[],[]]
        for kk in range(6):
            RR[JJ[jj][kk]] += R[kk]
        R = RR
        # print("R",R)
        ANS = [-1] * n
        ok = 1
        for i in R[0]:
            if J[1]==0:
                break
            ANS[i-1] = 1
            J[1] -= 1

        for i in R[1]:
            if J[2] == 0:
                break
            ANS[i-1] = 2
            J[2] -= 1
            
        tt = 0
        # print(ANS)
        for i in range(len(ANS)):
            if ANS[i] == -1:
                while J[tt] == 0:
                    tt += 1
                ANS[i] = tt
                J[tt] -= 1
        # print(J)
        # print(ANS)

        K = [1,0,0]
        for i in range(len(ANS)):
            ANS[i] += K[ANS[i]%3] * 3
            K[ANS[i]%3] += 1
        # print(ANS)
        print(" ".join([str(i) for i in ANS]))

if ok == 0:
    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)
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):
  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:
      Ans[i]=3*ct1+1
      ct1+=1
    else:
      Ans[i]=3*ct2+2
      ct2+=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())
g = [[] for i in range(N)]
for i in range(N-1):
    a, b = (int(i) for i in input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

c = [-1]*N
c[0] = 1
start = 0
Q = [start]
while Q:
    v = Q.pop()
    oc = c[v]
    for u in g[v]:
        if c[u] == -1:
            c[u] = 3-oc
            Q.append(u)

zeroma = N//3
itima = zeroma + int(N%3!=0)
nima = zeroma + int(N%3==2)
zc, ic, nc = (0, 0, 0)
zv, iv, nv = (3, 1, 2)
ans = [0]*N
for i in range(N):
    if c[i] == 1:
        if ic >= itima:
            if zc < zeroma:
                ans[i] = zv
                zv += 3
                zc += 1
            else:
                break
        else:
            ans[i] = iv
            iv += 3
            ic += 1
    else:
        if nc >= nima:
            if zc < zeroma:
                ans[i] = zv
                zv += 3
                zc += 1
            else:
                break
        else:
            ans[i] = nv
            nv += 3
            nc += 1
else:
    ans = [str(i) for i in ans]
    print(" ".join(ans))
    exit()

c = [3-i for i in c]
zc, ic, nc = (0, 0, 0)
zv, iv, nv = (3, 1, 2)
ans = [0]*N
for i in range(N):
    if c[i] == 1:
        if ic >= itima:
            if zc < zeroma:
                ans[i] = zv
                zv += 3
                zc += 1
            else:
                break
        else:
            ans[i] = iv
            iv += 3
            ic += 1
    else:
        if nc >= nima:
            if zc < zeroma:
                ans[i] = zv
                zv += 3
                zc += 1
            else:
                break
        else:
            ans[i] = nv
            nv += 3
            nc += 1
else:
    ans = [str(i) for i in ans]
    print(" ".join(ans))
    exit()

print("-1")

Submission status: Wrong Answer

Solution code:
import queue
n = int(input())
l = [[] for _ in range(n)]
for i in range(n - 1):
    a,b = map(int, input().split())
    l[a-1].append(b - 1)
    l[b-1].append(a - 1)

l3 = [[] for _ in range(n)]

l32 = [[0] for _ in range(n)]
for i in range(n):
    l32[i].append(i)


for x in range(n):
    d = [10] * n
    d[x] = 0
    q = queue.Queue()
    q.put([x,0])
    while not q.empty():
        p = q.get()
        for j in range(len(l[p[0]])):
            y = l[p[0]][j]
            if d[y] == 10:
                d[y] = p[1] + 1
                if d[y] == 3:
                    l32[y][0] += 1
                    if x < y:
                        l3[x].append(y)
                else:
                    q.put([y,d[y]])

l32.sort()

n3 = n // 3
if n%3==0:
    ln = [n3,n3]
elif n % 3 == 1:
    ln = [n3+1,n3]
else:
    ln = [n3+1,n3+1]

ans1 = [4] * n
for i in range(n3):
    ans1[l32[-i - 1][1]] = 0


h = 1
for i in range(n-1):
    if ans1[i] == 1:
        for j in range(len(l3[i])):
            if ans1[l3[i][j]] != 0:
                ans1[l3[i][j]] = 2
    if ans1[i] == 2:
        for j in range(len(l3[i])):
            if ans1[l3[i][j]] != 0:
                ans1[l3[i][j]] = 1
    if ans1[i] == 4:
        if h == 1:
            ans1[i] = 1
            h = 2
            for j in range(len(l3[i])):
                if ans1[l3[i][j]] != 0:
                    ans1[l3[i][j]] = 2
        else:
            ans1[i] = 2
            h = 1
            for j in range(len(l3[i])):
                if ans1[l3[i][j]] != 0:
                    ans1[l3[i][j]] = 1

c1 = ans1.count(1)
c2 = ans1.count(2)
r1 = ln[0] - c1
r2 = ln[1] - c2

for i in range(n):
    if ans1[i] == 4:
        if r1 > 0:
            ans1[i] = 1
            r1 -= 1
        else:
            ans1[i] = 2

m0 = 1
m1 = 1
m2 = 1

ans = []
for i in range(n):
    if ans1[i] == 0:
        ans.append(3 * m0)
        m0 += 1
    elif ans1[i] == 1:
        ans.append(3 * m1 - 2)
        m1 += 1
    else:
        ans.append(3 * m2 - 1)
        m2 += 1

print(*ans)

Submission status: Wrong Answer

Solution code:
n = int(input())  # n:頂点数　w:辺の数
print([3]*n)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

import random 

def main():
    N = INT()
    lr = random.sample(list(range(1,N+1)), N)
    print(*lr)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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]
    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(0)
            else:
                assign[num] = (ind_1 ) * 3 + 1
                ind_1 += 1
        else:
            if ind_2 == lim_2: #割当が足りなくなったら
                print(-1)
                exit(0)
            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: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    AB = [[] for j in range(N + 1)]

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

    pair = collections.Counter()
    pairset = [set() for j in range(N)]
    for i in range(N):
        S = collections.deque()
        S.append([i + 1, 0])
        v = set()
        v.add(i + 1)
        while S:
            c = S.pop()
            if c[1] == 3:
                pair[min(i, c[0] - 1), max(i, c[0] - 1)] += 1
                pairset[i].add(c[0] - 1)
                pairset[c[0] - 1].add(i)
                continue
            for next in AB[c[0]]:
                if next not in v:
                    v.add(next)
                    S.append([next, c[1] + 1])

    ans = [-1] * N
    icnt = collections.Counter()
    for i in pair.keys():
        icnt[i[0]] += 1
        icnt[i[1]] += 1

    for i, v in enumerate(icnt.most_common()):
        if i >= N // 3:
            break
        ans[v[0]] = 0

    ocnt = 0
    tcnt = 0
    for i in range(N):
        if ans[i] == 0:
            continue

        elif ans[i] == -1:
            of = True
            if ocnt > tcnt:
                of = False

            if of:
                ocnt += 1
                ans[i] = 1
                for j in list(pairset[i]):
                    if ans[j] == -1:
                        ans[j] = 2
                        tcnt += 1
            else:
                tcnt += 1
                ans[i] = 2
                for j in list(pairset[i]):
                    if ans[j] == -1:
                        ans[j] = 1
                        ocnt += 1
        elif ans[i] == 1:
            for j in list(pairset[i]):
                if ans[j] == -1:
                    ans[j] = 2
                    tcnt += 1
        elif ans[i] == 2:
            for j in list(pairset[i]):
                if ans[j] == -1:
                    ans[j] = 1
                    ocnt += 1
    zcnt = 1
    ocnt = 0
    tcnt = 0
    for i in range(N):
        if ans[i] == 0:
            ans[i] += 3 * zcnt
            zcnt += 1
        elif ans[i] == 1:
            ans[i] += 3 * ocnt
            ocnt += 1
        elif ans[i] == 2:
            ans[i] += 3 * tcnt
            tcnt += 1

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
S = list(range(1, n+1))
for i in range(n-1):
  a, b = map(int, input().split())
  S[a-1] = b
  S[b-1] = a
T = map(str, S)
print(''.join(T))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

N = n_in()
edges = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = l_in()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)


# Euler Tour の構築
S = []
depth = [0]*N
visited = set()

def dfs(v, d):
    visited.add(v)
    depth[v] = d
    S.append(v)
    for w in edges[v]:
        if w in visited:
            continue
        dfs(w, d+1)
        S.append(v)
dfs(0, 0)


res = [0 for _ in range(N)]

from collections import deque
q = deque([i for i in range(1,N+1) if i%3 == 0 ] + [i for i in range(1,N+1) if i%3 != 0 ])

if len(list(filter(lambda d: d%2 == 0, depth))) <= N//2:
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q.popleft()
    for i, d in enumerate(depth):
        if d%2 != 0:
            res[i] = q.popleft()
else:
    for i, d in enumerate(depth):
        if d%2 != 0:
            res[i] = q.popleft()
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q.popleft()


print_l(res)

Submission status: Wrong Answer

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

N=int(input())
E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

COLOR=[-1]*(N+1)

Q=[1]
COLOR[1]=1

while Q:
    x=Q.pop()
    for to in E[x]:
        if COLOR[to]==-1:
            COLOR[to]=1-COLOR[x]
            Q.append(to)

A1=N//3
A2=N//3
A3=N//3

if N%3==1:
    A1+=1
elif N%3==2:
    A1+=1
    A2+=1

S1=COLOR.count(1)
S2=COLOR.count(0)

ANS=[0]*(N+1)
now1=1
now2=2
if S1<S2:
    for i in range(1,N+1):
        if COLOR[i]==1:
            ANS[i]=now2
            now2+=3
        else:
            ANS[i]=now1
            now1+=3

else:
    for i in range(1,N+1):
        if COLOR[i]==0:
            ANS[i]=now2
            now2+=3
        else:
            ANS[i]=now1
            now1+=3

now3=3
for i in range(1,N+1):
    if ANS[i]>N:
        ANS[i]=now3
        now3+=3
        
for i in range(1,N+1):
    if ANS[i]>N:
        if now1<N:
            ANS[i]=now1
            now1+=3
        else:
            ANS[i]=now2
            now2+=3

print(*ANS[1:])

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = lr()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)
    pair = [[] for _ in range(N)]
    for i in range(N):
        dist = [-1]*N
        s = [i]
        dist[i] = 0
        while len(s) > 0:
            v = s.pop()
            for j in edges[v]:
                if dist[j] == -1:
                    dist[j] = dist[v]+1
                    if dist[j] == 3:
                        if i < j:
                            pair[i].append(j)
                            pair[j].append(i)
                        continue
                    s.append(j)
    one = N//3+min(1, N%3)
    two = N//3+N%3//2
    thr = N//3
    ans = [1]*N
    for i in range(N):
        if ans[i] == 1:
            for j in pair[i]:
                if two > 0:
                    ans[j] = 3*two-1
                    two -= 1
                elif thr > 0:
                    ans[j] = 3*thr
                    thr -= 1
                else:
                    print('-1')
                    return
        elif ans[i] == 2:
            for j in pair[i]:
                if ans[j] == 2:
                    if thr > 0:
                        ans[j] = 3*thr
                        thr -= 1
                    else:
                        print('-1')
    for i in range(N):
        if one == 0 and two == 0:
            break
        elif ans[i] == 1:
            if two > 0:
                ans[i] = 3*two-1
                two -= 1
            elif thr > 0:
                ans[i] = 3*thr
                thr -= 1
            else:
                ans[i] = 3*one-2
                one -= 1
    print(*ans, sep=' ') 
resolve()

Submission status: Wrong Answer

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

ans = [0] * (N+1)

q = [[1,1]]

while q:
	cp,cd = q.pop(0)
	for np in E[cp]:
		if ans[np] == 0:
			ans[np] = cd*(-1)
			q.append([np,cd*(-1)])

mod0 = 6
mod1 = 1
mod2 = 2

answer = [3]
for i in range(2,N+1):
	if ans[i] == 1:
		if mod1 <= N:
			answer.append(mod1)
			mod1 += 3
		else:
			answer.append(mod0)
			mod0 += 3
	else:
		if mod2 <= N:
			answer.append(mod2)
			mod2 += 3
		else:
			answer.append(mod0)
			mod0 += 3

print(*answer)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

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

grand_sum = [0 for _ in range(n)]
for i in range(n):
	grand_sum[i] = sum([len(adj[x]) for x in adj[i]]) - len(adj[i])

if n <= 3:
	print(*list(range(1, n+1)))
	sys.exit()

ans = [-1 for _ in range(n)]
#ONE, TWO = n//3 + (n%3 > 0), n//3 + (n%3 > 1)

tri = [0 for _ in range(n)]
for a, b in edges:
	tri[b] += grand_sum[a] - len(adj[b]) + 1
	tri[a] += grand_sum[b] - len(adj[a]) + 1
	#print(a, b)
	#print(tri_a, tri_b)
	#print("---")
#print(tri)

#THREE = 3
#for i, t in enumerate(tri):
#	if t >= n - (n//3):
#		if THREE > n:
#			print(-1)
#			sys.exit()
#		ans[i] = THREE
#		THREE += 3

flg = False
orig = -1
for i, t in enumerate(tri):
	if t >= n - (n//3):
		flg = True
		orig = i

#parity = [0, 0]
signs = [-1 for _ in range(n)]
def dfs(x):
	for v in adj[x]:
		if signs[v] < 0:
			signs[v] = 1 ^ signs[x]
			dfs(v)

signs[0] = 0
dfs(0)

if flg:
	cur = [1, 2, 3]
	for i in range(n):
		if signs[i] == signs[orig]:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] <= n:
			ans[i] = cur[0]
			cur[0] += 3
		else:
			ans[i] = cur[1]
			cur[1] += 3
	print(*ans)
	sys.exit()

num1 = sum(signs)
num2 = n - num1

#print(signs)

M, m = max(num1, num2), min(num1, num2) 
#if max(num1, num2) > n - (n // 3):
#	print(-1)
#	sys.exit()
#else:
if num1 > num2:
	one, two = num1, num2
	more = 1
else:
	one, two = num2, num1
	more = 0
cur = [2, 1, 3]
for i in range(n):
	if ans[i] > 0:
		continue
	if signs[i] == more:
		if cur[1] > n and cur[2] <= n: 
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[1] > n and cur[2] > n:
			ans[i] = cur[0]
			cur[0] += 3
		else:
			ans[i] = cur[1]
			cur[1] += 3
	else:
		if cur[0] > n and cur[2] <= n:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] > n and cur[2] > n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[0]
			cur[0] += 3
print(*ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
v=[0]*N
x=[0]*N
for i,j in AB:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
import sys
sys.setrecursionlimit(10**9)
def dfs(p):
    y=1 if x[p]==2 else 2
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            x[n]=y
            dfs(n)
v[0]=x[0]=1
dfs(0)
p,q,r=0,0,1
for i in range(N):
    if x[i]==1 and p*3+1<=N:
        x[i]=p*3+1
        p+=1
    elif x[i]==2 and q*3+2<=N:
        x[i]=q*3+2
        q+=1
    else:
        x[i]=r*3
        r+=1
print(*x)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import math

def dijkstra(s,n,w,cost):
    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

def main():
    n = int(input())
    num_list = []
    cost = [[float("inf") for i in range(n)] for i in range(n)] 
    for _ in range(n-1):
        x, y = map(int, input().split())
        num_list.append([x, y])
        cost[x-1][y-1] = 1
        cost[y-1][x-1] = 1

    tmp_list = []
    is_find = False

    for i in range(n):
        if is_find:
            break
        dist_list = dijkstra(i,n,n-1,cost)
        for j in range(n):
            if math.ceil(dist_list[j]) == 3:
                tmp_list.append(j+1)
                is_find = True

    ans_list = [0] * n

    ans_list[i-1] = i

    for i in tmp_list:
        ans_list[i-1] = 3

    for i in range(n):
        if i == n-1:
            print(ans_list[i])
            break
        print(ans_list[i],end=' ')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    A,B = list(map(int,input().split()))
    G[A-1].append((B-1,1))
    G[B-1].append((A-1,1))

from collections import deque
def bfs(s):
    dist = [None]*N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w, c in G[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + c
            que.append(w)
    d = max(dist)
    return dist.index(d), d, dist
F1, _, _ = bfs(0)
_, _, dist1 = bfs(F1)
L = [[] for i in range(N)]
out = [100]*N
for i in range(N):
    L[dist1[i]].append(i)

K = [1,2,0,2,1,0]
u=0
ui=u%6
for t in range(len(L)):
    s=0
    LN = len(L[t])
    while LN>s:
        out[L[t][s]] = K[ui]
        s+=1
    u+=1
    ui=u%6
s1 = 0
s2 = 0
s3 = 0
for i in range(N):
    if out[i]==0:
        out[i]=3*s1
        s1+=1
    if out[i]==1:
        out[i]=3*s2+1
        s2+=1
    if out[i]==2:
        out[i]=3*s3+2
        s3+=1
    if out[i]>N:
        out[i]+=-2
print(' '.join(map(str, out)))