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

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

root = -1
for i,e in enumerate(edge):
    if len(e) == 1:
        root = i
        break

visited = set([root])
to_search = [root]
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
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())

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

print("E===", E)

Q = []

DIS3 = [[] for _ in range(N+1)]
for i in range(1, N+1):
    nxt = [(x, i) for x in E[i]]

    Q = nxt
    for j in range(2):
        newQ = []

        while Q:
            a, prev = Q.pop()

            for v in E[a]:
                if v == prev:
                    continue
                newQ.append((v, a))

        if len(newQ) == 0:
            Q = []
            break
        Q = newQ

    DIS3[i] = Q

# print(DIS3)
print(0)
exit()

Submission status: Wrong Answer

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


INF = 10 ** 20
def solve(n, edges):
  def func(start):
    cost = [INF] * n
    que = [(0, start)]
    cost[start] = 0
    while que:
      acc, num = heappop(que)
      for to in edges[num]:
        if 1 + acc < cost[to]:
          cost[to] = 1 + acc
          heappush(que, (1 + acc, to))
    return cost
  
  cost1 = func(0)
  max_ind = cost1.index(max(cost1))
  cost2 = func(max_ind)
  max_ind2 = cost2.index(max(cost2))
  cost3 = func(max_ind2)
  res = [0] * n
  for i in range(n):
      res[i] = max(cost2[i], cost3[i])
  return res



n = int(input())
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)

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)

distance2 = solve(n, tree)
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:
import sys

n = int(input())
es = [[] for _ in range(n + 1)]

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

for i in range(1, n + 1):
	if len(es[i]) == 1:
		start = i
		break
			
#print(es)
depth = [[], [start]]

ll = [0, 1, 0, 0, 0, 0]

while len(depth[-1]) >= 1:
	#print(depth)
	new = []
	for dst in depth[-1]:
		new.extend(es[dst])
	depth.append([x for x in new if x not in depth[-2]])
	ll[(len(depth) - 1) % 6] += len(new)

print(depth)

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))
# graph = [[(6, 1), (7, 1)], [(6, 1)], [(6, 1)], [(4, 1)], [(3, 1), (5, 1)], [(4, 1), (7, 1)], [(0, 1), (1, 1), (2, 1)], [(0, 1), (5, 1)]]
# print(graph)


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
while counts[1] > 0 or counts[2] > 0:
    n = 1 if counts[1] >= counts[2] else 2
    i = 0
    while i < len(vs):
        if ansmod[vs[i]] < 0:
            break
        i += 1
    else:
        break
    while i < len(vs):
        v = vs[i]
        if ansmod[v] < 0 and counts[n] > 0:
            counts[n] -= 1
            ansmod[v] = n
        n = 1 if n == 2 else 2
        i += 3

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:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

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

    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()

    C = [len(child[v]) for v in range(N+1)]
    GC = [0] * (N+1)
    three_num = [0] * (N+1)
    for v in seq:
        for u in child[v]:
            GC[v] += C[u]
            three_num[v] += GC[u]
    #print(GC)
    #print(three_num)
    for v in seq:
        p = par[v]
        if p:
            three_num[v] += GC[p] - C[v]
        pp = par[p]
        if pp:
            three_num[v] += C[pp] - 1
        ppp = par[pp]
        if ppp:
            three_num[v] += 1

    one = list(range(1, N+1, 3))
    two = list(range(2, N+1, 3))
    three = list(range(3, N+1, 3))
    info = [(i, three_num[i], seen[i]&1) for i in range(1, N+1)]
    info.sort(key=lambda x: x[1], reverse=True)
    ans = [0] * (N+1)
    for v, _, flg in info:
        if three:
            ans[v] = three.pop()
        else:
            if flg:
                if one:
                    ans[v] = one.pop()
                else:
                    ans[v] = two.pop()
            else:
                if two:
                    ans[v] = two.pop()
                else:
                    ans[v] = one.pop()
    print(*ans[1:])


if __name__ == '__main__':
    main()

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_
        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 < m2:
                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 < m2:
                    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

    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:
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))
print(-1) #ごめんなさい

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
E = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

# def bfs(cur, pre, c):
#     stack = deque([[cur, pre, c]])
#     while stack:
#         cur, pre, c = stack.popleft()
#         if c <= 3:
#             for e in E[cur]:
#                 if e != pre:
#                     stack.append([e, cur, c+1])
#
# for i in range(n):
#     bfs(i, -1, 0)

print(-1)

Submission status: Wrong Answer

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

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

for i in range(n):
  print(bfs(i))

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
visited = [False]*N
q = deque([0])  # 始まりのノード
visited[0] = True
distant = [0]*N
distant[0] = 0
while len(q):
    # vは数字, 親のノードのインデックス
    v = q.pop()
    color = 1

    for e in tree[v]:
        if visited[e]:  # 到達済みなら次のノードへ
            continue
        visited[e] = True
        distant[e] = (distant[v] + 1) % 3
        q.append(e)

mod_dict = defaultdict(deque)
for i in range(2, N+1):
    mod_dict[i%3].append(i)
# print(mod_dict)

ans = [1]
for i in range(1, N):
    if len(mod_dict[distant[i]]) > 0:
        ans.append(mod_dict[distant[i]].popleft())
    elif len(mod_dict[distant[0]]) > 0:
        ans.append(mod_dict[distant[0]].popleft())
    else:
        print('-1')
        exit()
print(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n = int(input())

def f(x):
  return int(x)-1

rel = [[] for i in range(n)]

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

rel3 = [[] for i in range(n)]

for i in range(n):
  visited = [False]*n
  q = [(i,0)]
  while q:
    t,l = q.pop(0)
    visited[t] = True
    if l == 3:
      rel3[i].append(t)
    else:
      for nxt in rel[t]:
        if not visited[nxt]:
          q.append((nxt,l+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):
    went = [False]*n
    dis = [0 for _ in range(n)]
    que = deque([])
    que.append(0)
    went[0] = True
    cnt_odd = 0
    cnt_even = 1
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if went[g[go][i]]:
                continue
            dis[g[go][i]] = dis[go] + 1
            went[g[go][i]] = True
            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,ans,que_1,que_2):
    went = [False]*n
    dis = [0 for _ in range(n)]
    see = []
    que = deque([])
    que.append(s)
    went[s] = True
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if went[g[go][i]]:
                continue
            dis[g[go][i]] = dis[go] + 1
            went[g[go][i]] = True
            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 ans,que_1,que_2

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)
    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:
            ans,que_1,que_2 = length3(e,n,g,ans,que_1,que_2)
        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:
            ans,que_1,que_2 = length3(e,n,g,ans,que_1,que_2)
        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:
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)

visited = set([0])
to_search = [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
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)]
for i in range(n):
    x[rank[i]].append(i)
ans=[-1 for i in range(n)]
tmp1,tmp2,tmp3=1,2,3
for i in range(M+1):
    if i%2==0:
        for p in x[i]:
            if tmp1<=n:
                ans[p]=tmp1
                tmp1+=3
            else:
                ans[p]=tmp3
                tmp3+=3
    else:
        for p in x[i]:
            if tmp2<=n:
                ans[p]=tmp2
                tmp2+=3
            else:
                ans[p]=tmp3
                tmp3+=3
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Wrong Answer

Solution code:
N=int(input())

a=[]
b=[]

for i in range(N-1):
    kari=input().split(" ")
    a.append(int(kari[0]))
    b.append(int(kari[1]))
    
print("3"*N)

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 = []
for i in range(n):
    for j in range(n):
        k = dijkstra(i, n, w, cost)
        if k[j]==3:
            li1.append([i,j])
ans=[1]*n
for i in li1:
    ans[i[0]]=3
    ans[i[1]]=3

if li1 == []:
    print('-1')
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter, deque

N, = list(map(int, input().split()))

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

mod1 = 1
mod2 = 2
mod3 = 3

assign = {}

dist = {}
q = deque()
q.append(1)
dist[1] = 0
while q:
    node = q.popleft()
    level = dist[node]
    assert node not in assign

    if level % 2 == 0:
        assign[node] = mod1
        mod1 += 3
    if level % 2 == 1:
        assign[node] = mod2
        mod2 += 3

    for nbr in g[node]:
        if nbr not in dist:
            q.append(nbr)
            dist[nbr] = level + 1

for i in range(1, N + 1):
    if assign[i] > N:
        if mod3 > N:
            print(-1)
            exit()
        assign[i] = mod3
        mod3 += 3

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