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

Solution code:
from collections import deque

N = int(input())
tree = [[] for i 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)

d = deque([[0, -1]])
dist = [0] * N
while d:
  node, par = d.pop()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    dist[child] = (dist[node] + 1) % 2
    d.appendleft([child, node])

count0 = dist.count(0)
count1 = N - count0
s = [set(), set(), set()]
for i in range(1, N+1):
  s[i%3].add(i)
if count0 > N//3:
  if count1 > N//3:
    for i in range(N):
      if dist[i]:
        if s[2]:
          dist[i] = s[2].pop()
        else:
          dist[i] = s[0].pop()
      else:
        if s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
  else:
    for i in range(N):
      if dist[i]:
        dist[i] = s[0].pop()
      else:
        if s[2]:
          dist[i] = s[2].pop()
        elif s[1]:
          dist[i] = s[1].pop()
        else:
          dist[i] = s[0].pop()
else:
  for i in range(N):
    if dist[i]:
      if s[2]:
        dist[i] = s[2].pop()
      elif s[1]:
        dist[i] = s[1].pop()
      else:
        dist[i] = s[0].pop()
    else:
      dist[i] = s[0].pop()

print(*dist)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())

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

inf=float("inf")

prv=[inf]*n
prv[0]=-1
depth=[inf]*n
depth[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next in edge[cur]:
    if prv[next]==inf:
      prv[next]=cur
      depth[next]=depth[cur]+1
      stack.append(next)
e,o=0,0
for i in range(n):
  if depth[i]%2:
    o+=1
  else:
    e+=1
Ans=[0]*n
if e<=n//3:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if not depth[i]%2:
      Ans[i]=3*ct3+3
      ct3+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      elif 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1
elif o<=n//3:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if depth[i]%2:
      Ans[i]=3*ct3+3
      ct3+=1
    else:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      elif 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1
else:
  ct1,ct2,ct3=0,0,0
  for i in range(n):
    if not depth[i]%2:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      else:
        Ans[i]=3*ct3+3
        ct3+=1

print(*Ans)

Submission status: Accepted

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

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

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


class Tree:
    WHITE = 0
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += 1
                self.dfs(v)
                self.depth -= 1

        self.colors[u] = self.BLACK


tree = Tree(adj)
tree.dfs(0)

ev = [i for i, e in enumerate(tree.depths) if e % 2 == 0]
od = [i for i, e in enumerate(tree.depths) if e % 2]

l_ev = len(ev)
l_od = len(od)

mod0 = [e for e in range(1, n + 1) if e % 3 == 0]
mod1 = [e for e in range(1, n + 1) if e % 3 == 1]
mod2 = [e for e in range(1, n + 1) if e % 3 == 2]

ans = [0] * n


def f(li1, li2):
    while li1 and li2:
        i = li1.pop()
        num = li2.pop()
        ans[i] = num


if l_ev > n / 3 and l_od > n / 3:
    f(ev, mod1)
    f(od, mod2)
    f(ev, mod0)
    f(od, mod0)

elif l_ev <= n / 3:
    f(ev, mod0)
    f(od, mod0)
    f(od, mod1)
    f(od, mod2)

else:
    f(od, mod0)
    f(ev, mod0)
    f(ev, mod1)
    f(ev, mod2)

print(*ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

import queue

def main():
    N=I()
    adj=[[] for _ in range(N)]
    mod1=range(1,N+1,3)
    n1=0
    mod2=range(2,N+1,3)
    n2=0
    mod12=list(mod1)+list(mod2)
    n12=0
    mod3=range(3,N+1,3)
    n3=0
    
    p=[0]*N
    
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
     
    
    q=queue.Queue()
    q.put((0,-1,0))#node,par,depth
    d=[0]*N#深さをメモ
            
        
    while not q.empty():
        v,par,depth=q.get()
        d[v]=depth%2
                
        for i in range(len(adj[v])):
            nxt=adj[v][i]
            if nxt!=par:
                q.put((nxt,v,depth+1))
                
    dmod=[0,0]
    for i in range(N):
        dmod[d[i]]+=1
        
    if dmod[0]<=(N//3):
        for i in range(N):
            if d[i]==0:
                p[i]=mod3[n3]
                n3+=1
            else:
                if n12<len(mod12):
                    p[i]=mod12[n12]
                    n12+=1
                else:
                    p[i]=mod3[n3]
                    n3+=1
    elif dmod[1]<=(N//3):
        for i in range(N):
            if d[i]==1:
                p[i]=mod3[n3]
                n3+=1
            else:
                if n12<len(mod12):
                    p[i]=mod12[n12]
                    n12+=1
                else:
                    p[i]=mod3[n3]
                    n3+=1         
    
    else:
        for i in range(N):
            if d[i]==1:
                if n1<len(mod1):
                    p[i]=mod1[n1]
                    n1+=1
                else:
                    p[i]=mod3[n3]
                    n3+=1
            else:
                if n2<len(mod2):
                    p[i]=mod2[n2]
                    n2+=1
                else:
                    p[i]=mod3[n3]
                    n3+=1     
    
                
    print(' '.join(map(str, p)))
        
        
    
    
        
                
            
        
        
    

main()

Submission status: Accepted

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
    DistType = [0, 0]
    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)
        DistType[dist % 2] += 1
        for nextNode in Edge[nowNode]:
            if nextNode != preNode: q.append((nextNode, nowNode, dist + 1))
    Ans = [-1] * N
    if DistType[0] <= modCount[0]:
        for i, d in enumerate(Dist):
            if d % 2 == 0:
                Ans[i] = 3 * modIndex[0] + 3
                modIndex[0] += 1
            else:
                if modIndex[1] < modCount[1]:
                    Ans[i] = 3 * modIndex[1] + 1
                    modIndex[1] += 1
                elif modIndex[2] < modCount[2]:
                    Ans[i] = 3 * modIndex[2] + 2
                    modIndex[2] += 1
                else:
                    Ans[i] = 3 * modIndex[0] + 3
                    modIndex[0] += 1
    elif DistType[1] <= modCount[0]:
        for i, d in enumerate(Dist):
            if d % 2 == 1:
                Ans[i] = 3 * modIndex[0] + 3
                modIndex[0] += 1
            else:
                if modIndex[1] < modCount[1]:
                    Ans[i] = 3 * modIndex[1] + 1
                    modIndex[1] += 1
                elif modIndex[2] < modCount[2]:
                    Ans[i] = 3 * modIndex[2] + 2
                    modIndex[2] += 1
                else:
                    Ans[i] = 3 * modIndex[0] + 3
                    modIndex[0] += 1
    else:
        for i, d in enumerate(Dist):
            if d % 2 == 0:
                if modIndex[1] < modCount[1]:
                    Ans[i] = 3 * modIndex[1] + 1
                    modIndex[1] += 1
                else:
                    Ans[i] = 3 * modIndex[0] + 3
                    modIndex[0] += 1
            else:
                if modIndex[2] < modCount[2]:
                    Ans[i] = 3 * modIndex[2] + 2
                    modIndex[2] += 1
                else:
                    Ans[i] = 3 * modIndex[0] + 3
                    modIndex[0] += 1
    print(" ".join(map(str, Ans)))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10**6)

def dfs(i, depth):
    visited[i] = True
    oe = depth%2
    ans[i-1] = oe
    count[oe] += 1
    nodes = tree[i]
    for node in nodes:
        if visited[node]:
            continue
        dfs(node, depth+1)
    


N = int(input())
ans = [-1]*N
tree = [[] for i in range(N+1)]
visited = [False]*(N+1)
count = [0, 0]
base = [1, 2, 3]
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a] += [b]
    tree[b] += [a]
dfs(1, 0)
even_len = count[0]
odd_len = count[1]
if even_len > N//3 and odd_len > N//3:
    for i, oe in enumerate(ans):
        if base[oe] > N:
            ans[i] = str(base[2])
            base[2] += 3
        else:
            ans[i] = str(base[oe])
            base[oe] += 3
elif even_len <= N//3:
    for i, oe in enumerate(ans):
        if oe == 0:
            ans[i] = str(base[2])
            base[2] += 3
        elif base[0] <= N:
            ans[i] = str(base[0])
            base[0] += 3
        elif base[1] <= N:
            ans[i] = str(base[1])
            base[1] += 3
        else:
            ans[i] = str(base[2])
            base[2] += 3
elif odd_len <= N//3:
    for i, oe in enumerate(ans):
        if oe == 1:
            ans[i] = str(base[2])
            base[2] += 3
        elif base[0] <= N:
            ans[i] = str(base[0])
            base[0] += 3
        elif base[1] <= N:
            ans[i] = str(base[1])
            base[1] += 3
        else:
            ans[i] = str(base[2])
            base[2] += 3
print(' '.join(ans))

Submission status: Accepted

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

if q[0]<=r[0]+r[1] and q[1]<=r[0]+r[2]:
    for i in range(n):
        if rank[i]%2==0:
            if tmp1<=n:
                ans[i]=tmp1
                tmp1+=3
            else:
                ans[i]=tmp3
                tmp3+=3
        else:
            if tmp2<=n:
                ans[i]=tmp2
                tmp2+=3
            else:
                ans[i]=tmp3
                tmp3+=3

elif q[0]<=r[0]:
    for i in range(n):
        if rank[i]%2==0:
            ans[i]=tmp3
            tmp3+=3
        else:
            if tmp1<=n:
                ans[i]=tmp1
                tmp1+=3
            elif tmp2<=n:
                ans[i]=tmp2
                tmp2+=3
            else:
                ans[i]=tmp3
                tmp3+=3

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

    

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

Submission status: Accepted

Solution code:
from heapq import heappop as he
n=int(input())
s=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    s[a].append(b)
    s[b].append(a)
c=[0]*n
q=[1]
t=[1]*n
t[1]=0
fl=0
while q:
    fl^=1
    p=[]
    for j in q:
        for h in s[j]:
            if t[h]:
                t[h]=0
                c[h]=fl
                p.append(h)
    q=p.copy()
if c.count(1)>n//3 and c.count(0)>n//3:
    p,q,r=1,2,3
    for i in range(n):
        if c[i]:
            if q<=n:
                c[i]=q
                q+=3
            else:
                c[i]=r
                r+=3
        else:
            if p<=n:
                c[i]=p
                p+=3
            else:
                c[i]=r
                r+=3
elif c.count(1)<=n//3:
    p,q,r=1,2,3
    for i in range(n):
        if c[i]:
            c[i]=r
            r+=3
        else:
            if p<=n:
                c[i]=p
                p+=3
            elif q<=n:
                c[i]=q
                q+=3
            else:
                c[i]=r
                r+=3
else:
    p,q,r=1,2,3
    for i in range(n):
        if not c[i]:
            c[i]=r
            r+=3
        else:
            if q<=n:
                c[i]=q
                q+=3
            elif p<=n:
                c[i]=p
                p+=3
            else:
                c[i]=r
                r+=3
print(*c)

Submission status: Accepted

Solution code:
from collections import deque


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[root] = 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)
dfs(0)
cnt0 = 0
cnt1 = 0
for i in range(n):
    if visited[i] == 0:
        cnt0 += 1
    else:
        cnt1 += 1

num1 = n // 3 
num2 = n // 3
num3 = n // 3
if n % 3 >= 1:
   num1 += 1
if n % 3 >= 2:
   num2 += 1
    
ans = [0] * n

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)
        
if cnt0 <= num3:
    for i in range(n):
        if visited[i] == 0:
            ans[i] = set3.pop()
        else:
            if set1:
                ans[i] = set1.pop() 
            elif set2:
                ans[i] = set2.pop()         
            elif set3:
                ans[i] = set3.pop()  

elif cnt1 <= num3:
    for i in range(n):
        if visited[i] == 1:
            ans[i] = set3.pop()
        else:
            if set1:
                ans[i] = set1.pop() 
            elif set2:
                ans[i] = set2.pop()         
            elif set3:
                ans[i] = set3.pop()  
else:
    num147 = 0
    num258 = 0
    num369 = 0
    for i in range(n):
        if visited[i] == 0:
            num = num147 * 3 + 1
            if num > n:
                num = num369 * 3 + 3
                ans[i] = num
                if num > n:
                    error
                    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:
                    error
                    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: Accepted

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)
l0 = dist.count(0)
l1 = n - l0
if l0 <= n//3:
  for i in range(n):
    if dist[i] == 0:
      L[i] = F_0.pop()
    else:
      if F_1:
        L[i] = F_1.pop()
      elif F_2:
        L[i] = F_2.pop()
      else:
        L[i] = F_0.pop()
elif l1 <= n//3:
  for i in range(n):
    if dist[i]:
      L[i] = F_0.pop()
    else:
      if F_1:
        L[i] = F_1.pop()
      elif F_2:
        L[i] = F_2.pop()
      else:
        L[i] = F_0.pop()
else:
  for i in range(n):
    if dist[i]:
      if F_1:
        L[i] = F_1.pop()
      else:
        L[i] = F_0.pop()
    else:
      if F_2:
        L[i] = F_2.pop()
      else:
        L[i] = F_0.pop()
print(*L)

Submission status: Accepted

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 == 1 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: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 1(mod 3)のグループと2(mod 3)を先に決める
N = ir()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

root = 1
rank = [0] * (N+1) # 1-indexed
rank[1] = 1
parent = [0] * (N+1) # 1-indexed
stack = [root]
while stack:
    cur = stack.pop()
    r = rank[cur]
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        rank[next] = r + 1
        stack.append(next)

counter = [0, 0]
for x in rank[1:]:
    counter[x%2] += 1
num0mod3 = N // 2
num1mod3 = (N+2) // 3
num2mod3 = (N+1) // 3
answer = [0] * (N+1)
if max(counter) >= num1mod3 + num2mod3:
    #この時ここに1mod3、2mod3を全部入れる
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N+1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 1
            if cur % 3 == 0:
                cur += 1
            if cur > N:
                break
    cur = 1
    for j in range(1, N+1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)
else:
    #ここではcounterの多い方にnum1mod3を入れる
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N+1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 2
    for i in range(1, N+1):
        if rank[i] % 2 == 1-index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 1
    for j in range(1, N+1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)

print(*answer[1:])

Submission status: Accepted

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):
	if num1 > num2:
		more = 0
	else:
		more = 1
	cur = [1, 2, 3]
	for i in range(n):
		if signs[i] == more:
			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()

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

Solution code:
from collections import deque
import math

N = int(input())
side = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    side[a-1].append(b-1)
    side[b-1].append(a-1)
ans = [0]*N
ans[0] = 1
queue = deque([0])
count = [0,1,0]
while queue:
    q = queue.popleft()
    for i in side[q]:
        if ans[i] == 0:
            ans[i] = ans[q]%2 + 1
            count[ans[i]] += 1
            queue.append(i)
if max(count) <=N - (N+1)//3:
    X = [3,2,2]
    X[count.index(max(count))] = 1
    for i in range(N):
        if X[ans[i]] <= N:
            X[ans[i]] += 3
            ans[i] = X[ans[i]]-3
        else:
            ans[i] = X[0]
            X[0] += 3
else:
    Y = 3 - count.index(max(count))
    Z = 3 - Y
    X = 3
    for i in range(N):
        if ans[i] == Y:
            ans[i] = X
            X += 3
    W = 1
    for i in range(N):
        if ans[i] == Z:
            ans[i] = W
            W += 1
            if W%3 == 0 and W < X:
                W += 1
print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
seen = [0 for _ in range(n)]
clr = [2 for _ in range(n)]
seen[0] = 1
clr[0] = 0
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        now.append(y)
        clr[y] = 1 - clr[x]
#print(seen)
#print(clr)
a = n - sum(clr)
b = sum(clr)
z1 = 1
z2 = 2
z3 = 3
g1 = (n+2)//3
g2 = (n+1)//3
g3 = n//3
#print(g1,g2,g3)
ans = [0 for _ in range(n)]
if a > g3 and b > g3:
  for i in range(n):
    if clr[i] == 0:
      if g1:
        ans[i] = z1
        z1 += 3
        g1 -= 1
      else:
        ans[i] = z3
        z3 += 3
    else:
      if g2:
        ans[i] = z2
        z2 += 3
        g2 -= 1
      else:
        ans[i] = z3
        z3 += 3
elif a <= g3:
  g3 -= a
  for i in range(n):
    if clr[i] == 0:
      ans[i] = z3
      z3 += 3
    else:
      if g3:
        ans[i] = z3
        z3 += 3
        g3 -= 1
      elif g1:
        ans[i] = z1
        z1 += 3
        g1 -= 1
      else:
        ans[i] = z2
        z2 += 3
elif b <= g3:
  g3 -= b
  for i in range(n):
    if clr[i] == 1:
      ans[i] = z3
      z3 += 3
    else:
      if g3:
        ans[i] = z3
        z3 += 3
        g3 -= 1
      elif g1:
        ans[i] = z1
        z1 += 3
        g1 -= 1
      else:
        ans[i] = z2
        z2 += 3
else:
  err
print(' '.join(map(str,ans)))