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=sys.stdin.readline
N, = map(int, input().split())
G = [set() for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].add(b)
    G[b].add(a)

xs = [[] for _ in range(2)]
g2 = [set() for _ in range(N+1)]
vs = set()
stack = [1]
depth = [0]*(N+1)
dfs_vs = []
vs.add(1)
while stack:
    v = stack.pop()
    xs[depth[v] % 2].append(v)
    dfs_vs.append(v)
    for u in G[v]:
        if u in vs:
            continue
        depth[u] = depth[v] + 1
        g2[v].add(u)
        stack.append(u)
        vs.add(u)

xs.sort(key=lambda x:len(x))
rs = []
if len(xs[0]) <= N//3:
    i=j=k=0
    for x in xs[0]:
        i+=1
        rs.append((x, 3*i))
    for x in xs[1]:
        if i+1 <= N//3:
            i+=1
            rs.append((x, 3*i))
        elif j <= (N-1)//3:
            rs.append((x, 3*j+1))
            j+=1
        else:
            rs.append((x, 3*k+2))
            k+=1
else:
    i=j=k=0
    for x in xs[0]:
        if j <= (N-1)//3:
            rs.append((x, 3*j+1))
            j+=1
        elif i+1 <= N//3:
            i+=1
            rs.append((x, 3*i))
    for x in xs[1]:
        if i+1 <= N//3:
            i+=1
            rs.append((x, 3*i))
        else:
            rs.append((x, 3*k+2))
            k+=1

#print(rs)
rs.sort(key=lambda x:x[0])
print(" ".join(str(x[1]) for x in rs))

Submission status: Accepted

Solution code:
n = int(input())
edge = [[] 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)
 
group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)
 
three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))

Submission status: Accepted

Solution code:
from collections import deque

def resolve():
    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)
    
resolve()

Submission status: Accepted

Solution code:
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
from collections import deque
l = [deque() for _ in range(N+1)]
ans = [0]*N
for a,b in ab:
  l[a].append(b)
  l[b].append(a)
  
r = [0]*(N+1)
i = 0
p = l[1]
q = deque()
flag = [False]*(N+1)
flag[1]=True
while (len(p)!=0)or(len(q)!=0):
  if i%2==0:
    while len(p)!=0:
      j = p.pop()
      if flag[j]:
        continue
      else:
        q.extend(l[j])
        flag[j]=True
        r[j]=1
    i+=1
  else:
    while len(q)!=0:
      j = q.pop()
      if flag[j]:
        continue
      else:
        p.extend(l[j])
        flag[j]=True
    i+=1
a = deque(range(1,N+1,3))
b = deque(range(2,N+1,3))
c = deque(range(3,N+1,3))
x = sum(r)
if x<=N//3:
  for i in range(1,N+1):
    if r[i]==1:
      ans[i-1]=c.pop()
    else:
      if len(a)!=0:
        ans[i-1]=a.pop()
      elif len(b)!=0:
        ans[i-1]=b.pop()
      else:
        ans[i-1]=c.pop()
elif (N-x)<=N//3:
  for i in range(1,N+1):
    if r[i]==0:
      ans[i-1]=c.pop()
    else:
      if len(a)!=0:
        ans[i-1]=a.pop()
      elif len(b)!=0:
        ans[i-1]=b.pop()
      else:
        ans[i-1]=c.pop()
else:
  for i in range(1,N+1):
    if r[i]==1:
      if len(a)!=0:
        ans[i-1]=a.pop()
      elif len(c)!=0:
        ans[i-1]=c.pop()
      else:
        ans[i-1]=b.pop()
    else:
      if len(b)!=0:
        ans[i-1]=b.pop()
      elif len(c)!=0:
        ans[i-1]=c.pop()
      else:
        ans[i-1]=a.pop()
        
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

N, *ab = map(int, read().split())

if N == 2:
    print(1, 2)
    exit()

graph = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)
    graph[b].append(a)

k0 = list(range(3, N + 1, 3))
k1 = list(range(1, N + 1, 3))  # 1番多い
k2 = list(range(2, N + 1, 3))

start = ab[0]
color = 1  # 1が黒
queue = deque([(start, color)])
colors = [0] * (N + 1)
colors[start] = 1
while queue:
    V, c = queue.popleft()
    c = -c
    for v in graph[V]:
        if colors[v] == 0:
            colors[v] = c
            queue.append((v, c))

black = colors.count(1)
white = N - black
three = (N - 3) // 3 + 1
if black <= three:
    b = k0[:black]
    w = k1 + k2 + k0[black:]
    answer = [b.pop() if i == 1 else w.pop() for i in colors[1:]]
    print(' '.join(map(str, answer)))
elif white <= three:
    w = k0[:white]
    b = k1 + k2 + k0[white:]
    answer = [b.pop() if i == 1 else w.pop() for i in colors[1:]]
    print(' '.join(map(str, answer)))
else:
    answer = [0] * (N + 1)
    for i in range(1, N + 1):
        if colors[i] == 1:
            if k1:
                answer[i] = k1.pop()
            else:
                answer[i] = k0.pop()
        else:
            if k2:
                answer[i] = k2.pop()
            else:
                answer[i] = k0.pop()
    print(' '.join(map(str, answer[1:])))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

N = n_in()
edges = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = l_in()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)


# Euler Tour の構築
S = []
depth = [0]*N
visited = set()

def dfs(v, d):
    visited.add(v)
    depth[v] = d
    S.append(v)
    for w in edges[v]:
        if w in visited:
            continue
        dfs(w, d+1)
        S.append(v)


root = 0
dfs(root, 0)

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

from collections import deque
q0 = deque(i for i in range(1,N+1) if i%3 == 0)
q1 = deque(i for i in range(1,N+1) if i%3 == 1)
q2 = deque(i for i in range(1,N+1) if i%3 == 2)

even_depth = len(list(filter(lambda d: d%2 == 0, depth)))
odd_depth = len(list(filter(lambda d: d%2 != 0, depth)))

if even_depth > N//3 and odd_depth > N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            if len(q1) > 0:
                res[i] = q1.popleft()
            else:
                res[i] = q0.popleft()
        else:
            if len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()
elif even_depth <= N//3:
    for i, d in enumerate(depth):
        if d%2 == 0:
            res[i] = q0.popleft()
        else:
            if len(q1) > 0:
                res[i] = q1.popleft()
            elif len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()
else:
    for i, d in enumerate(depth):
        if d%2 != 0:
            res[i] = q0.popleft()
        else:
            if len(q1) > 0:
                res[i] = q1.popleft()
            elif len(q2) > 0:
                res[i] = q2.popleft()
            else:
                res[i] = q0.popleft()


print_l(res)

Submission status: Accepted

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

mod = [3, 1, 2]
ans = [0 for i in range(n)]
count = [0, 0]

def bfs(cur, pre, c):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        count[c % 2] += 1
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

def case1(cur, pre, c, i):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        t = c % 2
        if t == i:
            ans[cur] = mod[0]
            mod[0] += 3
        else:
            if mod[1] <= n:
                ans[cur] = mod[1]
                mod[1] += 3
            elif mod[2] <= n:
                ans[cur] = mod[2]
                mod[2] += 3
            else:
                ans[cur] = mod[0]
                mod[0] += 3
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

def case2(cur, pre, c):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        t = c % 2
        if mod[t+1] <= n:
            ans[cur] = mod[t+1]
            mod[t+1] += 3
        else:
            ans[cur] = mod[0]
            mod[0] += 3
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

bfs(0, -1, 0)

if count[0] <= n // 3:
    case1(0, -1, 0, 0)
elif count[1] <= n  // 3:
    case1(0, -1, 0, 1)
else:
    case2(0, -1, 0)

print(" ".join([str(i) for i in ans]))

Submission status: Accepted

Solution code:
n = int(input())
edge = [[] 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)

group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)

three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))

Submission status: Accepted

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

mod = [3, 1, 2]
ans = [0 for i in range(n)]
count = [0, 0]

def bfs(cur, pre, c):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        count[c % 2] += 1
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

def case1(cur, pre, c, i):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        t = c % 2
        if t == i:
            ans[cur] = mod[0]
            mod[0] += 3
        else:
            if mod[1] <= n:
                ans[cur] = mod[1]
                mod[1] += 3
            elif mod[2] <= n:
                ans[cur] = mod[2]
                mod[2] += 3
            else:
                ans[cur] = mod[0]
                mod[0] += 3
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

def case2(cur, pre, c):
    stack = deque([[cur, pre, c]])
    while stack:
        cur, pre, c = stack.popleft()
        t = c % 2
        if mod[t+1] <= n:
            ans[cur] = mod[t+1]
            mod[t+1] += 3
        else:
            ans[cur] = mod[0]
            mod[0] += 3
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, c+1])

bfs(0, -1, 0)

if count[0] < (n + 2)// 3:
    case1(0, -1, 0, 0)
elif count[1] < (n + 2) // 3:
    case1(0, -1, 0, 1)
else:
    case2(0, -1, 0)

print(" ".join([str(i) for i in ans]))

Submission status: Accepted

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

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

b=bfs(0)
ct0=0;ct1=0
for i in range(n):
  b[i]%=2
  if b[i]==0:
    ct0+=1
  else:
    ct1+=1

ans=[0]*n
x1=1;x2=2;x3=3

if ct0>=n//3+1 and ct1>=n//3+1:
  for i in range(n):
    if b[i]==0:
      if x1<=n:
        ans[i]=x1
        x1+=3
      else:
        ans[i]=x3
        x3+=3
    else:
      if x2<=n:
        ans[i]=x2
        x2+=3
      else:
        ans[i]=x3
        x3+=3

elif ct0<=n//3:
  for i in range(n):
    if b[i]==0:
      ans[i]=x3
      x3+=3
    else:
      if x1<=n:
        ans[i]=x1
        x1+=3
      elif x2<=n:
        ans[i]=x2
        x2+=3
      else:
        ans[i]=x3
        x3+=3

elif ct1<=n//3:
  for i in range(n):
    if b[i]==1:
      ans[i]=x3
      x3+=3
    else:
      if x1<=n:
        ans[i]=x1
        x1+=3
      elif x2<=n:
        ans[i]=x2
        x2+=3
      else:
        ans[i]=x3
        x3+=3

for i in range(n):
  ans[i]=str(ans[i])
print(' '.join(ans))

Submission status: Accepted

Solution code:
N = int(input())
from collections import defaultdict
flag = [0 for i in range(N)]
G = defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)


al = [0, 0]
for d in dist:
    al[d%2] += 1
if sum(al) // al[0] >= 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            ansl.append(numbers3.pop())
        else:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
elif sum(al) // al[1] >= 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
else:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            if numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)

Submission status: Accepted

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

def dfs(v, u, d):
    if d % 2 == 0:
        even.append(v)
    else:
        odd.append(v)
    for i in g[v]:
        if i == u:
            continue
        dfs(i, v, d + 1)
    return

N = int(input())
g = [[] for _ in range(N)]
odd = []
even =[]
ans = [-1] * N
nums = [[], [], []]
for i in range(1, N + 1):
    nums[i % 3].append(i)
sanlst = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

dfs(0, -1, 0)
zCnt = len(nums[0])

if len(even) <= zCnt:
    for node in even:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in odd:
        ans[node] = rest.pop()
elif len(odd) <= zCnt:
    for node in odd:
        ans[node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for node in even:
        ans[node] = rest.pop()
else:
    for i in nums[1]:
        ans[even.pop()] = i
    for i in nums[2]:
        ans[odd.pop()] = i
    rest = nums[0]
    for i in even:
        ans[i] = rest.pop()
    for i in odd:
        ans[i] = rest.pop()

print(*ans)

Submission status: Accepted

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


def dfs(v, step):
    global node0, node1
    if step & 1:
        color[v] = 1
        node1 += 1
    else:
        color[v] = 0
        node0 += 1
    for nv in edge[v]:
        if color[nv] is None:
            dfs(nv, step + 1)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)
color = [None] * N
node0 = node1 = 0
dfs(0, 0)

ans = [None] * N
num0 = N // 3
num1 = N // 3 + (N % 3 >= 1)
num2 = N // 3 + (N % 3 == 2)
q0 = deque()
q1 = deque()
q = deque()
if node0 > num0 and node1 > num0:
    for i in range(1, num0 + 1):
        q.append(3 * i)
    for i in range(1, num1 + 1):
        q1.append(3 * i - 2)
    for i in range(1, num2 + 1):
        q0.append(3 * i - 1)
elif node0 <= num0:
    for i in range(1, node0 + 1):
        q0.append(3 * i)
    for i in range(node0 + 1, num0 + 1):
        q.append(3 * i)
    for i in range(1, num1 + 1):
        q1.append(3 * i - 2)
    for i in range(1, num2 + 1):
        q.append(3 * i - 1)
else:
    for i in range(1, node1 + 1):
        q1.append(3 * i)
    for i in range(node1 + 1, num0 + 1):
        q.append(3 * i)
    for i in range(1, num1 + 1):
        q.append(3 * i - 2)
    for i in range(1, num2 + 1):
        q0.append(3 * i - 1)

for i in range(N):
    if color[i] == 0:
        Q = q0 if q0 else q
        ans[i] = Q.pop()
    else:
        Q = q1 if q1 else q
        ans[i] = Q.pop()
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
tree = [[0, 0] for _ in range(N+1)] # [parent, depth(e or o)]
edge = [set() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edge[a].add(b)
    edge[b].add(a)

queue = deque([1])
d, even_or_odd = 1, [1, 0]
while len(queue) > 0:
    newq = set()
    for _ in range(len(queue)):
        p = queue.pop()
        for q in edge[p]:
            if q != tree[p][0]:
                newq.add(q)
                tree[q][0], tree[q][1] = p, d % 2
    even_or_odd[d % 2] += len(newq)
    d += 1
    queue = deque(list(newq))

stock = [N//3] * 3
for i in range(N%3):    stock[i] += 1

if min(even_or_odd) > N//3:
    i, j, k, ans = 0, 0, 1, []
    for l in range(1, N+1):
        if tree[l][1] == 0 and i <= stock[0] - 1:
            ans.append(3*i + 1)
            i += 1
        elif tree[l][1] != 0 and j <= stock[1] - 1:
            ans.append(3*j + 2)
            j += 1
        else:
            ans.append(3*k)
            k += 1
elif even_or_odd[0] <= stock[0] - 1:
    ans, num = [], [3*i for i in range(1, N//3 + 1)] + [i for i in range(N+1) if i % 3 != 0]
    i, j = 0, -1
    for k in range(1, N+1):
        if tree[k][1] == 0:
            ans.append(num[i])
            i += 1
        else:
            ans.append(num[j])
            j -= 1
else:
    ans, num = [], [3*i for i in range(1, N//3 + 1)] + [i for i in range(N+1) if i % 3 != 0]
    i, j = 0, -1
    for k in range(1, N+1):
        if tree[k][1] != 0:
            ans.append(num[i])
            i += 1
        else:
            ans.append(num[j])
            j -= 1
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
import numpy as np

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

class TREE(object):
    def __init__(self, G, root=0):
        self.G = G
        self.root = root
        self.n = len(G)
        self.logn = (self.n - 1).bit_length()
        self.depth = [-1 if i != root else 0 for i in range(self.n)]
        self.parent = [[-1] * self.n for _ in range(self.logn)]
        self.dfs()

    def dfs(self):
        que = [self.root]
        while que:
            u = que.pop()
            for v in self.G[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    self.parent[0][v] = u
                    que += [v]


depth = np.array(TREE(es).depth)

ans = [0]*n

zero = one = two = n // 3
if n % 3 == 1: one += 1
if n % 3 == 2:
    one+=1
    two+=1

num_odd = np.count_nonzero(depth %2 == 1)

if num_odd <= n/3:
    for i in range(n):
        if depth[i] % 2 == 1:
            if zero > 0:
                ans[i] = zero*3
                zero -= 1
        else:
            if two > 0:
                ans[i] = two*3 - 1
                two -= 1
            elif one > 0:
                ans[i] = one*3 - 2
                one -= 1
            elif zero > 0:
                ans[i] = zero*3
                zero -= 1
            else:
                break
    else:
        print(*ans, sep=' ')
        exit()

if num_odd >= n/3*2:
    for i in range(n):

        if depth[i] % 2 == 0:
            if zero > 0:
                ans[i] = zero*3
                zero -= 1
        else:
            if two > 0:
                ans[i] = two*3 - 1
                two -= 1
            elif one > 0:
                ans[i] = one*3 - 2
                one -= 1
            elif zero > 0:
                ans[i] = zero*3
                zero -= 1
            else:
                break
    else:
        print(*ans, sep=' ')
        exit()


for i in range(n):
    if depth[i] % 2 == 0:
        if one > 0:
            ans[i] = one*3 - 2
            one -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
    else:
        if two > 0:
            ans[i] = two*3 - 1
            two -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            break
else:
    print(*ans, sep=' ')
    exit()

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd


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

data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

lst=[0 for i in range(N+1)]
stack=deque([[1,0]])
visited=set([1])

while stack:
    a,m=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            stack.append([p,m+1])
            lst[p]=m+1


oddslst=[i for i in range(len(lst)) if i and not lst[i]%2]
evenlst=[i for i in range(len(lst)) if i and lst[i]%2]
lst=[0 for i in range(N+1)]
if N//3<len(oddslst) and N//3<len(evenlst):
    for i in range(1,N+1):
        if i%3==1:
            lst[oddslst.pop()]=i
        if i%3==2:
            lst[evenlst.pop()]=i
    oddslst+=evenlst
    for i in range(1,N+1):
        if i%3==0:
            lst[oddslst.pop()]=i
else:
    if len(evenlst)<len(oddslst):
        oddslst,evenlst=evenlst,oddslst
    for i in range(1,N+1):
        if i%3==0:
            if oddslst:
                lst[oddslst.pop()]=i
            else:
                lst[evenlst.pop()]=i
        else:
            lst[evenlst.pop()]=i

print(" ".join([str(i) for i in lst if i]))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2 * 10**6)


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


def dfs(n, d):
    if depth[n] != -1:
        return
    depth[n] = d
    for nn in eAB[n]:
        dfs(nn, d + 1)
    return


N = int(input())
AB = [inpl() for i in range(N - 1)]

eAB = [[] for i in range(N)]
for a, b in AB:
    eAB[a - 1].append(b - 1)
    eAB[b - 1].append(a - 1)

depth = [-1 for i in range(N)]

dfs(0, 0)

eo = [[], []]
for i in range(N):
    eo[depth[i] % 2].append(i)

# print(eo)
ans = [-1 for i in range(N)]
if len(eo[0]) > N // 3 and len(eo[1]) > N // 3:
    for i in range(N // 3):
        ans[eo[0][i]] = 3 * i + 1
        ans[eo[1][i]] = 3 * i + 2
    t_0 = N // 3
    t_1 = N // 3
    if N % 3 > 0:
        ans[eo[0][N // 3]] = 3 * (N // 3) + 1
        t_0 += 1
    if N % 3 > 1:
        ans[eo[1][N // 3]] = 3 * (N // 3) + 2
        t_1 += 1
    # print(ans)
    for i, v in enumerate(eo[0][t_0:] + eo[1][t_1:]):
        ans[v] = 3 * (i + 1)
else:
    if len(eo[0]) <= N // 3:
        ni = 0
    else:
        ni = 1
    tmp = [True for i in range(N + 1)]
    for i in range(len(eo[ni])):
        ans[eo[ni][i]] = 3 * (i + 1)
        tmp[3 * (i + 1)] = False
    tmp = [i for i, t in enumerate(tmp) if t is True]
    j = 1
    for i in range(N):
        if ans[i] != -1:
            continue
        ans[i] = tmp[j]
        j += 1

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

Submission status: Accepted

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

N=int(input())
E=[[] for i in range(N+1)]

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

COLOR=[-1]*(N+1)

Q=[1]
COLOR[1]=1

while Q:
    x=Q.pop()
    for to in E[x]:
        if COLOR[to]==-1:
            COLOR[to]=1-COLOR[x]
            Q.append(to)

A1=N//3
A2=N//3
A3=N//3

if N%3==1:
    A1+=1
elif N%3==2:
    A1+=1
    A2+=1

S1=COLOR.count(1)
S2=COLOR.count(0)


SA=A1+A3-A2

if abs(S1-S2)<=SA:
    ANS=[0]*(N+1)
    now1=1
    now2=2
    if S1<S2:
        for i in range(1,N+1):
            if COLOR[i]==1:
                ANS[i]=now2
                now2+=3
            else:
                ANS[i]=now1
                now1+=3

    else:
        for i in range(1,N+1):
            if COLOR[i]==0:
                ANS[i]=now2
                now2+=3
            else:
                ANS[i]=now1
                now1+=3

    now3=3
    for i in range(1,N+1):
        if ANS[i]>N:
            ANS[i]=now3
            now3+=3

    print(*ANS[1:])
    
else:
    ANS=[0]*(N+1)
    now1=1
    now2=2
    now3=3

    if S1<S2:
        for i in range(1,N+1):
            if COLOR[i]==1:
                ANS[i]=now3
                now3+=3
    else:
        for i in range(1,N+1):
            if COLOR[i]==0:
                ANS[i]=now3
                now3+=3

    for i in range(1,N+1):
        if ANS[i]==0:
            if now1<=N:
                ANS[i]=now1
                now1+=3
            elif now2<=N:
                ANS[i]=now2
                now2+=3
            else:
                ANS[i]=now3
                now3+=3

    print(*ANS[1:])