Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and Vertex b_i.

Takahashi loves the number 3. He is seeking a permutation p_1, p_2, \ldots , p_N of integers from 1 to N satisfying the following condition:

For every pair of vertices (i, j), if the distance between Vertex i and Vertex j is 3, the sum or product of p_i and p_j is a multiple of 3.

Here the distance between Vertex i and Vertex j is the number of edges contained in the shortest path from Vertex i to Vertex j.

Help Takahashi by finding a permutation that satisfies the condition.

Constraints

2\leq N\leq 2\times 10^5

1\leq a_i, b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

If no permutation satisfies the condition, print -1.

Otherwise, print a permutation satisfying the condition, with space in between.
If there are multiple solutions, you can print any of them.

Sample Input 1

5
1 2
1 3
3 4
3 5

Sample Output 1

1 2 5 4 3 

The distance between two vertices is 3 for the two pairs (2, 4) and (2, 5).

p_2 + p_4 = 6

p_2\times p_5 = 6

Thus, this permutation satisfies the condition.



Sample input:
5
1 2
1 3
3 4
3 5


Sample output:
1 2 5 4 3

Submission status: Wrong Answer

Solution code:
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()
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:
  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:
      if len(b)!=0:
        ans[i-1]=b.pop()
      elif len(c)!=0:
        ans[i-1]=c.pop()
        
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for k in range(1, N + 1):
    if k % 3 == 0:
        mod0.append(k)
    elif k % 3 == 1:
        mod1.append(k)
    else:
        mod2.append(k)

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


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N / 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N / 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        if dist[i] % 2 == 0:
            if mod2:
                node_p[i] = mod2.pop()
            elif mod0:
                node_p[i] = mod0.pop()
            else:
                node_p[i] = mod1.pop()
        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod0:
                node_p[i] = mod0.pop()
            else:
                node_p[i] = mod2.pop()

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for k in range(1, N + 1):
    modfit(k)

print()

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import Counter

N = int(input())
T = [set() for x in range(N)]
search = [0] * N
isOdd = [0] * N

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

Q = deque()

search[0] = 1
Q.append(0)
dlen = 1
while dlen != 0:
    q = Q.pop()
    dlen -= 1
    for aa in T[q]:
        if search[aa]:
            continue
        search[aa] = 1
        Q.append(aa)
        dlen += 1
        isOdd[aa] = isOdd[q] ^ 1

C = Counter(isOdd)

a = []
if C[0] <= N // 3:
    a = lambda x:[-1,0,1][x%3]
elif C[1] <= N // 3:
    a = lambda x:[1,0,-1][x%3]
else:
    a = lambda x:[0,-1,1][x%3]

d = deque(sorted(range(1,N+1),key=a))
print(*[d.pop() if isOdd[x] == 0 else d.popleft() for x in range(N)],sep=" ")

Submission status: Wrong Answer

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()
  for u in edge[v]:
    if parent[u] != 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: Wrong Answer

Solution code:
from collections import deque
from collections import Counter

N = int(input())
T = [set() for x in range(N)]
search = [0] * N
isOdd = [0] * N

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

Q = deque()

search[0] = 1
Q.append(0)
dlen = 1
while dlen != 0:
    q = Q.pop()
    dlen -= 1
    for aa in T[q]:
        if search[aa]:
            continue
        search[aa] = 1
        Q.append(aa)
        dlen += 1
        isOdd[aa] = isOdd[q] ^ 1

C = Counter(isOdd)

a = []
if C[0] <= N // 3:
    a = lambda x:[1,0,-1][x%3]
elif C[1] <= N // 3:
    a = lambda x:[-1,0,1][x%3]
else:
    a = lambda x:[0,-1,1][x%3]

d = deque(sorted(range(1,N+1),key=a))
print(*[d.pop() if isOdd[x] else d.popleft() for x in range(N)],sep=" ")

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)

N = int(stdin.readline())
ab = [list(map(int, stdin.readline().split())) for i in range(N - 1)]

# 1 index
graph = [[] for i in range(N + 1)]

for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

q = deque([])

mod0 = deque([])
mod1 = deque([])
mod2 = deque([])

for k in range(1, N + 1):
    if k % 3 == 0:
        mod0.append(k)
    elif k % 3 == 1:
        mod1.append(k)
    else:
        mod2.append(k)

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


def bfs(start):
    q.append(start)
    dist[start] = 0

    while q:
        now = q.popleft()

        for node in graph[now]:
            if dist[node] != -1:
                continue
            else:
                dist[node] = dist[now] + 1
                q.append(node)


node_p = [0] * (N + 1)


def modfit(i):
    if even <= N / 3:
        if dist[i] % 2 == 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    elif odd <= N / 3:
        if dist[i] % 2 != 0:
            node_p[i] = mod0.pop()

        else:
            if mod1:
                node_p[i] = mod1.pop()
            elif mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()

    else:
        exit()
        if dist[i] % 2 == 0:
            if mod2:
                node_p[i] = mod2.pop()
            else:
                node_p[i] = mod0.pop()
        else:
            if mod1:
                node_p[i] = mod1.pop()
            else:
                node_p[i] = mod0.pop()

    print(node_p[i], end=" ")


odd = 0
even = 0

bfs(1)

for d in dist:
    if d % 2 == 0:
        even += 1
    else:
        odd += 1

for k in range(1, N + 1):
    modfit(k)

print()

Submission status: Wrong Answer

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
            else:
                ans[cur] = mod[2]
                mod[2] += 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: Wrong Answer

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, 0, 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(even) <= 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: Wrong Answer

Solution code:
from collections import deque

N = int(input())
T = [deque() for _ in range(N+1)]
seen = [False]*(N+1)
a, b = map(int, input().split())
a, b = min(a, b), max(a, b)
T[a].append(b)
seen[a] = True
seen[b] = True
for _ in range(N-2):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  if not seen[a]:
    T[b].append(a)
  else:
    T[a].append(b)
  seen[a] = True
  seen[b] = True
q = deque([[1, 0]])
even = deque()
odd = deque()
dist = 0
while q:
  cur, dist = q.pop()
  if dist % 2 == 0:
    even.append(cur)
  else:
    odd.append(cur)
  for c in T[cur]:
    q.append([c, dist+1])
if len(even) < 1 or len(odd) < 2:
  print(-1)
else:
  ans = [0]*(N+1)
  threes = deque(list(range(3, N+1, 3)))
  if len(even) > N//3 and len(odd) > N//3:
    i = 0
    while even and 3*i+1 <= N:
      e = even.pop()
      ans[e] = 3*i+1
      i += 1
    if even:
      while even:
        e = even.pop()
        thr = threes.pop()
        ans[e] = thr
    i = 0
    while odd and 3*i+2 <= N:
      o = odd.pop()
      ans[o] = 3*i+2
      i += 1
    if odd:
      while odd:
        o = odd.pop()
        thr = threes.pop()
        ans[o] = thr
  elif len(even) <= N//3:
    while even and threes:
      e = even.pop()
      thr = threes.pop()
      ans[e] = thr
    while odd and threes:
      o = odd.pop()
      thr = threes.pop()
      ans[o] = thr
    i = 0
    while odd and i*3+1 <= N:
      o = odd.pop()
      ans[o] = i * 3 +1
      i += 1
    i = 0
    while odd and i*3+2 <= N:
      o = odd.pop()
      ans[o] = i * 3 + 2
      i += 1
  else:
    while odd and threes:
      e = odd.pop()
      thr = threes.pop()
      ans[e] = thr
    while even and threes:
      o = even.pop()
      thr = threes.pop()
      ans[o] = thr
    i = 0
    while even and i*3+1 <= N:
      o = even.pop()
      ans[o] = i * 3 +1
      i += 1
    i = 0
    while even and i*3+2 <= N:
      o = even.pop()
      ans[o] = i * 3 + 2
      i += 1
  print(" ".join([str(a) for a in ans[1:]]))

Submission status: Wrong Answer

Solution code:
import re
import heapq
n=int(input())
p=[-1 for _ in range(n)]
nonuse_num=[3,1,2]
heapq.heapify(nonuse_num)
for i in range(n-1):
    a,b=map(int,input().split())
    if(p[a-1]==-1 and p[b-1]==-1):
        now_count=heapq.heappop(nonuse_num)
        p[a-1]=now_count
        p[b-1]=now_count+3 if now_count+3<=n else -1
        heapq.heappush(nonuse_num, now_count+6)
#    print(p,nonuse_num)

for i in range(n):
    if(p[i]==-1):
        p[i]=heapq.heappop(nonuse_num)
        heapq.heappush(nonuse_num,p[i]+3)

print(re.sub('[\[\]\,]', '', str(p)))

Submission status: Wrong Answer

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
    print(oddslst,evenlst)
    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: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import random
isdebug=0
if isdebug==0:
    N=int(input())
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
else:
    N=20*10**4
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=random.randrange(i+1),i+1
        G[a].append(b)
        G[b].append(a)
dist=[-1 for i in range(N)]
X=[]
Y=[]
q=deque([0])
dist[0]=0
while(len(q)>0):
    r=q.popleft()
    if dist[r]%2==0:
        X.append(r)
    else:
        Y.append(r)
    for p in G[r]:
        if dist[p]==-1:
            dist[p]=dist[r]+1
            q.append(p)
P=[0 for i in range(N)]
que=deque([])
if min(len(X),len(Y))<=N//3:
    for i in range(N):
        if i%3==0:
            que.appendleft(i)
        else:
            que.append(i)
    if len(X)>len(Y):
        for i in X:
            t=que.popleft()
            P[i]=t+1
        for i in Y:
            t=que.pop()
            P[i]=t+1
    else:
        for i in Y:
            t=que.popleft()
            P[i]=t+1
        for i in X:
            t=que.pop()
            P[i]=t+1
else:
    for i in range(N):
        if i%3==0:
            que.appendleft(i)
    for i in range(N):
        if i%3==1:
            que.appendleft(i)
        elif i%3==2:
            que.append(i)
    for i in X:
        t=que.popleft()
        P[i]=t+1
    for i in Y:
        t=que.pop()
        P[i]=t+1
print(*P)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
T = [deque() for _ in range(N+1)]
seen = [False]*(N+1)
a, b = map(int, input().split())
a, b = min(a, b), max(a, b)
T[a].append(b)
seen[a] = True
seen[b] = True
for _ in range(N-2):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  if not seen[a]:
    T[b].append(a)
  else:
    T[a].append(b)
  seen[a] = True
  seen[b] = True
q = deque([[1, 0]])
even = deque()
odd = deque()
dist = 0
D = 0
while q:
  cur, dist = q.pop()
  D = max(dist, D)
  if dist % 2 == 0:
    even.append(cur)
  else:
    odd.append(cur)
  for c in T[cur]:
    q.append([c, dist+1])
if len(even) < 1 or len(odd) < 1 or D < 3:
  print(-1)
else:
  ans = [0]*(N+1)
  threes = deque(list(range(3, N+1, 3)))
  if len(even) > N//3 and len(odd) > N//3:
    i = 0
    while even and 3*i+1 <= N:
      e = even.pop()
      ans[e] = 3*i+1
      i += 1
    if even:
      while even:
        e = even.pop()
        thr = threes.pop()
        ans[e] = thr
    i = 0
    while odd and 3*i+2 <= N:
      o = odd.pop()
      ans[o] = 3*i+2
      i += 1
    if odd:
      while odd:
        o = odd.pop()
        thr = threes.pop()
        ans[o] = thr
  elif len(even) <= N//3:
    while even and threes:
      e = even.pop()
      thr = threes.pop()
      ans[e] = thr
    while odd and threes:
      o = odd.pop()
      thr = threes.pop()
      ans[o] = thr
    i = 0
    while odd and i*3+1 <= N:
      o = odd.pop()
      ans[o] = i * 3 +1
      i += 1
    i = 0
    while odd and i*3+2 <= N:
      o = odd.pop()
      ans[o] = i * 3 + 2
      i += 1
  else:
    while odd and threes:
      e = odd.pop()
      thr = threes.pop()
      ans[e] = thr
    while even and threes:
      o = even.pop()
      thr = threes.pop()
      ans[o] = thr
    i = 0
    while even and i*3+1 <= N:
      o = even.pop()
      ans[o] = i * 3 +1
      i += 1
    i = 0
    while even and i*3+2 <= N:
      o = even.pop()
      ans[o] = i * 3 + 2
      i += 1
  print(" ".join([str(a) for a in ans[1:]]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
adjacent_list = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set()
inf = 10**9
dist = [inf for i in range(n+1)]
def dfs(node):
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dist[i] = dist[node]+1
            dfs(i)
dist[1] = 0
rem_1 = [i+1 for i in range(n) if (i+1) % 3 == 1]
rem_2 = [i+1 for i in range(n) if (i+1) % 3 == 2]
rem_0 = [i+1 for i in range(n) if (i+1) % 3 == 0]
index_0 = 0
index_1 = 0
index_2 = 0
dfs(1)
ans = []
count_even = 0
count_odd = 0
for i in range(1,len(dist)):
    if dist[i] % 2 == 0:
        count_even += 1
    else:
        count_odd += 1

#場合分け
if count_even > n/3 and count_odd > n/3:
    #この場合、普通にやる
    for i in range(1,len(dist)):
        if dist[i] % 2 == 1:
            if index_2 < len(rem_2):
                ans.append(rem_2[index_2])
                index_2 += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
        else:
            if index_1 < len(rem_1):
                ans.append(rem_1[index_1])
                index_1 += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
elif count_even <= n/3:
    #1からの距離が偶数のところが全体の1/3を閉めない場合
    #そこに全部3の倍数を入れてしまえば、題意を満たす
    li = rem_1 + rem_2
    print(li)
    index = 0
    for i in range(1,len(dist)):
        if dist[i] % 2 == 0:
            ans.append(rem_0[index_0])
            index_0 += 1
        else:
            if index < len(li):
                ans.append(li[index])
                index += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
else:
    ##1からの距離が奇数のところが全体の1/3を閉めない場合
    #そこに全部3の倍数を入れてしまえば、題意を満たす
    li = rem_1 + rem_2
    index = 0
    for i in range(1,len(dist)):
        if dist[i] % 2 == 1:
            ans.append(rem_0[index_0])
            index_0 += 1
        else:
            if index < len(li):
                ans.append(li[index])
                index += 1
            else:
                ans.append(rem_0[index_0])
                index_0 += 1
for i in ans:
    print(i, end=" ")

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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


def dfs(v, step):
    global node0, node1
    if (step % 3) & 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)
if node0 > num0 and node1 > num0:
    cur = 0
    while num1 > 0:
        if color[cur] == 1:
            ans[cur] = 3 * num1 - 2
            num1 -= 1
        cur += 1
    cur = 0
    while num2 > 0:
        if color[cur] == 0:
            ans[cur] = 3 * num2 - 1
            num2 -= 1
        cur += 1
elif node0 <= num0:
    cur = 0
    while node0 > 0:
        if color[cur] == 0:
            ans[cur] = 3 * num0
            num0 -= 1
            node0 -= 1
        cur += 1
else:
    cur = 0
    while node1 > 0:
        if color[cur] == 1:
            ans[cur] = 3 * num0
            num0 -= 1
            node1 -= 1
        cur += 1

cur = 0
while num0 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num0
        num0 -= 1
    cur += 1
while num1 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num1 - 2
        num1 -= 1
    cur += 1
while num2 > 0:
    if ans[cur] is None:
        ans[cur] = 3 * num2 - 1
        num2 -= 1
    cur += 1


print(*ans)

Submission status: Wrong Answer

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)
elif len(eo[0]) <= N // 3:
    for i in range(len(eo[0])):
        ans[eo[0][i]] = 3 * (i + 1)
    j = 0
    for i in range(N):
        if ans[i] != -1:
            continue
        ans[i] = eo[1][j]
        j += 1
elif len(eo[1]) <= N // 3:
    for i in range(len(eo[1])):
        ans[eo[1][i]] = 3 * (i + 1)
    j = 0
    for i in range(N):
        if ans[i] != -1:
            continue
        ans[i] = eo[0][j]
        j += 1

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