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: Time Limit Exceeded

Solution code:
import itertools 

N = int(input())
pairs = []
for i in range(N - 1):
  pairs.append([int(i) for i in input().split(' ')]) 
pairs = pairs + [list(reversed(l)) for l in pairs]

two = list(itertools.permutations(pairs, 2))

two_paths = []
for t in two:
  if t[0][1] == t[1][0]:
    two_paths.append(t)

three_paths = []

for p in list(itertools.permutations(pairs, 3)):
  if (p[0][0], p[2][1]) in pairs:
    continue 
  if p[0][1] != p[1][0] or p[1][1] != p[2][0] or p[0][0] == p[1][1] or p[1][0] == p[2][1] or p[0][0] == p[2][1]:
    continue

  skip = False
  for t in two_paths: 
    if t[0][0] == p[0][0] and t[1][1] == p[2][1]:
      skip = True
      break 
  
  if not skip and not (p[2][1], p[0][0]) in three_paths:
    three_paths.append((p[0][0], p[2][1]))

possibilities = list(itertools.permutations([n + 1 for n in range(N)], N))

for po in possibilities:
  verdict = True
  for tp in three_paths:
    if po[tp[0]- 1] * po[tp[1] - 1] % 3 != 0 and po[tp[0] - 1] + po[tp[1] - 1] % 3 != 0:
      verdict = False
      continue 
    
  if verdict:
    print(' '.join([str(k) for k in po]))
    break

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, permutations
from collections import Counter

def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in range(n - 1)]
    tgt = []

    # 1. 距離が3になる組み合わせを探す, 1つしか出現しない頂点が2つのもの
    for v in combinations(ab, 3):
        # print([hoge for i in v for hoge in i])
        # print(set([hoge for i in v for hoge in i]))
        # dic = Counter([hoge for i in v for hoge in i]) # ここがだめそう。
        # tmp = [i for i, j in dic.items() if j == 1]
        tmp = [hoge for i in v for hoge in i]
        if len(tmp) - len(set(tmp)) == 2:
            dic = Counter([hoge for i in v for hoge in i]) # ここがだめそう。
            fuga = [i for i, j in dic.items() if j == 1]
            tgt.append(fuga)

    # 2. 順列を作る
    for i in permutations(range(1, n + 1)):
        for tg in tgt:
            a = i[tg[0] - 1]
            b = i[tg[1] - 1]
            if not (((a + b) % 3 == 0) or ((a * b) % 3 == 0)):
                break
        else:
            print(' '.join(map(str, i)))
            exit(0)

    print('-1')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 久々の幅優先探索……

import queue

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n-1)]
num_0_mod_3 = n // 3
num_2_mod_3 = (n+1) // 3
num_1_mod_3 = (n+2) // 3


def add_edge(u, v ):
    G[u].append(v)
    G[v].append(u)

G = [[] for _ in range(n)] #グラフの隣接リスト表現
for edge in edges:
    add_edge(edge[0]-1, edge[1]-1)

num_distance_even = 0
num_distance_odd = 0

q = queue.Queue()
q.put(0)

distance = [-1] * n
distance[0] = 0
num_distance_even += 1

for v in G[0]:
    q.put(v)

while(q.qsize() > 0):
    now = q.get()
    for v in G[now]:
        if distance[v] >= 0:
            pass
        else:
            q.put(v)
            distance[v] = distance[now] + 1
            if (distance[v] & 1):
                num_distance_odd += 1
            else:
                num_distance_even += 1

# print(distance)
# print(num_distance_even, num_distance_odd)

ans = [-1] * n

index_one = 1
index_two = 2
index_zero = 3

if num_distance_even >= num_1_mod_3 + num_2_mod_3:
    # evenに120 oddに0

    for i in range(n):
        if (distance[i] & 1) == 1:
            ans[i] = index_zero
            index_zero += 3
        else:
            if (index_one <= n):
                ans[i] = index_one
                index_one += 3
            elif (index_two <= n):
                ans[i] = index_two
                index_two += 3
            else:
                ans[i] = index_zero
                index_zero += 3


elif num_distance_odd >= num_1_mod_3 + num_2_mod_3:
    # evenに0 oddに012
    for i in range(n):
        if (distance[i] & 1) == 0:
            ans[i] = index_zero
            index_zero += 3
        else:
            if (index_one <= n):
                ans[i] = index_one
                index_one += 3
            elif (index_two <= n):
                ans[i] = index_two
                index_two += 3
            else:
                ans[i] = index_zero
                index_zero += 3


else:
#     num_distance_even <= num_distance_odd * 2 and num_distance_odd <= num_distance_even * 2:
    # evenを2、oddを1、適宜0
    for i in range(n):
        if (distance[i] & 1) == 1:
            if (index_one <= n):
                ans[i] = index_one
                index_one += 3
            else:
                ans[i] = index_zero
                index_zero += 3
        else:
            if (index_two <= n):
                ans[i] = index_two
                index_two += 3
            else:
                ans[i] = index_zero
                index_zero += 3


print(' '.join(list(map(str, ans))))

Submission status: Time Limit Exceeded

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

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap





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

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

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


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


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

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


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

    # N = 2 * (10**5)
    # AB = [[i, i+1] for i in range(1, N)]
    # print(*slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n -1)]
for row in edges:
    row.append(1)

def BFS(K,edges,N):
    roots=[ [] for i in range(N)]
    for a,b,c in edges:
        roots[a-1]+=[(b-1,c)]
        roots[b-1]+=[(a-1,c)]
    dist=[-1]*N
    stack=[]
    stack.append(K)
    dist[K]=0
    while stack:
        label=stack.pop(-1)
        for i,c in roots[label]:
            if dist[i]==-1:
                dist[i]=dist[label]+c
                stack+=[i]
    return dist
            
ans = []          
for i in range(n):
    z = [j for j, x in enumerate(BFS(i, edges, n)) if x == 3 and i <= j]
    for p in z:
            ans.append([i + 1, p + 1])
import sys
import itertools
for i in itertools.permutations(range(1, n+1)):
    c = 0
    for j in range(len(ans)):
        if i[ans[j][0] - 1] + i[ans[j][1] - 1] % 3 == 0 or i[ans[j][0] - 1] * i[ans[j][1] - 1] % 3 == 0:
            c += 1
    if c == len(ans):
        print(' '.join(map(str, i)))
        sys.exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations, permutations
from collections import Counter

def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in range(n - 1)]
    tgt = []

    # 1. 距離が3になる組み合わせを探す, 1つしか出現しない頂点が2つのもの
    for v in combinations(ab, 3):
        dic = Counter([hoge for i in v for hoge in i])
        tmp = [i for i, j in dic.items() if j == 1]
        if len(tmp) == 2:
            tgt.append(tmp)

    # 2. 順列を作る
    for i in permutations([i for i in range(1, n + 1)], n):
        for tg in tgt:
            a = i[tg[0] - 1]
            b = i[tg[1] - 1]
            if not (((a + b) % 3 == 0) or ((a * b) % 3 == 0)):
                break
        else:
            print(' '.join(map(str, i)))
            exit(0)

    print('-1')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap





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

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

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


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


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

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


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

    # N = 2 * (10**5)
    # AB = [[i, i+1] for i in range(1, N)]
    # print(*slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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]:
        x=1
        for i in range(10**20):
            x+=1
        print(-1)
        sys.exit()
    else:
        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
            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: Time Limit Exceeded

Solution code:
n=int(input())

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

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

table=[]
def go(first,curr,step,checked):
    if step==3:
        a,b= min(first,curr),max(first,curr)
        if [a,b] not in table:
            table.append([a,b])
        return
    for i in graph[curr]:
        if i not in checked:
            checked.append(i)
            go(first,i,step+1,checked)
            checked.remove(i)

for i in range(n):
    go(i,i,0,[i])

#mods=[[j for j in range(n) if j%3==i] for i in range(3)]

found=False
def find_perm(used,left,case):
    global found
    if found:
        return
    if case==len(table):
        for i in range(n):
            if used[i]==-1:
                used[i]=left[0]
                left.pop(0)
        found=True
        print(' '.join(str(i) for i in used))
        return
    i,j= table[case][0],table[case][1]
    l,k= used[i],used[j]
    if k!=-1 and l!=-1:
        if (l + k) % 3 == 0 or (l * k) % 3 == 0:
            find_perm(used,left,case+1)
    elif k!=-1 and l==-1:
        for l in left:
            if l != k:
                if (l + k) % 3 == 0 or (l * k) % 3 == 0:
                    used[i] = l
                    left.remove(l)
                    find_perm(used, left, case + 1)
                    used[i] = -1
                    left.append(l)
    elif k==-1 and l!=-1:
        for k in left:
            if l != k:
                if (l + k) % 3 == 0 or (l * k) % 3 == 0:
                    used[j] = k
                    left.remove(k)
                    find_perm(used, left, case + 1)
                    used[j] = -1
                    left.append(k)
    else:
        for l in left:
            for k in left:
                if l!=k:
                    if (l+k)%3==0 or (l*k)%3==0:
                        used[i] = l
                        used[j] = k
                        left.remove(l)
                        left.remove(k)
                        find_perm(used, left, case + 1)
                        used[i] = -1
                        used[j] = -1
                        left.append(l)
                        left.append(k)

find_perm([-1 for i in range(n)],[i for i in range(1,n+1)],0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

table = [[] for _ in range(N + 1)]
sta = []
for x in range(1, N + 1):
  Q = dq([])
  Q.append((x, 0))
  vis = set()
  while len(Q):
    y, n = Q.popleft()
    if n == 3:
      table[x].append(y)
      continue
    for q in e[y]:
      if q in vis: continue
      vis.add(q)
      Q.append((q, n + 1))
  sta.append((len(table[x]), x))
sta.sort()
nm = [0] * 3
for x in range(1, N + 1): nm[x % 3] += 1

res = [0] * (N + 1)

while nm[0]:
  _, x = sta.pop()
  res[x] = nm[0] * 3
  nm[0] -= 1

while nm[1]:
  _, x = sta[-1]
  ng = 0
  for y in table[x]:
    if res[y] % 3 == 1:
      ng = 1
      break
  if ng:
    continue
  sta.pop()
  res[x] = (nm[1] - 1) * 3 + 1
  nm[1] -= 1

while nm[2]:
  _, x = sta[-1]
  ng = 0
  for y in table[x]:
    if res[y] % 3 == 2:
      ng = 1
      break
  if ng: continue
  sta.pop()
  res[x] = (nm[2] - 1) * 3 + 2
  nm[2] -= 1

print(*res[1: ])

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
#AB = [list(map(int1, readline().split())) for _ in range(N - 1)]

# N: 頂点数
# G[v]: 頂点vの子頂点 (親頂点は含まない)

# Euler Tour の構築
S = []
F = [0] * N
depth = [0] * N

G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    acc = list(map(int1, readline().split()))
    G[acc[0]].append(acc[1])


def dfs(v, d):
    F[v] = len(S)
    depth[v] = d
    S.append(v)
    for w in G[v]:
        dfs(w, d + 1)
        S.append(v)


dfs(0, 0)

# 存在しない範囲は深さが他よりも大きくなるようにする
INF = (N, None)

# LCAを計算するクエリの前計算
M = 2 * N
M0 = 2**(M - 1).bit_length()
data = [INF] * (2 * M0)
for i, v in enumerate(S):
    data[M0 - 1 + i] = (depth[v], i)
for i in range(M0 - 2, -1, -1):
    data[i] = min(data[2 * i + 1], data[2 * i + 2])


# LCAの計算 (generatorで最小値を求める)
def _query(a, b):
    yield INF
    a += M0
    b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b - 1]
        if a & 1:
            yield data[a - 1]
            a += 1
        a >>= 1
        b >>= 1


# LCAの計算 (外から呼び出す関数)
def query(u, v):
    fu = F[u]
    fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv + 1))[1]]


dists = []
for i in range(N):
    for j in range(i + 1, N):
        if depth[i] + depth[j] - 2 * depth[query(i, j)] == 3:
            dists.append((i, j))

for per in permutations(range(N)):
    flag = True
    for dist in dists:
        if ((per[dist[0]] + per[dist[1]]) % 3 != 0) & (
            (per[dist[0]] * per[dist[1]]) % 3 != 0):
            flag = False
            break
    if flag:
        print(*([p + 1 for p in per]))
        sys.exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

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

table=[]
def go(first,curr,step,checked):
    if step==3:
        a,b= min(first,curr),max(first,curr)
        if [a,b] not in table:
            table.append([a,b])
        return
    for i in graph[curr]:
        if i not in checked:
            checked.append(i)
            go(first,i,step+1,checked)
            checked.remove(i)

for i in range(n):
    go(i,i,0,[i])

#mods=[[j for j in range(n) if j%3==i] for i in range(3)]

def check(a):
    for t in table:
        i,j= t[0],t[1]
        if (a[i]+a[j])%3!=0 and (a[i]*a[j])%3!=0:
            return False
    return True

perm=[]

def find_perm(a):
    global perm
    if len(perm)!=0:
        return
    if len(a)==n:
        if(check(a)):
            perm=a
            print(' '.join(str(i) for i in a))
        return
    for i in range(1,n+1):
        if i not in a:
            a.append(i)
            find_perm(a)
            a.remove(i)

find_perm([])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
e = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = map(int, input().split())
    e[u].append(v)
    e[v].append(u)
vis = [False] * (n + 1)
cv = [[], []]
c = [0] * (n + 1)

q = [1]
vis[1] = True
c[1] = 0
cv[c[1]].append(1)
while q:
    u = q.pop(0)
    for v in e[u]:
        if vis[v]:
            continue
        q.append(v)
        vis[v] = True
        c[v] = c[u] ^ 1
        cv[c[v]].append(v)

bf = [[i for i in range(j, n + 1, 3)] for j in [3, 1, 2]]
res = [0] * (n + 1)
if len(cv[0]) > len(cv[1]):
    cv[0], cv[1] = cv[1], cv[0]


if len(cv[0]) <= len(bf[0]):
    for u in cv[0]:
        res[u] = bf[0].pop(-1)
    for v in cv[1]:
        for j in range(3):
            if not bf[j]:
                continue
            res[v] = bf[j].pop(-1)
            break
else:
    for u in cv[0]:
        for j in [2, 0, 1]:
            if not bf[j]:
                continue
            res[u] = bf[j].pop(-1)
            break
    for v in cv[1]:
        for j in range(3):
            if not bf[j]:
                continue
            res[v] = bf[j].pop(-1)
            break

print(*res[1:])

Submission status: Accepted

Solution code:
n=int(input())
ki=[[] for _ in range(n)]

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

odd=[-1]*n
odd[0]=0
todo=[0]
while todo:
    v=todo.pop()
    for nv in ki[v]:
        if odd[nv]==-1:
            odd[nv]=abs(odd[v]-1)
            todo.append(nv)
from collections import Counter
co=Counter(odd)
ans=[0]*n
if co[1]<=n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==1 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1

elif co[0]<=n//3:
    cnt1=1
    cnt2=0
    cnt3=1
    for i in range(n):
        if odd[i]==0 and 3*cnt3<=n:
            ans[i]=3*cnt3
            cnt3+=1
        else:
            if cnt1%3==0:cnt1+=1
            if cnt1<=n:
                ans[i]=cnt1
                cnt1+=1
            else:
                ans[i]=n-n%3-cnt2*3
                cnt2+=1
else:
    cnt1=1
    cnt2=1
    cnt3=1
    for i in range(n):
        if odd[i]==1:
            if 3*cnt1-2<=n:
                ans[i]=3*cnt1-2
                cnt1+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
        else:
            if 3*cnt2-1<=n:
                ans[i]=3*cnt2-1
                cnt2+=1
            else:
                ans[i]=3*cnt3
                cnt3+=1
print(*ans,sep=' ')

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n = int(input())
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    not_yet = deque([0])
    already = [False]*n
    already[0] = True
    dist = [0]*n

    while not_yet:
        value = not_yet.popleft()
        for v in tree[value]:
            if already[v]:
                continue
            already[v] = True
            dist[v] = (dist[value] + 1) % 2
            not_yet.append(v)
    
    zero = dist.count(0)
    one = dist.count(1)

    ans = [0]*n
    already = [False]*n
    if zero >= one:
        if one <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 1:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 0:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1
    else:
        if zero <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 0:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 1:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1

    print(*ans)

            


    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n = int(input())
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    
    not_yet = deque([0])
    already = [False]*n
    already[0] = True
    dist = [0]*n

    while not_yet:
        value = not_yet.popleft()
        for v in tree[value]:
            if already[v]:
                continue
            already[v] = True
            dist[v] = (dist[value] + 1) % 2
            not_yet.append(v)
    
    zero = dist.count(0)
    one = dist.count(1)

    ans = [0]*n
    already = [False]*n
    if zero >= one:
        if one <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 1:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 0:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1
    else:
        if zero <= n//3:
            ind = 1
            for i in range(n):
                if dist[i] == 0:
                    ans[i] = ind*3
                    already[ind*3-1] = True
                    ind += 1
            ind = 0
            for i in range(n):
                if ans[i] == 0:
                    while already[ind]:
                        ind += 1
                    ans[i] = ind + 1
                    already[ind] = True
    
        else:
            c0, c1, c2 = 0, 0, 1
            z, o = n//3 + bool(n%3), n//3 + bool(n%3==2)
            for i in range(n):
                if dist[i] == 1:
                    if c0 >= z:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c0*3 + 1
                    c0 += 1
                else:
                    if c1 >= o:
                        ans[i] = c2*3
                        c2 += 1
                        continue
                    ans[i] = c1*3 + 2
                    c1 += 1

    print(*ans)

            



    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
dist=[-1]*n
G=[[] for i in range(n)]

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

from collections import deque
queue=deque([[0,i] for i in G[0]])
dist[0]=0
while queue:
    now,to=queue.pop()
    # print(now,to)
    if dist[to]!=-1:continue
    dist[to]=1-dist[now]
    for i in G[to]:
        queue.appendleft([to,i])

# print(dist)
q=sum(dist)
LAST=[0]*n
if n/3 <= q and n/3 <= n-q:
    
    A=[i for i in range(1,n+1,3)] + [0]*n
    

    B=[i for i in range(2,n+1,3)] + [0]*n


    now1=0
    now2=0
    for i in range(n):
        if dist[i]:
            LAST[i]=B[now2]
            now2+=1
        else:
            LAST[i]=A[now1]
            now1+=1
    w=3
    for i in range(n):
      if LAST[i]==0:
        LAST[i]=w
        w+=3
    print(*LAST)
            
elif n/3 >q:
    w=3
    for i in range(n):
        if dist[i]:
            LAST[i]=w
            w+=3
    A=[i for i in range(w,n+1,3)]+[i for i in range(1,n+1) if i%3!=0]
    now=0
    for i in range(n):
        if LAST[i]==0:
            LAST[i]=A[now]
            now+=1
    print(*LAST)
else:
    w=3
    for i in range(n):
        if dist[i]==0:
            LAST[i]=w
            w+=3
    A=[i for i in range(w,n+1,3)]+[i for i in range(1,n+1) if i%3!=0]
    now=0
    for i in range(n):
        if LAST[i]==0:
            LAST[i]=A[now]
            now+=1
    print(*LAST)