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:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


# サイズが大きいとdefaultdictが早い(for文を書かなくて済む)
from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)

def is_bip(ns):
    start = 0
    q = [start]
    cs = [None]*n
    cs[start] = 1
    while q:
        u = q.pop()
        c = cs[u]
        cc = int(not c)
        for v in ns[u]:
            if cs[v] is None:
                cs[v] = cc
                q.append(v)
            elif cs[v]==c:
                return False, None
    return True, cs
_, cs = is_bip(ns)
v1, v0 = 0, 0
for num in cs:
    if num==0:
        v0 += 1
    else:
        v1 += 1
num0 = [i for i in range(1,n+1) if i%3==0]
num1 = [i for i in range(1,n+1) if i%3==1]
num2 = [i for i in range(1,n+1) if i%3==2]
if v0<=len(num0) or v1<=len(num0):
    if v0<=len(num0):
        val = 0
    else:
        val = 1
    for i in range(n):
        if cs[i]==val:
            cs[i] = num0.pop()
        else:
            if num1:
                cs[i] = num1.pop()
            elif num2:
                cs[i] = num2.pop()
            else:
                cs[i] = num0.pop()
else:
    if v0<=v1:
        val = 0
    else:
        val = 1
    for i in range(n):
        if cs[i]==val:
            if num1:
                cs[i] = num1.pop()
            else:
                cs[i] = num0.pop()
        else:
            if num2:
                cs[i] = num2.pop()
            else:
                cs[i] = num0.pop()
write(" ".join(map(str, cs)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N=int(input())

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

def dfs(u,par,depth):
  dist_list[u]=depth
  for v in tree[u]:
    if v!=par:
      dfs(v,u,depth+1)
  
dist_list=[-1]*(N+1)
dfs(1,0,0)
#print(dist_list)

num_even=num_odd=0
for i in range(1,N+1):
  if dist_list[i]%2==0:
    num_even+=1
  else:
    num_odd+=1
#print(num_even,num_odd)

num_3m0=3
num_3m1=1
num_3m2=2
answer_list=[0]*(N+1)
if num_even<=N//3:
  for i in range(1,N+1):
    if dist_list[i]%2==0:
      answer_list[i]=num_3m0
      num_3m0+=3
    else:
      if num_3m1<=N:
        answer_list[i]=num_3m1
        num_3m1+=3
      elif num_3m2<=N:
        answer_list[i]=num_3m2
        num_3m2+=3
      else:
        answer_list[i]=num_3m0
        num_3m0+=3
elif num_odd<=N//3:
  for i in range(1,N+1):
    if dist_list[i]%2==1:
      answer_list[i]=num_3m0
      num_3m0+=3
    else:
      if num_3m1<=N:
        answer_list[i]=num_3m1
        num_3m1+=3
      elif num_3m2<=N:
        answer_list[i]=num_3m2
        num_3m2+=3
      else:
        answer_list[i]=num_3m0
        num_3m0+=3
else:
  for i in range(1,N+1):
    if dist_list[i]%2==0:
      if num_3m1<=N:
        answer_list[i]=num_3m1
        num_3m1+=3
      else:
        answer_list[i]=num_3m0
        num_3m0+=3
    else:
      if num_3m2<=N:
        answer_list[i]=num_3m2
        num_3m2+=3
      else:
        answer_list[i]=num_3m0
        num_3m0+=3
        
print(*answer_list[1:])

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(2*10**5)
I = [int(_) for _ in open(0).read().split()]
N = I[0]
AB = I[1:]
G = collections.defaultdict(set)
for a, b in zip(AB[::2], AB[1::2]):
    G[a].add(b)
    G[b].add(a)
color = [None] * (N + 1)


def dfs(G, v, cur):
    color[v] = cur
    for w in G[v]:
        if color[w] is None:
            dfs(G, w, 1 - cur)


dfs(G, 1, 0)
c=collections.Counter(color[1:])
cand1 = set(range(1, N + 1, 3))
cand2 = set(range(2, N + 1, 3))
cand3 = set(range(3, N + 1, 3))

i0, i1 = 0, 1
if c[0] > c[1]:
    i0, i1 = 1, 0

ans = [None] * (N + 1)
if c[i0] <= len(cand3):
    for i in range(1, N + 1):
        if color[i]==i0:
            ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand2:
                ans[i] = cand2.pop()
            elif cand3:
                ans[i] = cand3.pop()
else:
    for i in range(1, N + 1):
        if color[i] == i0:
            if cand2:
                ans[i] = cand2.pop()
            elif cand3:
                ans[i] = cand3.pop()
        else:
            if cand1:
                ans[i] = cand1.pop()
            elif cand3:
                ans[i] = cand3.pop()
print(*ans[1:])

Submission status: Accepted

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

def bfs():
    color = [0]*N
    color[0] = 1
    q = deque([0])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if color[nv]==0:
                color[nv] = -color[v]
                q.append(nv)
    
    return color

N = int(input())
G = [[] for _ in range(N)]

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

n = [0, 0, 0]

for i in range(1, N+1):
    n[i%3] += 1
    
color = bfs()
b = color.count(1)

if b>N-b:
    for i in range(N):
        color[i] *= -1
        
ans = [-1]*N

if min(b, N-b)<=n[0]:
    q = deque([i for i in range(1, N+1) if i%3==0]+[i for i in range(1, N+1) if i%3!=0])
else:
    q = deque([i for i in range(1, N+1) if i%3==1]+[i for i in range(1, N+1) if i%3==0]+[i for i in range(1, N+1) if i%3==2])

for i in range(N):
    if color[i]==1:
        ans[i] = q.popleft()
        
for i in range(N):
    if color[i]==-1:
        ans[i] = q.popleft()

print(*ans)

Submission status: Accepted

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

N = int(input())

tree = [[] for _ in range(N)]
bip = [None for _ in range(N)]

for _ in range(N - 1):
    u, v = map(int, input().split())
    tree[u - 1].append(v - 1)
    tree[v - 1].append(u - 1)

stack = [0]
bip[0] = 0

while stack:
    node = stack.pop()
    for adj in tree[node]:
        if bip[adj] is not None:
            continue
        bip[adj] = not bip[node]
        stack.append(adj)

res = [None for _ in range(N)]

white = sum(bip)
black = N - white

p0 = []
p1 = []
p2 = []

for i in range(1, N + 1):
    if i % 3 == 0:
        p0.append(i)

for i in range(1, N + 1):
    if i % 3 == 1:
        p1.append(i)

for i in range(1, N + 1):
    if i % 3 == 2:
        p2.append(i)

if white <= N // 3:
    p = p0 + p1 + p2
    cnt = 0
    for i in range(N):
        if bip[i]:
            res[i] = p[cnt]
            cnt += 1
    for i in range(N):
        if not bip[i]:
            res[i] = p[cnt]
            cnt += 1
    print(*res)

elif black <= N // 3:
    p = p0 + p1 + p2
    cnt = 0
    for i in range(N):
        if not bip[i]:
            res[i] = p[cnt]
            cnt += 1
    for i in range(N):
        if bip[i]:
            res[i] = p[cnt]
            cnt += 1
    print(*res)

else:
    p = p1 + p0 + p2
    cnt = 0
    for i in range(N):
        if not bip[i]:
            res[i] = p[cnt]
            cnt += 1
    for i in range(N):
        if bip[i]:
            res[i] = p[cnt]
            cnt += 1
    print(*res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
e = [[] for _ in range(N + 1)]
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

a = [1]
b = []
s = [1]
vis = [0] * (N + 1)
table = [-1] * (N + 1)
table[1] = 1
vis[1] = 1
while len(s):
  x = s.pop()
  for y in e[x]:
    if vis[y]: continue
    vis[y] = 1
    table[y] = table[x] ^ 1
    if table[y]: a.append(y)
    else: b.append(y)
    s.append(y)
if len(a) > len(b): a, b = b, a
res = [0] * (N + 1)
if len(a) <= N // 3:
  ss = set([x for x in range(1, N + 1)])
  x = 3
  for y in a:
    res[y] = x
    ss.discard(x)
    x += 3
  ss = list(ss)
  for i in range(1, N + 1):
    if res[i]: continue
    res[i] = ss.pop()
  print(*res[1: ])
else:
  ss = set([x for x in range(1, N + 1)])
  x = 2
  for y in a:
    res[y] = x
    ss.discard(x)
    x += 3
    if x > N: break
  x = 3
  for y in a:
    if res[y]: continue
    res[y] = x
    ss.discard(x)
    x += 3
  ss = list(ss)
  for i in range(1, N + 1):
    if res[i]: continue
    res[i] = ss.pop()
  print(*res[1: ])

Submission status: Accepted

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

rb = [-1]*n
rb[0] = 1
count1 = 1
count2 = 0
rb_m = [[0]]
for i in rb_m:
    n_rb = []
    for j in i:
        x = rb[j]
        for k in ab[j]:
            if(rb[k] != -1):
                continue
            if(x == 1):
                rb[k] = 2
                count2 += 1
            elif(x == 2):
                rb[k] = 1
                count1 += 1
            n_rb.append(k)
    set(n_rb)
    if(n_rb == []):
        break
    else:
        rb_m.append(n_rb)

ans = [0 for i in range(n)]
if(count1 > n//3 and count2 > n//3):
    ne1 = 1
    ne2 = 2
    ne3 = 3
    for i in range(n):
        if(rb[i] == 1 and ne1 <= n):
            ans[i] = ne1
            ne1 += 3
        elif(rb[i] == 2 and ne2 <= n):
            ans[i] = ne2
            ne2 += 3
        else:
            ans[i] = ne3
            ne3 += 3
elif(count2 >= 2*n//3):
    ne1 = 1
    ne2 = 2
    ne3 = 3
    for i in range(n):
        if(rb[i] == 1):
            ans[i] = ne3
            ne3 += 3
        elif(ne1 <= n):
            ans[i] = ne1
            ne1 += 3
        elif(ne2 <= n):
            ans[i] = ne2
            ne2 += 3
        else:
            ans[i] = ne3
            ne3 += 3
elif(count1 >= 2*n//3):
    ne1 = 1
    ne2 = 2
    ne3 = 3
    for i in range(n):
        if(rb[i] == 2):
            ans[i] = ne3
            ne3 += 3
        elif(ne1 <= n):
            ans[i] = ne1
            ne1 += 3
        elif(ne2 <= n):
            ans[i] = ne2
            ne2 += 3
        else:
            ans[i] = ne3
            ne3 += 3
print(*ans)

Submission status: Accepted

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())
  a=a-1
  b=b-1
  E[a].append(b)
  E[b].append(a)
D=deque([0])
V=[0]*n
V[0]=1
A=[0]*n
k=1
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(E[x])):
    if V[E[x][i]]==0:
      V[E[x][i]]=1
      D.append(E[x][i])
      A[E[x][i]]=A[x]^1
f=0
if n-sum(A)>sum(A):
  f=1
g=max(n-sum(A),sum(A))
a=(n+2)//3
b=n//3
if g>a+b:
  Ans=[0]*n
  s=1
  t=2
  u=3
  if f==0:
    for i in range(n):
      if A[i]==0:
        Ans[i]=u
        u=u+3
      else:
        if s<=n:
          Ans[i]=s
          s=s+3
        elif t<=n:
          Ans[i]=t
          t=t+3
        else:
          Ans[i]=u
          u=u+3
  else:
    for i in range(n):
      if A[i]==1:
        Ans[i]=u
        u=u+3
      else:
        if s<=n:
          Ans[i]=s
          s=s+3
        elif t<=n:
          Ans[i]=t
          t=t+3
        else:
          Ans[i]=u
          u=u+3
else:
  Ans=[0]*n
  s=1
  t=2
  u=3
  if f==1:
    for i in range(n):
      if A[i]==0 and s<=n:
        Ans[i]=s
        s=s+3
      elif A[i]==0 and s>n:
        Ans[i]=u
        u=u+3
      elif A[i]==1 and t<=n:
        Ans[i]=t
        t=t+3
      else:
        Ans[i]=u
        u=u+3
  else:
    for i in range(n):
      if A[i]==1 and s<=n:
        Ans[i]=s
        s=s+3
      elif A[i]==1 and s>n:
        Ans[i]=u
        u=u+3
      elif A[i]==0 and t<=n:
        Ans[i]=t
        t=t+3
      else:
        Ans[i]=u
        u=u+3
print(*Ans)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
even=[]
odd=[]
ansl=[0]*n
nums=set([i for i in range(1,n+1)])
dist=[-1]*n
dist[0]=0
even.append(0)
D=deque([0])
while D:
    v=D.popleft()
    for i in graph[v]:
        if dist[i]!=-1:continue
        dist[i]=dist[v]+1
        D.append(i)
        if dist[i]%2:odd.append(i)
        else:even.append(i)
El=len(even)
Ol=len(odd)
if El <= Ol:
    if El <= n//3:
        for i in range(El):
            ansl[even[i]]=(i+1)*3
            nums.remove((i+1)*3)
        for i in range(Ol):
            ansl[odd[i]]=nums.pop()
    else:
        cnt=0
        while 3*cnt+2<=n:
            ansl[even[cnt]]=3*cnt+2
            ansl[odd[cnt]]=3*cnt+1
            nums.remove(3*cnt+2)
            nums.remove(3*cnt+1)
            cnt+=1
        for i in range(cnt,El):
            ansl[even[i]]=nums.pop()
        for i in range(cnt,Ol):
            ansl[odd[i]]=nums.pop()

if Ol < El:
    if Ol <= n//3:
        for i in range(Ol):
            ansl[odd[i]]=(i+1)*3
            nums.remove((i+1)*3)
        for i in range(El):
            ansl[even[i]]=nums.pop()
    else:
        cnt=0
        while 3*cnt+2<=n:
            ansl[odd[cnt]]=3*cnt+2
            ansl[even[cnt]]=3*cnt+1
            nums.remove(3*cnt+2)
            nums.remove(3*cnt+1)
            cnt+=1
        for i in range(cnt,Ol):
            ansl[odd[i]]=nums.pop()
        for i in range(cnt,El):
            ansl[even[i]]=nums.pop()
print(*ansl)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

bigraph = [0] * n


def dfs(v, v_p, depth):
    bigraph[v] = depth % 2
    for v_next in graph[v]:
        if v_next == v_p:
            continue
        dfs(v_next, v, depth + 1)


dfs(0, -1, 1)
m1 = sum(bigraph)
m2 = n - m1

ans = [-1] * n
if m1 > n // 3 and m2 > n // 3:
    c1 = 1
    c2 = 2
    for i in range(n):
        if bigraph[i] == 0 and c1 <= n:
            ans[i] = c1
            c1 += 3
        if bigraph[i] == 1 and c2 <= n:
            ans[i] = c2
            c2 += 3
    c3 = 3
    for i in range(n):
        if ans[i] == -1:
            ans[i] = c3
            c3 += 3
elif m1 > m2:
    # print('A')
    c1 = 1
    c2 = 2
    c3 = 3
    for i in range(n):
        if bigraph[i] == 0:
            # print(i, c1)
            ans[i] = c3
            c3 += 3
    for i in range(n):
        if ans[i] == -1:
            if c1 <= n:
                ans[i] = c1
                c1 += 3
            elif c2 <= n:
                ans[i] = c2
                c2 += 3
            else:
                ans[i] = c3
                c3 += 3
else:  # m1 < m2
    # print('B')
    c1 = 1
    c2 = 2
    c3 = 3
    for i in range(n):
        if bigraph[i] == 1:
            # print(i, c1)
            ans[i] = c3
            c3 += 3
    for i in range(n):
        if ans[i] == -1:
            if c1 <= n:
                ans[i] = c1
                c1 += 3
            elif c2 <= n:
                ans[i] = c2
                c2 += 3
            else:
                ans[i] = c3
                c3 += 3

print(*ans)

Submission status: Accepted

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

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
mod_0 = []
mod_1 = []
mod_2 = []
for i in range(1, n + 1):
    if i % 3 == 0:
        mod_0.append(i)
    elif i % 3 == 1:
        mod_1.append(i)
    else:
        mod_2.append(i)
ans = [-1]*n
from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

d = bfs(0)

cnt = [[] for _ in range(2)]

for i in range(n):
    if d[i] % 2 == 0:
        cnt[0].append(i + 1)
    elif d[i] % 2 == 1:
        cnt[1].append(i + 1)

cnt = sorted(cnt, key=lambda x: len(x))

if len(mod_0) >= len(cnt[0]):
    for i in range(len(cnt[0])):
        ans[cnt[0][i] - 1] = mod_0.pop()
    for i in range(len(cnt[1])):
        if mod_0:
            ans[cnt[1][i] - 1] = mod_0.pop()
        elif mod_1:
            ans[cnt[1][i] - 1] = mod_1.pop()
        else:
            ans[cnt[1][i] - 1] = mod_2.pop()
    print(*ans)
    sys.exit()

for i in range(2):
    c = cnt[i]
    for j in range(len(c)):
        if mod_2 and i == 0:
            ans[cnt[i][j] - 1] = mod_2.pop()
        elif mod_1 and i == 1:
            ans[cnt[i][j] - 1] = mod_1.pop()
        elif mod_0:
            ans[cnt[i][j] - 1] = mod_0.pop()
        else:
            print(-1)
            sys.exit()
print(*ans)

Submission status: Accepted

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())
  a=a-1
  b=b-1
  E[a].append(b)
  E[b].append(a)
D=deque([0])
V=[0]*n
V[0]=1
A=[0]*n
k=1
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(E[x])):
    if V[E[x][i]]==0:
      V[E[x][i]]=1
      D.append(E[x][i])
      A[E[x][i]]=A[x]^1
f=0
if n-sum(A)>sum(A):
  f=1
g=max(n-sum(A),sum(A))
a=(n+2)//3
b=n//3
if g>a+b:
  Ans=[0]*n
  s=1
  t=2
  u=3
  if f==0:
    for i in range(n):
      if A[i]==0:
        Ans[i]=u
        u=u+3
      else:
        if s<=n:
          Ans[i]=s
          s=s+3
        elif t<=n:
          Ans[i]=t
          t=t+3
        else:
          Ans[i]=u
          u=u+3
  else:
    for i in range(n):
      if A[i]==1:
        Ans[i]=u
        u=u+3
      else:
        if s<=n:
          Ans[i]=s
          s=s+3
        elif t<=n:
          Ans[i]=t
          t=t+3
        else:
          Ans[i]=u
          u=u+3
else:
  Ans=[0]*n
  s=1
  t=2
  u=3
  if f==1:
    for i in range(n):
      if A[i]==0 and s<=n:
        Ans[i]=s
        s=s+3
      elif A[i]==0 and s>n:
        Ans[i]=u
        u=u+3
      elif A[i]==1 and t<=n:
        Ans[i]=t
        t=t+3
      else:
        Ans[i]=u
        u=u+3
  else:
    for i in range(n):
      if A[i]==1 and s<=n:
        Ans[i]=s
        s=s+3
      elif A[i]==1 and s>n:
        Ans[i]=u
        u=u+3
      elif A[i]==0 and t<=n:
        Ans[i]=t
        t=t+3
      else:
        Ans[i]=u
        u=u+3
print(*Ans)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = [[] for _ in range(N + 1)]
dist = [-1 for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
zero = []
one = []
two = []
for i in range(1, N + 1):
    if i % 3 == 1:
        one.append(i)
    elif i % 3 == 2:
        two.append(i)
    else:
        zero.append(i)
q = deque([1])
dist[1] = 0

while q.__len__() != 0:
    s = q.popleft()
    for i in G[s]:
        if dist[i] == -1:
            q.append(i)
            dist[i] = (dist[s] + 1) % 2

red = 0
blue = 0

for i in range(1, N + 1):
    if dist[i] == 0:
        red += 1
    else:
        blue += 1
ans = []
if red > N / 3 and blue > N / 3:
    for i in range(1, N + 1):
        if dist[i] == 0 and one.__len__() != 0:
            ans.append(one.pop())
        elif dist[i] == 1 and two.__len__() != 0:
            ans.append(two.pop())
        else:
            ans.append(zero.pop())
elif red <= N / 3:
    for i in range(1, N + 1):
        if dist[i] == 0:
            ans.append(zero.pop())
        else:
            if one.__len__() != 0:
                ans.append(one.pop())
            elif two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

else:
    for i in range(1, N + 1):
        if dist[i] == 1:
            ans.append(zero.pop())
        else:
            if one.__len__() != 0:
                ans.append(one.pop())
            elif two.__len__() != 0:
                ans.append(two.pop())
            else:
                ans.append(zero.pop())

print(*ans)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

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)

depth=[0]*N
def dfs(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            depth[nv]=depth[v]+1
            dfs(nv,v)

dfs(0,-1)

even=0
odd=0
for i in range(N):
    if depth[i]%2==0:
        even+=1
    else:
        odd+=1

ans=[0 for i in range(N)]

if N%3==0:
    if min(even,odd)>=N//3:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==0:
                if N//3>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif N//3>even:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==0:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==1:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
    else:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==1:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==0:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
elif N%3==2:
    if min(even,odd)>=N//3+1:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==0:
                if N//3+1>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3+1>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif N//3+1>even:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==0:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==1:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
    else:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==1:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==0:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
else:
    if even>=N//3+1 and odd>=N//3:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==0:
                if N//3+1>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif even>=N//3 and odd>=N//3+1:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==1:
                if N//3+1>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif N//3>=even:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==0:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==1:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
    else:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==1:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==0:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)

Submission status: Accepted

Solution code:
g = {}
n=int(input())
m = [-1]*n
import sys
sys.setrecursionlimit(1000000000)
def dfs(graph,node,height):
    global m
    global zeros
    global ones
    m[node-1]=height
    if height==0:
      zeros+=1
    if height==1:
      ones+=1
    for n in graph[node]:
      if m[n-1]==-1:
        dfs(graph,n,1-height)

zeros=0
ones=0
for i in range(n-1):
  a,b=map(int,input().split())
  if not a in g:
    g[a]=[b]
  else:
    g[a].append(b)
  if not b in g:
    g[b]=[a]
  else:
    g[b].append(a)
dfs(g,1,0)
ans=[0]*n
used=[0]*n
r=n//3
if 3*(r+1)<=n:
  r+=1
if zeros<=r:
  current=3
  for i in range(n):
    if m[i]==0:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==1:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
elif ones<=r:
  current=3
  for i in range(n):
    if m[i]==1:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==0:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
else:
  if zeros<ones:
    current=1
    for i in range(n):
      if m[i]==0:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
    counter=0
    for i in range(n):
      if m[i]==1:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
  else:
    current=1
    for i in range(n):
      if m[i]==1:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
      counter=0
    for i in range(n):
      if m[i]==0:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    q = deque()
    q.append(1)
    dist = [-1] * (n + 1)
    dist[1] = 0
    while q:
        p = q.popleft()
        for i in G[p]:
            if dist[i] == -1:
                dist[i] = dist[p] + 1
                q.append(i)
    return dist

n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
dist = bfs()
c1, c2 = 0, 0
group1, group2 = [], []
for i in range(1, n + 1):
    if dist[i] % 2 == 1:
        c1 += 1
        group1.append(i)
    else:
        c2 += 1
        group2.append(i)
m = n // 3
ans = [0] * (n + 1)
if m >= min(c1, c2):
    l = [3 * i + 3 for i in range(m)] + [3 * (i // 2) + (i % 2) + 1 for i in range(n - m)]
    j = 0
    if c1 < c2:
        for i in group1:
            ans[i] = l[j]
            j += 1
        for i in group2:
            ans[i] = l[j]
            j += 1
    else:
        for i in group2:
            ans[i] = l[j]
            j += 1
        for i in group1:
            ans[i] = l[j]
            j += 1
else:
    j = 1
    for i in range(c1):
        if i <= (n - 1) // 3:
            ans[group1[i]] = 3 * i + 1
        else:
            ans[group1[i]] = 3 * j
            j += 1
    for i in range(c2):
        if i <= (n - 2) // 3:
            ans[group2[i]] = 3 * i + 2
        else:
            ans[group2[i]] = 3 * j
            j += 1
ans.pop(0)
print(*ans)