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
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)
C=[-1]*n
C2=[-1]*n
def ch(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C[x]=0
    return C[x]
  else:
    for e in edge[x]:
      if e==prv[x]:
        continue
      else:
        ret+=1
    C[x]=ret
    return C[x]
def ch2(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C2[x]=0
    return C2[x]
  else:
    for e in edge[x]:
      if e==prv[x]:
        continue
      else:
        ret+=C[e]
    C2[x]=ret
    return C2[x]
for i in range(n):
  ch(i)
for i in range(n):
  ch2(i)

TH=[0]*n
for i in range(n):
  if i==0:
    cur=0
  elif depth[i]==1:
    cur=C2[prv[i]]-C[i]
  else:
    cur=C2[prv[i]]+C[prv[prv[i]]]-C[i]-1
  if depth[i]>=3:
    cur+=1
  for e in edge[i]:
    if e==prv[i]:
      continue
    else:
      cur+=C2[e]
  TH[i]=cur
TH2=[0]*n
for i in range(n):
  TH2[i]=TH[i]*(10**6)+i
TH2.sort(reverse=True)
Ans=[0]*n
ct1,ct2,ct3=0,0,0
for i in range(3,n,3):
  if TH[TH2[i//3-1]%(10**6)]>4:
    Ans[TH2[i//3-1]%(10**6)]=i
    ct3+=1
for i in range(n):
  if Ans[i]!=0:
    continue
  else:
    if depth[i]%2==0:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      elif 3*ct3+3<=n:
        Ans[i]=3*ct3+3
        ct3+=1
      else:
        Ans[i]=3*ct2+2
        ct2+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      elif 3*ct3+3<=n:
        Ans[i]=3*ct3+3
        ct3+=1
      else:
        Ans[i]=3*ct1+1
        ct1+=1
if max(Ans)>n:
  print(-1)
else:
  print(*Ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N-1)]
print(*([3]*N))

Submission status: Wrong Answer

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

N = int(input())

p = [[] for _ in range(N)]
c = [[] for _ in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    p[b].append(a)
    c[a].append(b)

three = []
for i in range(N):
    if not p[i]:
        continue
    parent = p[i][0]
    for j in c[parent]:
        if i == j:
            continue
        for k in c[j]:
            three.append((i, k))

ans = [0] * N
idx = 1
used = set()
for l, r in three:
    if l > r:
        l, r = r, l
    if ans[l] == 0:
        ans[l] = 3 * idx
        used.add(3 * idx)


n = 1
for i in range(N):
    if ans[i] > 0:
        continue
    if n in used:
        n += 1
    ans[i] = n
    n += 1

for a in ans:
    print(a)

Submission status: Wrong Answer

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

def make_tree(graph, x, pre_lst, tree):
    if pre_lst[2] != -1:
        tree[x].append(pre_lst[2])
        tree[pre_lst[2]].append(x)
    for nex in graph[x]:
        if nex == pre_lst[0]:
            continue
        tree = make_tree(graph, nex, [x, pre_lst[0], pre_lst[1]], tree)
    return tree

def solve(tree, n):
    lst_0 = [i for i in range(3, n+1, 3)]
    lst_1 = [i for i in range(1, n+1, 3)]
    lst_2 = [i for i in range(2, n+1, 3)]
    cnt_0, cnt_1, cnt_2 = 0, 0, 0
    f = [True]*n
    ans = [None]*n
    for i in range(n):
        if f[i]:
            q = queue.Queue()
            q.put(i)
            f[i] = False
            if cnt_2 < len(lst_2):
                ans[i] = lst_2[cnt_2]
                cnt_2 += 1
            elif cnt_1 < len(lst_1):
                ans[i] = lst_1[cnt_1]
                cnt_1 += 1
            elif cnt_0 < len(lst_0):
                ans[i] = lst_0[cnt_0]
                cnt_0 += 1
            while not q.empty():
                target = q.get()
                for v in tree[target]:
                    if f[v]:
                        f[v] = False
                        if ans[target] % 3 == 2 and cnt_1 < len(lst_1):
                            ans[v] = lst_1[cnt_1]
                            cnt_1 += 1
                            q.put(v)
                        elif ans[target] % 3 == 1 and cnt_2 < len(lst_2):
                            ans[v] = lst_2[cnt_2]
                            cnt_2 += 1
                            q.put(v)
                        elif ans[target] % 3 == 0:
                            if cnt_2 < len(lst_2):
                                ans[v] = lst_2[cnt_2]
                                cnt_2 += 1
                                q.put(v)
                            elif cnt_1 < len(lst_1):
                                ans[v] = lst_1[cnt_1]
                                cnt_1 += 1
                                q.put(v)
                            else:
                                ans[v] = lst_0[cnt_0]
                                cnt_0 += 1
                                q.put(v)
                        elif cnt_0 < len(lst_0):
                            ans[v] = lst_0[cnt_0]
                            cnt_0 += 1
                            q.put(v)
                        else:
                            print("-1")
                            sys.exit()
    for v in ans:
        print(v, end=" ")

def main():
    n = int(input())
    tree = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[b].append(a)
        tree[a].append(b)
    top = -1
    for i in range(n):
        if len(tree[i]) == 1:
            top = i
            break
    new_tree = [[] for _ in range(n)]
    for v in tree[top]:
        new_tree = make_tree(tree, v, [top, -1, -1], new_tree)
    solve(new_tree, n)

if __name__ == "__main__":
    main()

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 p in range(N):
        if p in R:
            Co[2].append(p)
        elif len(Co[0]) < c0:
            Co[0].append(p)
        elif len(Co[1]) < c1:
            Co[1].append(p)
        else:
            Co[2].append(p)
else:
    R1 = set(C[0])
    R2 = set(C[1])
    for p in range(N):
        if p in R2:
            if len(Co[0]) < c0:
                Co[0].append(p)
            else:
                Co[2].append(p)
        else:
            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
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)]

def bfs(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)

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    Par = [0 for _ in range(N)]
    Son = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
    Dist = [0] * N
    q = deque()
    q.append((0, 0, 0)) #(now, pre, dist)
    modCount = [N // 3, N // 3, N // 3]
    if N % 3 == 1: modCount[1] += 1
    elif N % 3 == 2:
        modCount[1] += 1
        modCount[2] += 1
    modIndex = [0, 0, 0]
    search = deque()
    while q:
        nowNode, preNode, dist = q.popleft()
        Dist[nowNode] = dist
        Par[nowNode] = preNode
        Son[preNode].append(nowNode)
        search.append(nowNode)
        for nextNode in Edge[nowNode]:
            if nextNode != preNode: q.append((nextNode, nowNode, dist + 1))

    Ans = [-1] * N
    while search:
        nowNode = search.popleft()
        dType = Dist[nowNode] % 2
        if modIndex[dType + 1] < modCount[dType + 1]: 
            Ans[nowNode] = 3 * modIndex[dType + 1] + dType + 1
            modIndex[dType + 1] += 1
        elif modIndex[0] < modCount[0]:
            Ans[nowNode] = 3 * modIndex[0] + 3
            modIndex[0] += 1
        else:
            if Dist[nowNode] < 2:
                Ans[nowNode] = 3 * modIndex[dType ^ 1] + (dType ^ 1) + 1
                modIndex[dType ^ 1] += 1
            else:
                f = Par[nowNode]
                g = Par[f]
                if Ans[g] % 3 == dType ^ 1:
                    print(-1)
                    break
                else:
                    possible = True
                    for u in Son[g]:
                        if u != f and Ans[u] % 3 == dType ^ 1 + 1:
                            possible = False
                            break
                    if possible:
                        Ans[nowNode] = 3 * modIndex[dType ^ 1] + (dType ^ 1) + 1
                        modIndex[dType ^ 1] += 1
                    else:
                        print(-1)
                        break
    else:
        print(" ".join(map(str, Ans)))

    return 0

if __name__ == "__main__":
    solve()

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)]
for a,b in ab:
  l[a-1].append(b-1)
  l[b-1].append(a-1)
  
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
e_dict = {x:[] for x in range(1,n+1)}

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

three_pair = {x:[] for x in range(1,n+1)}
three_num = {x:[] for x in range(1,n+1)}

for i in range(1,n+1):
  visited = set([i])
  vertex = e_dict[i]
  visited = visited | set(vertex)
  
  unvisited = []
  for _ in range(2):
    unvisited = []
    for j1 in vertex:
      for j2 in e_dict[j1]:
        if j2 not in visited:
          unvisited.append(j2)
          visited.add(j2)
    vertex = unvisited
        
  three_pair[i] = unvisited
  three_num[i] = len(unvisited)

##
done_ver = []
done_num = []
not_done_num = []
done_num_dict = {}

ans = [0 for i in range(n)]
count = 1
count2  = 1
for k,v in three_pair.items():
  if len(v) <= 1:
    not_done_num.append(k)
    continue
  if len(v) >= 2:
    done_ver.append(k)
    
    if count *3 < n:
      num = 3 * count
      count += 1
      
    else:
      num = count2
      count2 +=1
      if count2%3 == 0:
        count2 += 1
  
    done_num.append(num)
    done_num_dict[num] = k

for i in range(0,n):
  if i+1 in done_num:
    ans[i] = done_num_dict[i+1]
  else:
    ans[i] = not_done_num.pop(0)

for a in ans:
  print(str(a)+' ',end='')

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for _ 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)
d = [-1] * n
s = [0]
d[0] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            d[node] = (d[p] + 1) % 2
            s.append(node)
a = d.count(0)
b = d.count(1)
if a > b:
    tmp = 0
else:
    tmp = 1
a, b = max(a, b), min(a, b)
ans = [0] * n
if a - b <= n // 3:
    p = 1
    q = 2
    t = 3
    for i in range(n):
        if d[i] == tmp:
            if t <= n:
                ans[i] = t
                t += 3
            else:
                ans[i] = p
                p += 3
        else:
            ans[i] = q
            q += 3
else:
    t = 3
    k = 1
    for i in range(n):
        if d[i] == tmp:
            ans[i] = k
            k += 1
            if k % 3 == 0:
                k += 1
        else:
            ans[i] = t
            t += 3
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

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

s = n * 398*12093 + 123129389748
s %= n
s += 1
ans = [-1]*(n+1)
q = [s]
ans[s] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if ans[next] == -1:
            q.append(next)
            ans[next] = (ans[now]+1)%2


zero = 0
one = 0
two = 0
for i in range(1, n+1):
    if ans[i] == 0:
        ans[i] = zero*3+1
        zero += 1
    elif ans[i] == 1:
        ans[i] = one*3+2
        one += 1

three = 0
for i in range(1, n+1):
    if ans[i] > n:
        ans[i] = three*3+3
        three += 1
print(" ".join(map(str, ans[1:])))

Submission status: Wrong Answer

Solution code:
from collections import deque
import random
def main():
    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)
    H=[[] for i in range(N)]
    q=deque([])
    q_append=q.append
    for i in range(N):
        q_append(i)
        dist=dict()
        dist[i]=0
        while(len(q)>0):
            r=q.popleft()
            for p in G[r]:
                if p in dist:
                    continue
                dist[p]=dist[r]+1
                if dist[p]<3:
                    q_append(p)
                else:
                    H[i].append(p)
    #print(H)
    I=[len(H[i]) for i in range(N)]
    for i in range(N):
        H[i].sort(key=lambda x:I[x])
    P=[0 for i in range(N)]
    X=[]
    Y=[]
    Z=[]
    for i in range(1,N+1):
        if i%3==0:
            X.append(i)
        elif i%3==1:
            Y.append(i)
        else:
            Z.append(i)
    J=sorted(range(N),key=lambda x:-I[x])
    for j in J:
        q=deque([j])
        if P[j]!=0:
            continue
        if len(X)>0:
            P[j]=X[-1]
            X.pop()
        elif len(Y)>0:
            P[j]=Y[-1]
            Y.pop()
        else:
            P[j]=Z[-1]
            Z.pop()
        while(len(q)>0):
            r=q.pop()
            for p in H[r]:
                if P[p]!=0:
                    continue
                if P[r]%3==0:
                    if random.randrange(2)==0:
                        if len(Y)>0:
                            P[p]=Y[-1]
                            Y.pop()
                        elif len(Z)>0:
                            P[p]=Z[-1]
                            Z.pop()
                        else:
                            P[p]=X[-1]
                            X.pop()
                    else:
                        if len(Z)>0:
                            P[p]=Z[-1]
                            Z.pop()
                        elif len(Y)>0:
                            P[p]=Y[-1]
                            Y.pop()
                        else:
                            P[p]=X[-1]
                            X.pop()
                elif P[r]%3==1:
                    if len(Z)>0:
                        P[p]=Z[-1]
                        Z.pop()
                    elif len(X)>0:
                        P[p]=X[-1]
                        X.pop()
                    else:
                        print(-1)
                        exit()
                else:
                    if len(Y)>0:
                        P[p]=Y[-1]
                        Y.pop()
                    elif len(X)>0:
                        P[p]=X[-1]
                        X.pop()
                    else:
                        print(-1)
                        exit()
    print(*P)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5+1)

def cur(p):
    for i in x[p]:
        if rank[i]==-1:
            rank[i]=rank[p]+1
            par[i]=p
            cur(i)


n=int(input())
x=[[] for i in range(n)]

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

rank=[-1 for i in range(n)]
rank[0]=0
par=[-1 for i in range(n)]

cur(0)
M=max(rank)
x=[[] for i in range(M+1)]

q=[0,0]
r=[n//3,n//3,n//3]
if n%3>0: r[1]+=1
if n%3>1: r[2]+=1
tmp1,tmp2,tmp3=1,2,3

for i in range(n):
    q[rank[i]%2]+=1
    x[rank[i]].append(i)
ans=[-1 for i in range(n)]


if q[0]>r[0]+r[1] or q[1]>r[0]+r[2]:
    if q[0]>r[0]+r[2] or q[1]>r[0]+r[1]:
        print(-1)
        sys.exit()
    else:
        tmp1,tmp2=2,1


for i in range(M+1):
    if i%2==0:
        for p in x[i]:
            if tmp1<=n:
                ans[p]=tmp1
                tmp1+=3
            else:
                ans[p]=tmp3
                tmp3+=3
    else:
        for p in x[i]:
            if tmp2<=n:
                ans[p]=tmp2
                tmp2+=3
            else:
                ans[p]=tmp3
                tmp3+=3
for i in range(n-1):
    print(ans[i],end=" ")
print(ans[n-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
hpop = heapq.heappop
hpush = heapq.heappush
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

table = [[] for _ in range(N + 1)]
sta = []
for x in range(1, N + 1):
  Q = dq([])
  Q.append((x, 0))
  vis = set()
  while len(Q):
    y, n = Q.popleft()
    if n == 3:
      table[x].append(y)
      continue
    for q in e[y]:
      if q in vis: continue
      vis.add(q)
      Q.append((q, n + 1))
  hpush(sta, (-len(table[x]), x))

nm = [0] * 3
for x in range(1, N + 1): nm[x % 3] += 1

res = [0] * (N + 1)

while nm[0]:
  _, x = hpop(sta)
  res[x] = nm[0] * 3
  nm[0] -= 1

rest = []
while nm[1]:
  if len(sta) == 0: break
  v, x = hpop(sta)
  ng = 0
  for y in table[x]:
    if res[y] % 3 == 1:
      ng = 1
      break
  if ng:
    rest.append((v, x))
    continue
  res[x] = (nm[1] - 1) * 3 + 1
  nm[1] -= 1

for t in rest: hpush(sta, t)

while nm[2]:
  if len(sta) == 0: break
  _, x = hpop(sta)
  ng = 0
  for y in table[x]:
    if res[y] % 3 == 2:
      ng = 1
      break
  if ng: continue
  res[x] = (nm[2] - 1) * 3 + 2
  nm[2] -= 1
#print(res, table)
for i in range(1, N + 1):
  if res[i] == 0:
    print(-1)
    exit(0)
  for j in table[i]:
    if ((res[i] + res[j]) % 3) > 0 and ((res[i] * res[j]) % 3) > 0:
      print(-1)
      exit(0)
print(*res[1: ])

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(si):
    q = deque()
    used = set()
    q.append([si, 0])
    used.add(si)

    while len(q) > 0:
        prvi, d = q.popleft()
        if d < 2:
            for i in g[prvi]:
                if i not in used:
                    q.append([i, d + 1])
                    used.add(i)

        elif d == 2:
            for i in g[prvi]:
                if i not in used:
                    if si < i:
                        dis3_pairs[si].add(i)

N = int(input())
g = {i: [] for i in range(1, N + 1)}

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

try:
    dis3_pairs = {i: set() for i in range(1, N + 1)}
    for n in range(1, N + 1):
        bfs(n)

    sorted_dis3_pairs = sorted(dis3_pairs.items(), key=lambda x: len(x[1]), reverse=True)

    mod3_0 = deque()
    mod3_1 = deque()
    mod3_2 = deque()
    for i in range(1, N + 1):
        if i % 3 == 0:
            mod3_0.append(i)
        elif i % 3 == 1:
            mod3_1.append(i)
        else:
            mod3_2.append(i)

    ans = [-1 for _ in range(N)]
    for par_node, chi_nodes in sorted_dis3_pairs:
        if len(chi_nodes) == 0:
            continue

        if len(mod3_0) > 0:
            tmp_num1 = mod3_0.pop()
            ans[par_node - 1] = tmp_num1
        else:
            chi_mod = None
            for chi_node in chi_nodes:
                if ans[chi_node-1] == -1:
                    continue
                else:
                    if chi_mod is None:
                        chi_mod = ans[chi_node-1] % 3
                    else:
                        print(chi_mod, ans[chi_node-1] % 3)
                        if chi_mod != ans[chi_node-1] % 3:
                            print(-1)
                            exit()
            if chi_mod is None:
                if len(mod3_1) > len(mod3_2):
                    for_par_node = mod3_2
                    for_chi_node = mod3_1
                else:
                    for_par_node = mod3_1
                    for_chi_node = mod3_2
            else:
                if chi_mod == 1:
                    for_par_node = mod3_2
                    for_chi_node = mod3_1
                else:
                    for_par_node = mod3_1
                    for_chi_node = mod3_2

            ans[par_node - 1] = for_par_node.pop()

            for chi_node in chi_nodes:
                if ans[chi_node - 1] == -1:
                    ans[chi_node - 1] = for_chi_node.pop()

    for i in range(N):
        if ans[i] == -1:
            if len(mod3_0) > 0:
                ans[i] = mod3_0.pop()
            elif len(mod3_1) > 0:
                ans[i] = mod3_1.pop()
            else:
                ans[i] = mod3_2.pop()
    print(*ans)
except:
    print(-1)

Submission status: Wrong Answer

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

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

import queue

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

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter, deque

N, = list(map(int, input().split()))

g = defaultdict(list)
for i in range(N - 1):
    u, v = list(map(int, input().split()))
    g[u].append(v)
    g[v].append(u)


dist = {}
q = deque()
q.append(1)
dist[1] = 0
while q:
    node = q.popleft()
    level = dist[node]
    for nbr in g[node]:
        if nbr not in dist:
            q.append(nbr)
            dist[nbr] = level + 1

parityCounts = Counter(level % 2 for level in dist.values())
parityToMod = {}
if parityCounts[0] > parityCounts[1]:
    parityToMod[0] = 1
    parityToMod[1] = 2
else:
    parityToMod[0] = 2
    parityToMod[1] = 1
mod = {1: 1, 2: 2, 0: 3}
assign = {}
for i in range(1, N + 1):
    parity = dist[i] % 2
    val = mod[parityToMod[parity]]
    mod[parityToMod[parity]] += 3
    if val > N:
        val = mod[0]
        mod[0] += 3
        if val > N:
            print(-1)
            exit()
    assign[i] = val

print(" ".join(str(assign[i]) for i in range(1, N + 1)))

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
	ta,tb = map(int,input().split())
	if ta > tb:
		ta,tb = tb,ta
	E[ta].append(tb)
	E[tb].append(ta)

ans = [0] * (N+1)

q = [[1,1]]

while q:
	cp,cd = q.pop(0)
	for np in E[cp]:
		if ans[np] == 0:
			ans[np] = cd*(-1)
			q.append([np,cd*(-1)])
mod0 = 6
mod1 = 1
mod2 = 2

answer = [3]
for i in range(2,N+1):
	if ans[i] == 1:
		if mod1 <= N:
			answer.append(mod1)
			mod1 += 3
		else:
			answer.append(mod0)
			mod0 += 3
	else:
		if mod2 <= N:
			answer.append(mod2)
			mod2 += 3
		else:
			answer.append(mod0)
			mod0 += 3

print(*answer)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    T = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        T[a].append(b)
        T[b].append(a)

    def calc_dis3(s):
        stack = [(s, 1)]
        visited = [0] * N
        dis3 = set()

        while stack:
            n, depth = stack.pop()
            visited[n] = 1

            if depth == 4:
                dis3.add(n)
                continue

            for to in T[n]:
                if visited[to]:
                    continue

                stack.append((to, depth + 1))

        return dis3

    dis3_counts = [0] * N
    for n in range(N):
        ret_calc_dis3 = calc_dis3(n)
        dis3_counts[n] = len(ret_calc_dis3)

    # ３の倍数をできるだけいい位置にセット
    ans = [-1] * N
    dis3_counts_sorted = sorted([[c, i] for i, c in enumerate(dis3_counts)], reverse=True)
    for i in range(N // 3):
        ans[dis3_counts_sorted[i][1]] = 3 * (i + 1)

    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Tree:
    def __init__(self, N):
        self.N = N # #vertices
        self.D = (self.N-1).bit_length() # #iterations in doubling
        self.E = [{} for _ in range(N)]
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def lca_initialize(self):
        self.dfs(0)
        self.doubling()
    
    def dfs(self, root):
        # parents[v]: the parent of the vertex v
        # depth[v]: the depth of the vertex v from the root
        # dist[v]: the distance of the vertex v from the root.
        self.parent = [None] * self.N
        self.depth = [None] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u, d in self.E[v].items():
                if self.depth[u] is not None: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + d
                stack.append(u)
    
    def doubling(self):
        # O(N log N) time
        self.next = [[-1] * self.N for _ in range(self.D)]
        for v in range(self.N):
            self.next[0][v] = self.parent[v]
        for d in range(self.D - 1):
            for v in range(self.N):
                if self.next[d][v] != -1:
                    self.next[d + 1][v] = self.next[d][self.next[d][v]]
    
    def lca(self, u, v):
        # O(log N) time
        # the depth of v is set to be no less than that of u
        if self.depth[u] > self.depth[v]: u, v = v, u
        # find the ancestor of v with the same depth as that of u
        diff = self.depth[v] - self.depth[u]
        for i in range(diff.bit_length()):
            if diff & (1 << i): v = self.next[i][v]
        if u == v: return u
        for i in range(self.depth[u].bit_length() - 1, -1, -1):
            pu, pv = self.next[i][u], self.next[i][v]
            if pu != pv: u, v = pu, pv
        return self.next[0][u]

N = int(input())
tr = Tree(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    tr.add_edge(a-1, b-1, 1, undirected=True)
tr.dfs(0)
d_odd, d_even = [], []
rem = [[] for _ in range(3)]
for i in range(N):
    if tr.depth[i] % 2 == 0: d_even.append(i)
    else: d_odd.append(i)
    rem[(i+1)%3].append(i+1)
P = [0] * N
if len(d_odd) < len(d_even):
    for i in d_odd:
        if rem[2]:
            P[i] = rem[2].pop()
        elif rem[0]:
            P[i] = rem[0].pop()
        else:
            P[i] = rem[1].pop()
    temp = rem[2] + rem[0] + rem[1]
    for i in d_even: P[i] = temp.pop()
else:
    for i in d_even:
        if rem[2]:
            P[i] = rem[2].pop()
        elif rem[0]:
            P[i] = rem[0].pop()
        else:
            P[i] = rem[1].pop()
    temp = rem[2] + rem[0] + rem[1]
    for i in d_odd: P[i] = temp.pop()
print(*P)

Submission status: Wrong Answer

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

def search(now):
    global pair1
    global pair2
    nowlist = ab[now]
    pair1[now] = set(nowlist)
    for i in nowlist:
        if i < now:
            pair2[now] |= pair1[i]-set([now])
        else:
            pair2[now] |= set(ab[i]) -set([now])
            

for i in range(N):
    search(i)
for i in range(N):
    a = set()
    for j in pair2[i]:
        if j > i:
            a |= set(pair1[j])
    a -= set(pair1[i])
    pair3.append(a)
print(pair1)
print(pair2)
print(pair3)