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

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

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

# print(pair)

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))
        
    Safe = [True] * N
    Ans = [-1] * N
    Check = False
    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
            if Check:
                f = Par[nowNode]
                g = Par[f]
                if not Safe[g]:
                    print(-1)
                    break
                else:
                    possible = True
                    for u in Son[g]:
                        if u != f and not Safe[u]:
                            possible = False
                            break
                    if not possible:
                        print(-1)
                        break

        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) + 1] + (dType ^ 1) + 1
                modIndex[(dType ^ 1) + 1] += 1
                Safe[nowNode] = False
                Check = True
            else:
                f = Par[nowNode]
                g = Par[f]
                print(f, g)
                if not Safe[g]:
                    print(-1)
                    break
                else:
                    possible = True
                    for u in Son[g]:
                        if u != f and not Safe[u]:
                            possible = False
                            break
                    if possible:
                        Ans[nowNode] = 3 * modIndex[(dType ^ 1) + 1] + (dType ^ 1) + 1
                        modIndex[(dType ^ 1) + 1] += 1
                        Safe[nowNode] = False
                        Check = True
                    else:
                        print(-1)
                        break
    else:
        print(" ".join(map(str, Ans)))


    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d = [i % 2+1 for i in d]
    d2 = [0]*n
    j = 1
    for i in range(n):
        if d[i] == 1:
            d2[i] = j
            j += 3
    j = 2
    for i in range(n):
        if d[i] == 2:
            d2[i] = j
            j += 3
    j = 3
    for i in range(n):
        if d2[i] > n:
            d2[i] = j
            j += 3
    print(*d2)


main()

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
if r1 < 0 or r2 < 0:
    print(-1)

else:
    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:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
L = [-1]*n
dist = [-1]*n
dist[0] = 0
F_1 = [i for i in range(1, n+1) if i%3==1]
F_2 = [i for i in range(1, n+1) if i%3==2]
F_0 = [i for i in range(1, n+1) if i%3==0]
def dfs(v):
  for nv in T[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v] + 1
      dfs(nv)
dfs(0)
K = sorted([(j, i) for i, j in enumerate(dist)], reverse=True)
for d, num in K:
  if F_1:
    L[num] = F_1.pop()
  elif F_2:
    L[num] = F_2.pop()
  else:
    L[num] = F_0.pop()
print(*L)

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)
bp = [0] * N
for i, v in enumerate(vs):
    bp[v] = i & 1

ansmod = [-1] * N
if bp.count(0) <= counts[0]:
    # 3を割り当てる
    for v, b in enumerate(bp):
        if b == 0 and counts[0] > 0:
            ansmod[v] = 0
            counts[0] -= 1
elif bp.count(1) <= counts[0]:
    # 3を割り当てる
    for v, b in enumerate(bp):
        if b == 0 and counts[0] > 0:
            ansmod[v] = 0
            counts[0] -= 1
else:
    # 違う方に違うのを割り当てる
    for v, b in enumerate(bp):
        if b == 0 and counts[1] > 0:
            ansmod[v] = 1
            counts[1] -= 1
        if b == 1 and counts[2] > 0:
            ansmod[v] = 2
            counts[2] -= 1
# 残りに余ってるのを割り当てる
for v in range(N):
    if ansmod[v] < 0:
        for i in range(3):
            if counts[i] > 0:
                ansmod[v] = i
                counts[i] -= 1
                break

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5+1)

def cur(p):
    for i in x[p]:
        if rank[i]==-1:
            rank[i]=rank[p]+1
            par[i]=p
            cur(i)


n=int(input())
x=[[] for i in range(n)]

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

rank=[-1 for i in range(n)]
rank[0]=0
par=[-1 for i in range(n)]

cur(0)
M=max(rank)
x=[[] for i in range(M+1)]

q=[0,0]
r=[n//3,n//3,n//3]
if n%3>0: r[1]+=1
if n%3>1: r[2]+=1
tmp1,tmp2,tmp3=1,2,3

for i in range(n):
    q[rank[i]%2]+=1
    x[rank[i]].append(i)
ans=[-1 for i in range(n)]


if q[0]>r[0]+r[1] or q[1]>r[0]+r[2]:
    if q[0]>r[0]+r[2] or q[1]>r[0]+r[1]:
        tmp1,tmp2=2,1


for i in range(M+1):
    if i%2==0:
        for p in x[i]:
            if tmp1<=n:
                ans[p]=tmp1
                tmp1+=3
            elif tmp3<=n:
                ans[p]=tmp3
                tmp3+=3
            else:
                ans[p]=tmp2
                tmp2+=3
    else:
        for p in x[i]:
            if tmp2<=n:
                ans[p]=tmp2
                tmp2+=3
            elif tmp3<=n:
                ans[p]=tmp3
                tmp3+=3
            else:
                ans[p]=tmp1
                tmp1+=3


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

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict

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

pa = defaultdict(int)
pa[-1] = -1
pa[0] = -1
que = deque([(-1,0)])
while que:
    pre,now = que.popleft()
    for child in G[now]:
        if child == pre:continue
        pa[child] = now
        que.append((now,child))

Graph = [[] for _ in range(n)]
for i in range(n):
    if pa[pa[i]] != -1:
        for j in G[pa[pa[i]]]:
            if j == pa[i]:continue
            Graph[i].append(j)
            Graph[j].append(i)
#print(G)
ans = [-1 for i in range(n)]
num = [[len(Graph[i]),i] for i in range(n)]
num.sort(reverse=True)
#print(num)
i = 1
while 3*i <= n:
    ans[num[i-1][1]] = 3*i
    i += 1

use = [1, 2]
for i in range(n):
    #print(ans)
    if ans[i] != -1: continue
    queue = deque([])
    if use[0] + 1 <= max(use[1], n):
        ans[i] = use[0]
        use[0] += 3
        queue.append((i,1))
    elif use[1] <= max(use[0] + 1, n):
        ans[i] = use[1]
        use[1] += 3
        queue.append((i,2))
    while queue:
        now,num = queue.popleft()
        for to in Graph[now]:
            if ans[to] != -1:continue
            if num == 1:
                if use[1] > n:
                    print(-1)
                    exit()
                ans[to] = use[1]
                use[1] += 3
                queue.append((to,2))
            else:
                if use[0] > n:
                    print(-1)
                    exit()
                ans[to] = use[0]
                use[0] += 3
                queue.append((to,1))

print(*ans)

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(' '.join(map(str,kouho)))
            exit()

print('-1')

Submission status: Wrong Answer

Solution code:
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

    if n >= 7:
        ans_list = [7] * n
    else:
        ans_list = [n] * 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:
import sys
sys.setrecursionlimit(10**5+1)

def cur(p):
    for i in x[p]:
        if rank[i]==-1:
            rank[i]=rank[p]+1
            par[i]=p
            cur(i)


n=int(input())
x=[[] for i in range(n)]

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

rank=[-1 for i in range(n)]
rank[0]=0
par=[-1 for i in range(n)]

cur(0)
M=max(rank)
x=[[] for i in range(M+1)]

q=[0,0]
r=[n//3,n//3,n//3]
if n%3>0: r[1]+=1
if n%3>1: r[2]+=1
tmp1,tmp2,tmp3=1,2,3

for i in range(n):
    q[rank[i]%2]+=1
    x[rank[i]].append(i)
ans=[-1 for i in range(n)]


if q[0]>r[0]+r[1] or q[1]>r[0]+r[2]:
    if q[0]>r[0]+r[2] or q[1]>r[0]+r[1]:
        tmp1,tmp2=2,1


for i in range(M+1):
    if i%2==0:
        for p in x[i]:
            if tmp1<=n:
                ans[p]=tmp1
                tmp1+=3
            elif tmp3<=n:
                ans[p]=tmp3
                tmp3+=3
            else:
                ans[p]=tmp2
                tmp2+=3
    else:
        for p in x[i]:
            if tmp2<=n:
                ans[p]=tmp2
                tmp2+=3
            elif tmp3<=n:
                ans[p]=tmp3
                tmp3+=2
            else:
                ans[p]=tmp1
                tmp1+=3


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

Submission status: Wrong Answer

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


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) and cnt_1 < len(lst_1):
                if len(lst_2) - cnt_2 < len(lst_1) - cnt_1:
                    ans[i] = lst_1[cnt_1]
                    cnt_1 += 1
                else:
                    ans[i] = lst_2[cnt_2]
                    cnt_2 += 1
            elif 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:
import sys


def main():
    input = sys.stdin.readline
    N = int(input())
    G = [set() for i in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].add(b)
        G[b].add(a)

    # 距離3の点を調べていく
    s = [set() for i in range(N)]
    import collections
    q = collections.deque()
    for i in range(N):
        r = [True]*N
        r[i] = False
        q.append((i, 0))
        while(q):
            x, c = q.popleft()
            if c == 3:
                s[i].add(x)
                continue
            for y in G[x]:
                if r[y]:
                    q.append((y, c+1))
                    r[y] = False

    ans = [0]*N
    k = [N//3]*3
    for i in range(N % 3):
        k[i] += 1
    r = set()
    #t = set([i+1 for i in range(N)])
    #s.sort(key=lambda x: len(x[1]))
    #q = collections.deque(s)

    for i in range(N):
        s[i] -= r
        for x in s[i]:
            tmp = s[x] & s[i]
            for y in tmp:
                if ans[y] != 0:
                    continue
                if k[2] > 0:
                    ans[y] = k[2] * 3
                    k[2] -= 1
                    r.add()
                    s[i].remove(y)
                else:
                    print(-1)
                    exit(0)
    for i in range(N):
        if ans[i] == 0:
            if k[0] > 0:
                ans[i] = k[0]*3 - 2
                k[0] -= 1
                for x in s[i]:
                    if ans[x] != 0:
                        continue
                    if k[1] > 0:
                        ans[x] = k[1]*3 - 1
                        k[1] -= 1
                    else:
                        ans[x] = k[2]*3
                        k[2] -= 1
            elif k[1] > 0:
                ans[i] = k[0]*3 - 1
                k[1] -= 1
                for x in s[i]:
                    if ans[x] != 0:
                        continue
                    if k[0] > 0:
                        ans[x] = k[0]*3 - 1
                        k[0] -= 1
                    else:
                        ans[x] = k[2]*3
                        k[2] -= 1
            else:
                ans[i] = k[2] * 3
                k[2] -= 1

    print(*ans)


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+3
        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)))

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
		elif cur[1] <= n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[2]
			cur[2] += 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:
def main():
    import itertools
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**9)

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

    A  = [[] for j in range(N+1)]
    for edge in edges:
      A[edge[0]].append([edge[1]])
      A[edge[1]].append([edge[0]])

    #print(N,edges)
    #print(A)

    def dfs(A, s):
        for v in A[s]:
            if depth[v[0]] == -1:
                depth[v[0]] = depth[s] + 1
                dfs(A, v[0])

    pair = []
    for i in range(1,N+1):
        depth = [-1] * (N + 1)
        depth[i] = 0
        dfs(A, i)
        for j,d in enumerate(depth):
            if d ==3:
                pair.append([i,j])
    #print(pair)

    cand = list(itertools.permutations(list(range(1,N+1))))

    flg = 1
    for a in cand:
        #print(a,a[1])
        for i in range(len(pair)//2):
            i1,i2= pair[i][0]-1,pair[i][1]-1
            #print(i1,i2,a)
            if (a[i1]+a[i2])%3!=0 and (a[i1]*a[i2])%3!=0:
                break
            elif i == len(pair)//2-1:
                print(*a)
                flg = 0
            if flg ==0:
                break
        if flg ==0:
            break

    if flg ==1:
        print(-1)

if __name__ == '__main__':
    main()

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]]

cnt = 1
while cnt < N:
	cp,cd = q.pop(0)
	for np in E[cp]:
		if ans[np] == 0:
			ans[np] = cd*(-1)
			cnt += 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)