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:
# 閉路はない
n = int(input())

from collections import deque
d1 = [deque([]) for _ in range(n)]
d2 = [deque([]) for _ in range(n)]
d3 = [deque([]) for _ in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    d1[a].append(b)
    d1[b].append(a)

# 距離2を作る
for i in range(n):
    for j in range(len(d1[i])):
        # その距離1のエッジ
        en = d1[i][j]
        for k in range(len(d1[en])):
            # 距離2 の エッジ
            d2e = d1[en][k]
            # 自分自身ではなく、自分のテーブルにないなら
            if d2e != i and d2e not in d1[i]:
                if d2e not in d2[i]:
                    d2[i].append(d2e)
                if i not in d2[d2e]:
                    d2[d2e].append(i)
#print(d2)

# 距離3を作る
for i in range(n):
    for j in range(len(d2[i])):
        # その距離2のエッジ
        en = d2[i][j]
        for k in range(len(d1[en])):
            # 距離2 の エッジの距離1のエッジ = 3 候補
            d3e = d1[en][k]
            # 自分自身ではなく、自分のテーブルにないなら
            if d3e != i and d3e not in d1[i] and d3e not in d2[i]:
                if d3e not in d3[i]:
                    d3[i].append(d3e)
                if i not in d3[d3e]:
                    d3[d3e].append(i)
#print(d3)
count = []
m0can = deque([])
m1can = deque([])
m2can = deque([])
for i in range(n):
    count.append( (len(d3[i]), i) )
    if (i+1) % 3 == 0:
        m0can.append(i+1)
    elif (i+1) % 3 == 1:
        m1can.append(i+1)
    elif (i+1) % 3 == 2:
        m2can.append(i+1)

count.sort(reverse=True)
count = deque(count)
#print(count)

res = [-1] * n
usedmax = n + 1 # 掛け算の捨てよう
used = [False] * (n+1)
while(len(m0can) > 0):
    if len(count) != 0:
        e = count.popleft()
        nv = m0can.popleft()
        res[e[1]] = nv
        used[nv] = True

mode = 1

canComplete = True
for i in range(n):
    #print("loop", i)
    if res[i] != -1: # 決定しているなら
        continue
    l3 = len(d3[i])
    if l3== 0: # 何でもいい子は後回し
        #print("this node not needs", i)
        continue
    enforce = -1
    for j in range(l3):
        #print("search enf" ,j , res[d3[i][j]] )
        if res[d3[i][j]] == -1: # 未使用なら関係ない
            #print("nous")
            continue
        elif enforce == -1: # まだ色の指定がないならその色で
            #print("deside")
            enforce = res[d3[i][j]] % 3
        elif enforce != res[d3[i][j]] % 3:
            canComplete = False
            break
    #print("this must enforce", enforce)
    if enforce == 0: # mod0の希望なら何でもいいので今の色
        if mode == 1 and len(m1can) != 0:
            nv = m1can.popleft()
            res[i] = nv
            used[nv] = True
            mode = 2
        elif len(m2can) != 0:
            nv = m2can.popleft()
            res[i] = nv
            used[nv] = True
            mode = 1
        else: # m3を指定してもいいか？
            canComplete = False
            break
    elif enforce == 1: # mod1が来ているならmod2ないといけない
        if len(m2can) != 0:
            nv = m2can.popleft()
            res[i] = nv
            used[nv] = True
            mode = 1
    elif enforce == 2: # mod1が来ているならmod2ないといけない
        if len(m1can) != 0:
            nv = m1can.popleft()
            res[i] = nv
            used[nv] = True
            mode = 2
    elif enforce == -1: # 希望なし
        #print("enf-1")
        if mode == 1 and len(m1can) != 0:
            nv = m1can.popleft()
            res[i] = nv
            used[nv] = True
            mode = 2
        elif mode == 2 and len(m2can) != 0:
            nv = m2can.popleft()
            res[i] = nv
            used[nv] = True
            mode = 1

candidate = 1
"""
print(res)
print(used)
print(m0can)
print(m1can)
print(m2can)
"""
for i in range(n):
    if res[i] == -1:
        while used[candidate] is True:
            candidate += 1
        res[i] = candidate
        used[candidate] = True

if canComplete is False or n==1 or n==2 or n==3:
    print(-1)
else:
    print(" ".join(list(map(str, res))))

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()

print("-1")

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def bfs(n,g):
    dis = [-1 for _ in range(n)]
    que = deque([])
    que.append(0)
    dis[0] = 0
    cnt_odd = 0
    cnt_even = 1
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] != -1:
                continue
            dis[g[go][i]] = dis[go] + 1
            if dis[g[go][i]]%2 == 0:
                cnt_even += 1
            else:
                cnt_odd += 1
            que.append(g[go][i])
    return dis,cnt_odd,cnt_even

def length3(s,n,g):
    global que_1,que_2,ans
    dis = [-1 for _ in range(n)]
    see = []
    que = deque([])
    que.append(s)
    dis[s] = 0
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] != -1:
                continue
            dis[g[go][i]] = dis[go] + 1
            if dis[g[go][i]] < 3:
                que.append(g[go][i])
            elif dis[g[go][i]] == 3:
                see.append(g[go][i])
    check1 = 0
    check2 = 0
    for e in see:
        if ans[e] == 0:
            continue
        if ans[e]%3 == 1:
            check1 += 1
        if ans[e]%3 == 2:
            check2 += 1
    if check1>0 and check2>0:
        print(-1)
        exit()
    if check1>0:
        if que_2:
            ans[s] = que_2.pop()
        else:
            print(-1)
            exit()
        for e in see:
            if ans[e] == 0:
                if que_1:
                    ans[e] = que_1.pop()
                else:
                    print(-1)
                    exit()
    elif check2>0:
        if que_1:
            ans[s] = que_1.pop()
        else:
            print(-1)
            exit()
        for e in see:
            if ans[e] == 0:
                if que_2:
                    ans[e] = que_2.pop()
                else:
                    print(-1)
                    exit()
    else:
        if len(que_1) > len(que_2):
            if que_2:
                ans[s] = que_2.pop()
            else:
                print(-1)
                exit()
            for e in see:
                if ans[e] == 0:
                    if que_1:
                        ans[e] = que_1.pop()
                    else:
                        print(-1)
                        exit()
        else:
            if que_1:
                ans[s] = que_1.pop()
            else:
                print(-1)
                exit()
            for e in see:
                if ans[e] == 0:
                    if que_2:
                        ans[e] = que_2.pop()
                    else:
                        print(-1)
                        exit()
    return

def main():
    n = inp()
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        a,b = inpm()
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    dis,cnt_odd,cnt_even = bfs(n,g)
    global que_1,que_2,ans
    ans = [0 for _ in range(n)]
    if min(cnt_even,cnt_odd) <= n//3:
        check = [1 for _ in range(n)]
        x = 1
        if cnt_even <= cnt_odd:
            for i in range(n):
                if dis[i]%2 == 0:
                    ans[i] = 3*x
                    check[3*x-1] = 0
                    x += 1
            x = 0
            for i in range(n):
                if ans[i] == 0:
                    while not check[x]:
                        x += 1
                    ans[i] = x + 1
                    x += 1
            print(*ans)
        elif cnt_even >= cnt_odd:
            for i in range(n):
                if dis[i]%2 == 1:
                    ans[i] = 3*x
                    check[3*x-1] = 0
                    x += 1
            x = 0
            for i in range(n):
                if ans[i] == 0:
                    while not check[x]:
                        x += 1
                    ans[i] = x + 1
                    x += 1
            print(*ans)
        return
    check = [1 for _ in range(n)]
    x = 1
    if cnt_even <= cnt_odd:
        remain = []
        for i in range(n):
            if dis[i]%2 == 0:
                if x*3 <= n:
                    ans[i] = 3*x
                    check[3*x-1] = 0
                    x += 1
                else:
                    remain.append(i)
        que_1 = deque()
        que_2 = deque()
        for i in range(n):
            if (i+1)%3 == 1:
                que_1.append(i+1)
            elif (i+1)%3 == 2:
                que_2.append(i+1)
        for e in remain:
            length3(e,n,g)
        for i in range(n):
            if ans[i] == 0:
                if que_1:
                    ans[i] = que_1.pop()
                else:
                    ans[i] = que_2.pop()
        print(*ans)
    else:
        remain = []
        for i in range(n):
            if dis[i]%2 == 1:
                if x*3 <= n:
                    ans[i] = 3*x
                    check[3*x-1] = 0
                    x += 1
                else:
                    remain.append(i)
        que_1 = deque()
        que_2 = deque()
        for i in range(n):
            if (i+1)%3 == 1:
                que_1.append(i+1)
            elif (i+1)%3 == 2:
                que_2.append(i+1)
        for e in remain:
            length3(e,n,g)
        for i in range(n):
            if ans[i] == 0:
                if que_1:
                    ans[i] = que_1.pop()
                else:
                    ans[i] = que_2.pop()
        print(*ans)
        
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(250000)
l=[None]*N
g=[1,0]
def hu(n,c):
    for i in s[n]:
        if l[i]==None:
            l[i]=c
            g[c%2]+=1
            hu(i,c+1)
l[0]=0
hu(0,1)
a=[1,2,3]
if min(g)>N//3:
    b,c=0,1
    for i in l:
        if i%2:
            print(a[b],end=" ")
            a[b]+=3    
            if a[b]>N:
                b=2
        else:
            print(a[c],end=" ")
            a[c]+=3
            if a[c]>N:
                c=2
else:
    if g[0]<g[1]:
        b,c=2,0
        for i in l:
            if i%2:
                print(a[b],end=" ")
                a[b]+=3
                if a[b]>N:
                    if b==0:
                        b=1
                    else:
                        b=2
            else:
                print(a[c],end=" ")
                a[c]+=3
    else:
        b,c=0,2
        for i in l:
            if not i%2:
                print(a[b],end=" ")
                a[b]+=3
                if a[b]>N:
                    if b==0:
                        b=1
                    else:
                        b=2
            else:
                print(a[c],end=" ")
                a[c]+=3

Submission status: Wrong Answer

Solution code:
def BFS(qu, D, firstqu, searchList):
    if D <= 3:
        for i in range(0, len(CountList[qu])):
            if CountList[qu][i] not in searchList:
                searchList.append(CountList[qu][i])
                BFS(CountList[qu][i], D + 1, firstqu, searchList)
    else:
        ResultList[firstqu].append(qu)


N = int(input())

ABList = []
CountList = [[] for i in range(N)]
ResultList = [[] for i in range(N)]

OutPut = []

for i in range(N - 1):
    A, B = map(int, input().split())
    ABList.append([A - 1, B - 1])
    CountList[A - 1].append(B - 1)
    CountList[B - 1].append(A - 1)
ABList.sort()


for i in range(N):
    emptyList = [i]
    BFS(i, 1, i, emptyList)

for i in range(N):
    if len(ResultList[i]) == 0:
        OutPut.append(1)
    else:
        OutPut.append(3)
    print(OutPut[i], end=' ')

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    from heapq import heappush, heappop
    import sys
    input = sys.stdin.readline

    N = int(input())

    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)

    def bfs3(s):
        dq = deque()
        dq.append(s)
        dist = [-1] * N
        dist[s] = 0

        dist3 = set()
        while dq:
            v = dq.popleft()
            d = dist[v]
            for u in graph[v]:
                if ~dist[u]: continue
                dist[u] = d + 1
                if d == 2:
                    dist3.add(u)
                else:
                    dq.append(u)

        return dist3

    # solve
    dist3s = []
    h = []
    deg = [0] * N
    for v in range(N):
        res = bfs3(v)
        dist3s.append(res)
        d_ = len(res)
        deg[v] = d_
        if d_:
            heappush(h, (-d_, v))

    ret = [-1] * N
    need_update = [0] * N
    need = [-1] * N

    m3 = 3
    m2 = 2
    m1 = 1
    while h:
        d, v = heappop(h)
        if need_update[v]:
            heappush(h, (-deg[v], v))
            need_update[v] = 0
            continue

        if need[v] == 0:
            if m1 // 3 < m2 // 3:
                if m1 > N:
                    print(-1)
                    return

                ret[v] = m1
                m1 += 3
                for u in dist3s[v]:
                    deg[u] -= 1
                    need_update[u] = 1
                    need[u] = 2  # 2


            else:
                if m2 > N:
                    print(-1)
                    return

                ret[v] = m2
                m2 += 3
                for u in dist3s[v]:
                    deg[u] -= 1
                    need_update[u] = 1
                    need[u] = 1  # 1

        elif need[v] == 2:
            if m2 > N:
                print(-1)
                return

            ret[v] = m2
            m2 += 3
            for u in dist3s[v]:
                deg[u] -= 1
                need_update[u] = 1
                need[u] = 1  # 1

        elif need[v] == 1:
            if m1 > N:
                print(-1)
                return

            ret[v] = m1
            m1 += 3
            for u in dist3s[v]:
                deg[u] -= 1
                need_update[u] = 1
                need[u] = 2  # 2

        else:
            if m3 <= N:
                ret[v] = m3
                m3 += 3
                for u in dist3s[v]:
                    deg[u] -= 1
                    need_update[u] = 1
                    need[u] = 0  # なんでも
            else:
                if m1 // 3 < m2 // 3:
                    if m1 > N:
                        print(-1)
                        return

                    ret[v] = m1
                    m1 += 3
                    for u in dist3s[v]:
                        deg[u] -= 1
                        need_update[u] = 1
                        need[u] = 2  # 2

                else:
                    if m2 > N:
                        print(-1)
                        return

                    ret[v] = m2
                    m2 += 3
                    for u in dist3s[v]:
                        deg[u] -= 1
                        need_update[u] = 1
                        need[u] = 1  # 1

    for v in range(N):
        if ret[v] == -1:
            if m1 <= N:
                ret[v] = m1
                m1 += 3
            elif m2 <= N:
                ret[v] = m2
                m2 += 3
            elif m3 <= N:
                ret[v] = m3
                m3 += 3
            else:
                print(-1)
                return

    print(*ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

Solution code:
import math
import itertools
N = int(input())
array=[]
for i in range(0, N-1):
    array.append(input().split())
dist3=[]
for row in array:
    a,b=row
    c = []
    d=[]
    for tmpc1,tmpc2 in array:
        if tmpc1 == a and tmpc2 != a and tmpc2!=b:
            c.append(int(tmpc2)-1)
        if tmpc1 != a and tmpc2 == a and tmpc1 != b:
            c.append(int(tmpc1)-1)
    for tmpd1,tmpd2 in array:
        if tmpd1 == b and tmpd2!=a and tmpd2 != b and tmpd2!=c:
            d.append(int(tmpd2)-1)
        if tmpd1 != b and tmpd1!=a and tmpd2 == b and tmpd1!=c:
            d.append(int(tmpd1)-1)
    if c != [] and d != []:
        #print("{} {} {} {}".format(a, b, c, d))
        dist3.append([c, d])
        
for kouho in itertools.permutations(list(range(1,N+1)),N):
    breakflag=False
    for c, d in dist3:
        for tmpc in c:
            for tmpd in d:
                if (kouho[tmpc] + kouho[tmpd]) % 3 != 0 and (kouho[tmpc] * kouho[tmpd]) % 3 != 0:
                    breakflag = True
                    break
                #else:
                    #print("{} {} {} {}".format( tmpc, tmpd,kouho[tmpc],kouho[tmpd]))
            if breakflag==True:
                break
        if breakflag!=True:
            print(kouho)
            exit()

print('-1')

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
import sys
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)
  
def dfs(N):
  ans=defaultdict(list)
  for i in range(1,N+1):
    s=i
    stack=[]
    stack.append(s)
    seen=[]
    seen.append(s)
    prev=defaultdict(list)
    while len(stack)!=0:
      u=stack.pop()
      if u!=s and prev[u][1]==3:
        if u in ans[s] or s in ans[u]:
          pass
        else:
          s,u=min(s,u),max(s,u)
          ans[s].append(u)
      elif u!=s and prev[u][1]>3:
        pass
      else:
        if u==s:
          for v in G[u]:
            if v not in seen:
              seen.append(v)
              stack.append(v)
              prev[v]=[u,1]
        else:
          for v in G[u]:
            if v not in seen:
              seen.append(v)
              stack.append(v)
              prev[v]=[u,prev[u][1]+1]
  return ans

three=dfs(N)
 
init=1
P=[str(i) for i in range(1,N+1)]

if len(three.keys())==0:
  print(' '.join(P))
  sys.exit()
  
for i in three.keys():
  for j in three[i]:
    if (i+j)%3==0 or (i*j)%3==0:
      pass
    else:
      if 3*init>N:
        print(-1)
        sys.exit()
      P[j-1]=str(3*init)
      P[3*init-1]=str(j)
      init+=1
print(' '.join(P))

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [[] for i in range(n)]
m1 = 0
m2 = 0
m3 = 0
ans = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)

sizes = [[i,len(edge[i])] for i in range(n)]
sizes.sort(key=lambda x:x[1])


visited = set([sizes[0][0]])
to_search = [sizes[0][0]]
mod_mode = 1
while True:
    temp = []
    for v in to_search:
        if mod_mode == 1:
            if m1*3+1 <= n:
                ans[v] = m1*3+1
                m1 += 1
            else:
                ans[v] = m3*3+3
                m3 += 1
        else:
            if m2*3+2 <= n:
                ans[v] = m2*3+2
                m2 += 1
            else:
                ans[v] = m3*3+3
                m3 += 1
        nex = edge[v]
        for vv in nex:
            if vv not in visited:
                temp.append(vv)
                visited.add(vv)
    if len(temp) == 0:
        break
    to_search = temp

    mod_mode *= -1

for i in range(n-1):
    print(ans[i],end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
n = int(readline())

graph = [[] for _ in range(n+1)] #隣接リスト
for i in range(n-1):
    a,b = map(int,readline().split())
    graph[a].append(b)
    graph[b].append(a)
 
#親のノードに子を入れてくdfs
AB = []
def bfs(i): #長さ3までi=3まで
    queue = deque([[i,0]])
    visited = []
    while queue:
        x,l = queue.popleft()
        if l < 3:
            for j in graph[x]:
                if not j in visited:
                    queue.append([j,l+1])
            visited.append(x)
        else:
            if i < x:
                AB.append([i,x])
            visited.append(x)
for i in range(1,n+1):
    bfs(i)
graph = [[] for _ in range(n+1)] #隣接リスト
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

#親のノードに子を入れてくdfs
if len(AB) == 0:
    print(*[i for i in range(1,n+1)])
    exit()
stack = [AB[0][0]] #グラフに組み込まれた適当な値を入れる
parent = [0]*(n+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in graph[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)

ans = [0]*(n+1)

t0 = [i*3 for i in range(1,n//2)]
t1 = [1+i*3 for i in range(0,n//2)]
t2 = [2+i*3 for i in range(0,n//2)]
l0,l1,l2 = len(t0),len(t1),len(t2)
k0,k1,k2 = 0,0,0
for x in order: #親
    if parent[x] == 0:
        ans[x] = t1[k1]
        k1 += 1
    else:
        if ans[parent[x]]%3 == 0: #ans[parent[x]] != 0 and ←決まってる？
            if k1 < l1:
                ans[x] = t1[k1]
                k1 += 1
            elif k2 < l2:
                ans[x] = t2[k2]
                k2 += 1
            elif k0 < l0:
                ans[x] = t0[k0]
                k0 += 1
            else:
                print(-1)
                exit()
        elif ans[parent[x]]%3 == 1:
            if k2 < l2:
                ans[x] = t2[k2]
                k2 += 1
            elif k0 < l0:
                ans[x] = t0[k0]
                k0 += 1
            else:
                print(-1)
                exit()
        else:
            if k1 < l1:
                ans[x] = t1[k1]
                k1 += 1
            elif k0 < l0:
                ans[x] = t0[k0]
                k0 += 1
            else:
                print(-1)
                exit()

for x in range(1,n+1):
    if ans[x] == 0:
        if k1 < l1:
            ans[x] = t1[k1]
            k1 += 1
        elif k2 < l2:
            ans[x] = t2[k2]
            k2 += 1
        elif k0 < l0:
            ans[x] = t0[k0]
            k0 += 1
        else:
            print(-1)
            exit()
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
n=int(input())
ans=[0]*n
three=n//3
two=(n-three)//2
one=n-three-two
t=[[]for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  t[a].append(b)
  t[b].append(a)
th=[]
Q=[0]
visited={0}
ma=0
thi=-1
while Q:
  th.append(Q)
  if len(Q)>ma:
    ma=len(Q)
    thi=len(th)-1
  P=[]
  for j in Q:
    for i in t[j]:
      if i not in visited:
        P.append(i)
        visited.add(i)
  Q=P
odd=even=0
for i in range(len(th)):
  if i%2==1:odd+=len(th[i])
  else:even+=len(th[i])
if odd>one+three:
  flag="error"
  d=0
elif even>one+three:
  flag="error"
  d=1
else:
  flag="normal"

if flag=="error":
  sudenideta=set()
  num=3
  for i in range(d,len(th),2):
    for j in th[i]:
      ans[j]=num
      sudenideta.add(num)
      num+=3
  num=1
  for i in range(d^1,len(th),2):
    for j in th[i]:
      while num in sudenideta:num+=1
      ans[j]=num
      sudenideta.add(num)
      num+=1
else:
  odd_num=1
  even_num=2
  three_num=3
  for i in range(len(th)):
    for j in th[i]:
      if i%2==1:
        if odd_num>n:
          ans[j]=three_num
          three_num+=3
        else:
          ans[j]=odd_num
          odd_num+=3
      else:
        if even_num>n:
          ans[j]=three_num
          three_num+=3
        else:
          ans[j]=even_num
          even_num+=3
print(*ans)

Submission status: Wrong Answer

Solution code:
import queue
import sys
sys.setrecursionlimit(10 ** 7)

def make_tree_2(graph, x, n):
    st = [[None]*2 for _ in range(n)]
    l = 1
    s[0] = x
    tree = [[] for _ in range(n)]
    while 0 < l:
        print("A")


def make_tree(graph, x, pre_lst, tree):
    if pre_lst[2] != -1:
        tree[x].append(pre_lst[2])
        tree[pre_lst[2]].append(x)
    for nex in graph[x]:
        if nex == pre_lst[0]:
            continue
        tree = make_tree(graph, nex, [x, pre_lst[0], pre_lst[1]], tree)
    return tree

def solve(tree, n):
    lst_0 = [i for i in range(3, n+1, 3)]
    lst_1 = [i for i in range(1, n+1, 3)]
    lst_2 = [i for i in range(2, n+1, 3)]
    cnt_0, cnt_1, cnt_2 = 0, 0, 0
    f = [True]*n
    ans = [None]*n
    for i in range(n):
        if f[i] and len(tree[i]) <= 1:
            q = queue.Queue()
            q.put(i)
            f[i] = False
            if cnt_2 < len(lst_2):
                ans[i] = lst_2[cnt_2]
                cnt_2 += 1
            elif cnt_1 < len(lst_1):
                ans[i] = lst_1[cnt_1]
                cnt_1 += 1
            elif cnt_0 < len(lst_0):
                ans[i] = lst_0[cnt_0]
                cnt_0 += 1
            while not q.empty():
                target = q.get()
                for v in tree[target]:
                    if f[v]:
                        f[v] = False
                        if ans[target] % 3 == 2 and cnt_1 < len(lst_1):
                            ans[v] = lst_1[cnt_1]
                            cnt_1 += 1
                            q.put(v)
                        elif ans[target] % 3 == 1 and cnt_2 < len(lst_2):
                            ans[v] = lst_2[cnt_2]
                            cnt_2 += 1
                            q.put(v)
                        elif ans[target] % 3 == 0:
                            if cnt_2 < len(lst_2):
                                ans[v] = lst_2[cnt_2]
                                cnt_2 += 1
                                q.put(v)
                            elif cnt_1 < len(lst_1):
                                ans[v] = lst_1[cnt_1]
                                cnt_1 += 1
                                q.put(v)
                            else:
                                ans[v] = lst_0[cnt_0]
                                cnt_0 += 1
                                q.put(v)
                        elif cnt_0 < len(lst_0):
                            ans[v] = lst_0[cnt_0]
                            cnt_0 += 1
                            q.put(v)
                        else:
                            print("-1")
                            sys.exit()
    for v in ans:
        print(v, end=" ")

def main():
    n = int(input())
    tree = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[b].append(a)
        tree[a].append(b)
    top = -1
    for i in range(n):
        if len(tree[i]) == 1:
            top = i
            break
    new_tree = [[] for _ in range(n)]
    for v in tree[top]:
        new_tree = make_tree(tree, v, [top, -1, -1], new_tree)
    solve(new_tree, n)

if __name__ == "__main__":
    main()

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
        break
ans=[3]*n
if check:
    print(ans)
else:
    print('-1')