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

Submission status: Wrong Answer

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


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

Cl = [-1]*N
C = [[0], []]
q = [0]
c = 0
Cl[0] = 0
while q:
    qq = []
    c ^= 1
    for p in q:
        for np in graph[p]:
            if Cl[np]  == -1:
                Cl[np] = c
                C[c].append(np)
                qq.append(np)
    q = qq

if len(C[0]) > len(C[1]):
    C = [C[1], C[0]]

c0 = (N+2)//3
c1 = (N+1)//3
c2 = N//3
Co = [[], [], []]
if len(C[0]) < c1:
    R = set(C[0])
    for r in R:
        Co[2].append(r)
    for p in range(N):
        if p in R:
            continue
        elif len(Co[0]) < c0:
            Co[0].append(p)
        elif len(Co[1]) < c1:
            Co[1].append(p)
        else:
            Co[2].append(p)
else:
    R2 = set(C[1])
    for p in range(N):
        if p in R2: # larger
            if len(Co[0]) < c0:
                Co[0].append(p)
            else:
                Co[2].append(p)
        else: # smaller
            if len(Co[1]) < c1:
                Co[1].append(p)
            else:
                Co[2].append(p)

ans = [None]*N
for i, n in enumerate(Co[0]):
    ans[n] = 3*i+1
for i, n in enumerate(Co[1]):
    ans[n] = 3*i+2
for i, n in enumerate(Co[2]):
    ans[n] = 3*i+3


print(*ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

inf=float("inf")

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

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)

def main():
    n=int(input())
    tree=[[] for i in range(n)]
    for _ in range(n-1):
       a,b=map(int,input().split())
       a-=1
       b-=1
       tree[a].append(b)
       tree[b].append(a)
    
    if n%3==0:
        z=n//3
        o=z
        t=z
    elif n%3==1:
        z=n//3
        o=z+1
        t=z
    else:
        z=n//3
        o=z+1
        t=o
    
    depth=[-1]*n
    depth[0]=0
    
    def dfs(i,before=-1):
        for e in tree[i]:
            if depth[e]==-1:
                depth[e]=depth[i]+1
                dfs(e,i)
    
    dfs(0,0)
    if max(depth)<=2:
        ans=list(range(1,n+1))
        print(*ans)
        exit()

    else:
        depth=[i%2 for i in depth]

    cnt_even=depth.count(0)-1
    cnt_odd=n-cnt_even-1

    if cnt_odd > cnt_even :
        a=cnt_odd
        b=cnt_even
        odd=True
    else:
        a=cnt_even
        b=cnt_odd
        odd=False
    

    ans=[3*z]*n
    z-=1
    if odd:
            for l in range(1,n):
                if  depth[l]==0:
                    if t==0:
                        ans[l]=3*z
                        z-=1
                        if z<0:
                            ans=-1
                            break
                    else:
                        ans[l]=3*t-1
                        t-=1
                else:
                    if o==0:
                        ans[l]=3*z
                        z-=1
                        if z<0:
                            ans=-1
                            break
                    else:
                        ans[l]=3*o-2
                        o-=1
    else:
            for l in range(1,n):
                if depth[l]==0:
                    if o==0:
                        ans[l]=3*z
                        z-=1
                        if z<0:
                            ans=-1
                            break
                    else:
                        ans[l]=3*o-2
                        o-=1
                else:
                    if t==0:
                        ans[l]=3*z
                        z-=1
                        if z<0:
                            ans=-1
                            break
                    else:
                        ans[l]=3*t-1
                        t-=1
    if ans==-1:
        print(ans)
    else:
        print(*ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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)

try:
    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)
except:
    try:
        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 numbers3:
                    ansl.append(numbers3.pop())
            else:
                if numbers2:
                    ansl.append(numbers2.pop())
                elif numbers1:
                    ansl.append(numbers1.pop())
                else:
                    raise Exception()
        for a in ansl:
            print(a)
    except:
        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 numbers2:
                    ansl.append(numbers2.pop())
                elif numbers1:
                    ansl.append(numbers1.pop())
                else:
                    raise Exception()
            else:
                if numbers3:
                    ansl.append(numbers3.pop())
        for a in ansl:
            print(a)

Submission status: Wrong Answer

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

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

# 木の直径を求める（隣接リスト、重みなし）
def getDiameterOfTree(adjList):
    numV = len(adjList)

    def bfs(vSt):
        costs = [-1] * numV
        costs[vSt] = cost = 0
        vs = [vSt]
        while vs:
            cost += 1
            v2s = []
            for v in vs:
                for v2 in adjList[v]:
                    if costs[v2] == -1:
                        costs[v2] = cost
                        v2s.append(v2)
            vs = v2s
        maxC = cost-1
        vMaxC = costs.index(maxC)
        return (maxC, vMaxC)

    maxC, v1 = bfs(0)
    maxC, v2 = bfs(v1)
#    return maxC
    return (maxC, v1, v2)

diam, vSt, vEn = getDiameterOfTree(adjL)

def getPath(vSt, vEn):
    path = []
    def dfs(vNow, vPar, vEn):
        if vNow == vEn:
            path.append(vNow)
            return True

        for v2 in adjL[vNow]:
            if v2 != vPar:
                if dfs(v2, vNow, vEn):
                    path.append(vNow)
                    return True

    dfs(vSt, -1, vEn)
    return path

if diam <= 4:
    path = getPath(vSt, vEn)
    vRoot = path[diam//2]

    def dfs(vNow, vPar, depth):
        pars[vNow] = vPar
        depths[vNow] = depth
        for v2 in adjL[vNow]:
            if v2 != vPar:
                dfs(v2, vNow, depth+1)
    
    pars = [-1] * N
    depths = [-1] * N
    dfs(vRoot, -1, 0)

    numVs = [0] * 3
    for v in range(N):
        numVs[depths[v]%3] += 1

    D = 1 if numVs[1] >= numVs[2] else 2
    Pss = [[] for _ in range(3)]
    for i in range(1, N+1):
        Pss[i%3].append(i)
    Ps = Pss[1] + Pss[0] + Pss[2]

    anss = [-1] * N
    anss[vRoot] = Ps[0]
    iP = 1
    for v in range(N):
        if v == vRoot: continue
        if depths[v] == D:
            anss[v] = Ps[iP]
            iP += 1
    for v in range(N):
        if v == vRoot: continue
        if depths[v] == 3-D:
            anss[v] = Ps[iP]
            iP += 1
    print(' '.join(map(str, anss)))

else:
    if diam != N-1:
        print(-1)
    else:
        path = getPath(vSt, vEn)
        anss = [-1] * N
        for P, v in enumerate(path, 1):
            anss[v] = P
        print(' '.join(map(str, anss)))

Submission status: Wrong Answer

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)

try:
    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)
except:
    try:
        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 numbers3:
                    ansl.append(numbers3.pop())
            else:
                if numbers2:
                    ansl.append(numbers2.pop())
                elif numbers1:
                    ansl.append(numbers1.pop())
                else:
                    ansl.append(numbers3.pop())
        for a in ansl:
            print(a)
    except:
        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 numbers2:
                    ansl.append(numbers2.pop())
                elif numbers1:
                    ansl.append(numbers1.pop())
                else:
                    ansl.append(numbers3.pop())
            else:
                if numbers3:
                    ansl.append(numbers3.pop())
        for a in ansl:
            print(a)

Submission status: Wrong Answer

Solution code:
from collections import deque


n = int(input())

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


root = 0
visited = [-1] * n
def dfs(root):
    q = deque([root])
    visited[root] = 0
    while q:
        v = q.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v] != -1:
                continue
            else:
                visited[nxt_v] = (visited[v] + 1) % 2
                q.append(nxt_v)
dfs(0)
cnt0 = 0
cnt1 = 0
for i in range(n):
    if visited[i] == 0:
        cnt0 += 1
    else:
        cnt1 += 1

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

set1 = set()
set2 = set()
set3 = set()
for i in range(1, n + 1):
    if i % 3 == 0:
        set3.add(i)
    elif i % 3 == 1:
        set1.add(i)
    elif i % 3 == 2:
        set2.add(i)
        
if cnt0 <= num3:
    exit()
    for i in range(n):
        if visited[i] == 0:
            ans[i] = pop.set3()
        else:
            if set1:
                ans[i] = pop.set1() 
            elif set2:
                ans[i] = pop.set2()         
            elif set3:
                ans[i] = pop.set3()  

elif cnt1 <= num3:
    exit()
    for i in range(n):
        if visited[i] == 1:
            ans[i] = pop.set3()
        else:
            if set1:
                ans[i] = pop.set1() 
            elif set2:
                ans[i] = pop.set2()         
            elif set3:
                ans[i] = pop.set3()  
else:
    num147 = 0
    num258 = 0
    num369 = 0
    for i in range(n):
        if visited[i] == 0:
            num = num147 * 3 + 1
            if num > n:
                num = num369 * 3 + 3
                ans[i] = num
                if num > n:
                    print(-1)
                    exit()
                set3.remove(num)
                num369 += 1
                continue
            ans[i] = num # 1, 4, 7, 10, ...
            set1.remove(num)
            num147 += 1
        else:
            num = num258 * 3 + 2 
            if num > n:
                num = num369 * 3 + 3
                if num > n:
                    print(-1)
                    exit()
                ans[i] = num
                set3.remove(num)
                num369 += 1
                continue
            ans[i] = num # 2, 5, 8, 11, ...
            set2.remove(num)
            num258 += 1
     
    for i in range(n):
        if ans[i] == 0:
            if set1:
                ans[i] = set1.pop()
            elif set2:
                ans[i] = set2.pop()
            elif set3:
                ans[i] = set3.pop()
print(*ans)

Submission status: Wrong Answer

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

ans = []
ans_ar = [0] * (n+1)


def bfs(start, W):
    move = [0] * (n + 1)
    work_q = deque([])
    visited = set()
    work_q.append(start)
    visited.add(start)
    while work_q:
        here = work_q.popleft()
        for ii in W[here]:
            if ii not in visited:
                work_q.append(ii)
                visited.add(ii)
                move[ii] = move[here] + 1
    return move


for i in range(1, n+1):
    dia = bfs(i, eda_array)
    for j in range(i, n+1):
        if dia[j] == 3:
            ans.append((i, j))

visited = set()
used = set()

for i in ans:
    st, go = i[0], i[1]
    num = 1
    if st not in visited and go not in visited:
        visited.add(st)
        ans_ar[st] = num
        used.add(num)
        num += 1
        visited.add(go)
        ans_ar[go] = num
        used.add(num)
        num += 1
    elif go not in visited:
        for j in range(1, n+1):
            if (ans_ar[st] + j) % 3 == 0 and j not in used:
                ans_ar[go] = j
                used.add(j)
here = 1
for i in range(1, n+1):
    if i not in used:
        nums = i
        for j in range(here, n+1):
            if ans_ar[j] == 0:
                ans_ar[j] = nums
                here = j
                break
print(*ans_ar[1::])

Submission status: Wrong Answer

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

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()
        # self.doubling()

    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 = TREE(es).depth

ans = [0]*n

ans = [1 if d % 2 == 0 else 2 for d in depth]

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


flg = 1

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:
            flg = -1
            break
    else:
        if two > 0:
            ans[i] = two*3 - 1
            two -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            flg = -1
            break

if flg == 1:
    print(*ans, sep=' ')
    exit()

flg2 = 1


zero = one = two = n // 3


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

if flg == 1:
    print(*ans, sep=' ')
    exit()

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
for i in range(1, n+1):
    nums[i%3].append(i)

ans = [0 for _ in range(n)]
def dfs(idx, pre_3, pre_2, pre_1):
    if pre_1 == -1:
        if pre_1 % 3 == 2 and len(nums[1]) > 0:
            out = nums[1].pop()
        elif pre_1 % 3 == 1 and len(nums[2]) > 0:
            out = nums[2].pop()
        else:
            out = nums[0].pop()
    else:
        if pre_1 % 3 != 0:
            if pre_1 % 3 == 2 and len(nums[1]) > 0:
                out = nums[1].pop()
            elif pre_1 % 3 == 1 and len(nums[2]) > 0:
                out = nums[2].pop()
            else:
                if len(nums[0]) > 0:
                    out = nums[0].pop()
                else:
                    print(-1)
                    exit()
        else:
            if len(nums[1]) > 0:
                out = nums[1].pop()
            elif len(nums[2]) > 0:
                out = nums[2].pop()
            else:
                if len(nums[0]) > 0:
                    out = nums[0].pop()
                else:
                    print(-1)
                    exit()
    ans[idx-1] = out
    for k in edges[idx].keys():
        if ans[k-1] == 0:
            dfs(k, pre_2, pre_1, out)

for i in range(1, n+1):
    if len(edges[i]) == 1:
        dfs(i, -1, -1, -1)
        break

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

Submission status: Wrong Answer

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

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()
        # self.doubling()

    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 = TREE(es).depth

ans = [0]*n

ans = [1 if d % 2 == 0 else 2 for d in depth]

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


flg = 1

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:
            flg = -1
            break
    else:
        if two > 0:
            ans[i] = two*3 - 1
            two -= 1
        elif zero > 0:
            ans[i] = zero*3
            zero -= 1
        else:
            flg = -1
            break

if flg == 1:
    print(*ans, sep='')
    exit()

flg2 = 1


zero = one = two = n // 3


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

if flg == 1:
    print(*ans, sep='')
    exit()

print(-1)

Submission status: Wrong Answer

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

def main():
    n=int(input())
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
    Depth=[-1]*n
    Depth[0]=0
    q=deque()
    q.append(0)
    while q:
        fr=q.popleft()
        for to in Edges[fr]:
            if Depth[to]==-1:
                Depth[to]=Depth[fr]+1
                q.append(to)
    Group=[[] for _ in range(2)]
    for i in range(n):
        Group[Depth[i]%2].append(i)
    #print(Depth,Group)
    l_even,l_odd=len(Group[0]),len(Group[1])
    Ans=[0]*n
    Used=[False]*(n+1)
    if l_even<=l_odd:
        if l_even<n//3:
            tmp_3=3
            tmp_others=1
            for i in range(n):
                if Depth[i]%2==1:
                    continue
                Ans[i]=tmp_3
                Used[tmp_3]=True
                tmp_3+=3
            for i in range(n):
                if Depth[i]%2==0:
                    continue
                while Used[tmp_others]:
                        tmp_others+=1
                Ans[i]=tmp_others
                Used[tmp_others]=True
            print(*Ans)
            exit()
    else:
        if l_odd<n//3:
            tmp_3=3
            tmp_others=1
            for i in range(n):
                if Depth[i]%2==0:
                    continue
                Ans[i]=tmp_3
                Used[tmp_3]=True
                tmp_3+=3
            for i in range(n):
                if Depth[i]%2==1:
                    continue
                while Used[tmp_others]:
                        tmp_others+=1
                Ans[i]=tmp_others
                Used[tmp_others]=True
            print(*Ans)
            exit()
    tmp_odd,tmp_even,tmp_others=1,2,3
    for i in range(n):
        if Depth[i]%2==1:
            if tmp_odd<=n:
                Ans[i]=tmp_odd
                tmp_odd+=3
            else:
                Ans[i]=tmp_others
                tmp_others+=3
        else:
            if tmp_even<=n:
                Ans[i]=tmp_even
                tmp_even+=3
            else:
                Ans[i]=tmp_others
                tmp_others+=3
    print(*Ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import numpy as np
def resolve():
    N = int(input())
    ab = [list(map(int, input().split())) for _ in range(N-1)]

    adj = [[] for _ in range(N)]
    for c in ab:
        a = c[0]-1
        b = c[1]-1
        adj[a].append(b)
        adj[b].append(a)

    three = [[] for _ in range(N)]
    pairs = set()

    # 距離3の頂点を探す
    INF = 9999999
    for i in range(N):
        reached = [INF] * N

        def bfs():
            que = deque([])
            que.append(i)
            reached[i] = 0

            while len(que) > 0:
                p = que.pop()
                #print(p)
                if reached[p] < 3:
                    for c in adj[p]:
                        if reached[c] == INF:
                            que.append(c)
                            reached[c] = reached[p] + 1
                            if reached[c] == 3:
                                three[i].append(c)
                                pairs.add((i, c))
        bfs()

    hub = list(map(len, three))
    x = np.argsort(hub)[::-1]

    def check(a, b):
        if (a + b) % 3 == 0 or (a * b) % 3 == 0:
            return True
        return False

    anser = list(range(1, N+1))
    good = [3] * (N//3)
    for i, g in enumerate(good):
        tmp = anser[x[i]]
        anser[x[i]] = g
        anser[g-1] = tmp

    print(' '.join(map(str, anser)))

if __name__ == "__main__":
    resolve()