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 = sys.stdin.readline

from collections import deque
n = int(input())
edge = [[] for _ 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)
san = [[] for _ in range(n)]
for i in range(n):
    flag = [True]*n
    flag[i] = False
    stack = deque([])
    for e in edge[i]:
        flag[e] = False
        stack.appendleft((e,1))
    while stack:
        p,q = stack.pop()
        if (q==1):
            for e in edge[p]:
                if (flag[e]):
                    flag[e] = False
                    stack.appendleft((e,2))
        else:
            for e in edge[p]:
                if (flag[e] and e>i):
                    san[i].append(e)
#print(san)
ans = [-1]*n
c1=(n-1)//3
c2=(n-1)//3
c3=(n-1)//3
if ((n-1)%3>=0):
    c1+=1
if ((n-1)%3>=1):
    c2+=1
if ((n-1)%3>=2):
    c3+=1
#print(c1,c2,c3)
for i in range(n):
    d = {-1:0, 1:0, 2:0, 3:0}
    for j in san[i]:
        d[ans[j]] += 1
    if (d[1]>0 and d[2]>0):
        ans[i] = 3
    elif (d[1]>0):
        if (ans[i]==-1):
            ans[i] = 2
            for j in san[i]:
                ans[j] = 1
        elif (ans[i]==1):
            ans[i] = 3
        else:
            for j in san[i]:
                ans[j] = 1
    elif (d[2]>0):
        if (ans[i]==-1):
            ans[i] = 1
            for j in san[i]:
                ans[j] = 2
        elif (ans[i]==2):
            ans[i] = 3
        else:
            for j in san[i]:
                ans[j] = 2
    else:
        if (ans[i] ==1):
            for j in san[i]:
                ans[j] = 2
        elif (ans[i]==2):
            for j in san[i]:
                ans[j] = 1
        else:
            ans[i] = 1
            for j in san[i]:
                ans[j] = 2
res = [0]*n
for i in range(n):
    if (ans[i]==1):
        if (c1>0):
            res[i] = 3*c1-2
            c1 -=1
        elif (c3>0):
            res[i] = 3*c3
            c3 -= 1
        else:
            print(-1)
            exit()
    elif (ans[i]==2):
        if (c2>0):
            res[i] = 3*c2-1
            c2 -=1
        elif (c3>0):
            res[i] = 3*c3
            c3 -= 1
        else:
            print(-1)
            exit()
for i in range(n):
    if (res[i]==0):
        if (c1>0):
            res[i] = 3*c1-2
            c1 -=1
        elif (c2>0):
            res[i] = 3*c2-1
            c2 -=1
        elif (c3>0):
            res[i] = 3*c3
            c3 -= 1
        else:
            print(-1)
            exit()
print(*res)

Submission status: Wrong Answer

Solution code:
print("-1")

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
one = collections.deque([1])
two = collections.deque([])
three = collections.deque([])
graph = [[] for _ in range(n)]

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    if i % 3 == 0: two.append(i + 2)
    elif i % 3 == 1: three.append(i + 2)
    else: one.append(i + 2)

que = collections.deque([0])
num = [0] * n
dist = [-1] * n
parity = [0] * 2
dist[0] = 0
flag = True
while len(que) != 0:
    i = que.popleft()
    parity[dist[i] % 2] += 0
    for j in graph[i]:
        if dist[j] != -1: continue
        dist[j] = dist[i] + 1
        que.append(j)

rem = 0 if parity[0] >= parity[1] else 1
for i, v in enumerate(dist):
    if v % 2 == rem:
        if len(one) != 0: num[i] = str(one.popleft())
        elif len(three) != 0: num[i] = str(three.popleft())
        else:
            flag = False
            break
    else:
        if len(two) != 0: num[i] = str(two.popleft())
        elif len(three) != 0: num[i] = str(three.popleft())
        else:
            flag = False
            break

if flag:
    print(' '.join(num))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
one = collections.deque([1])
two = collections.deque([])
three = collections.deque([])
graph = [[] for _ in range(n)]

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    if i % 3 == 0: two.append(i + 2)
    elif i % 3 == 1: three.append(i + 2)
    else: one.append(i + 2)

que = collections.deque([0])
num = [0] * n
dist = [-1] * n
dist[0] = 0
flag = True
while len(que) != 0:
    i = que.popleft()
    if dist[i] % 2 == 0:
        if len(one) != 0: num[i] = str(one.popleft())
        elif len(three) != 0: num[i] = str(three.popleft())
        else:
            flag = False
            break
    else:
        if len(two) != 0: num[i] = str(two.popleft())
        elif len(three) != 0: num[i] = str(three.popleft())
        else:
            flag = False
            break
    for j in graph[i]:
        if dist[j] != -1: continue
        dist[j] = dist[i] + 1
        que.append(j)

if flag:
    print(' '.join(num))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,*ab = map(int,open(0).read().split())
edge = [[] for _ in range((n))]

for a,b in zip(ab[::2],ab[1::2]):
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)


q = deque([(0,0)])
num = [1,2,3]
ans = [0]*n

while q:
    v,g = q.popleft()
    if num[g] <=n:
        ans[v] = num[g]
        num[g] += 3
    elif num[2] <= n:
        ans[v] = num[2]
        num[2] += 3
    else:
        ans = [-1]
        break
    
    for ve in edge[v]:
        if ans[ve] >0: continue
        q.append((ve,g^1))

print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,*ab = map(int,open(0).read().split())
edge = [[] for _ in range((n))]

for a,b in zip(ab[::2],ab[1::2]):
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)


q = deque([(0,0)])
num = [1,2,3]
ans = [0]*n

while q:
    v,g = q.popleft()
    if num[g] <=n:
        ans[v] = num[g]
        num[g] += 3
    elif num[2] <= n:
        ans[v] = num[2]
        num[2] += 3
    else:
        ans = [-1]
        break
    
    for ve in edge[v]:
        if ans[ve] >0: continue
        q.append((ve,g^1))

print("\n".join(map(str,ans)))

Submission status: Wrong Answer

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

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

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

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

for i in range(1, N+1):
    cnt[i%3] += 1

color = bfs()
m = color.count(1)
ans = [-1]*N

if m<=cnt[0]:
    c0, c1, c2 = 3, 1, 2
    
    for i in range(N):
        if color[i]==1:
            ans[i] = c0
            c0 += 3
    
    for i in range(N):
        if color[i]==-1:
            if c0<N:
                ans[i] = c0
                c0 += 3
            else:
                if c1<N:
                    ans[i] = c1
                    c1 += 3
                else:
                    ans[i] = c2
                    c2 += 3
elif m>=N-cnt[0]:
    c0, c1, c2 = 3, 1, 2
    
    for i in range(N):
        if color[i]==-1:
            ans[i] = c0
            c0 += 3
    
    for i in range(N):
        if color[i]==1:
            if c0<N:
                ans[i] = c0
                c0 += 3
            else:
                if c1<N:
                    ans[i] = c1
                    c1 += 3
                else:
                    ans[i] = c2
                    c2 += 3
else:
    c0, c1, c2 = 3, 1, 2
    
    for i in range(N):
        if color[i]==1:
            if c1<N:
                ans[i] = c1
                c1 += 3
            else:
                ans[i] = c0
                c0 += 3
        
    for i in range(N):
        if color[i]==-1:
            if c0<N:
                ans[i] = c0
                c0 += 3
            else:
                ans[i] = c2
                c2 += 3

print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    return 
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [0]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(1,n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)

ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in r:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
elif B <= n//3:
    tmp = 3
    for i in b:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
else:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if i % 3 == 0:
            if r:
                ans[r.pop()] = i
            elif b:
                ans[b.pop()] = i
            elif ans[0] == None:
                ans[0] = i
print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    return 
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [1]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(1,n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)

ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in r:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
elif B <= n//3:
    tmp = 3
    for i in b:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
else:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            continue
        elif b:
            v = b.pop()
            ans[v] = i
            continue
        elif ans[0] == None:
            ans[0] = i
print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    return 
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [0]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(1,n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)

ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in r:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
elif B <= n//3:
    tmp = 3
    for i in b:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
else:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            continue
        if b:
            v = b.pop()
            ans[v] = i
            continue
        if ans[0] == None:
            ans[0] = i
print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    return 
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [1]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(1,n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)

ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in r:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
elif B <= n//3:
    tmp = 3
    for i in b:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
else:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i
        break
print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    return 
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [0]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(1,n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)

ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in r:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
    print(*ans)
elif B <= n//3:
    tmp = 3
    for i in b:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
    print(*ans)
elif R > n//3 and B > n//3:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i
        break
    print(*ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [0]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(1,n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)

ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in r:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
    print(*ans)
elif B <= n//3:
    tmp = 3
    for i in b:
        ans[i] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
    print(*ans)
elif R > n//3 and B > n//3:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i
        break
    print(*ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [0]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(1,n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)

ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in range(R):
        ans[r[i]] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
elif B <= n//3:
    tmp = 3
    for i in range(B):
        ans[b[i]] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
else:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i
        break
print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs(s,p):
    for v in edges[s]:
        if v == p:
            continue
        dist[v] = dist[s] + 1
        dfs(v,s)
    
n = I()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
dist = [0]*n
dfs(0,-1)
R,B = 0,0
r,b = [],[]
for i in range(1,n):
    if dist[i] % 2:
        R += 1
        r.append(i)
    else:
        B += 1
        b.append(i)
print(R,B)
ans = [None]*n
f = defaultdict(lambda:0)
if R <= n//3:
    tmp = 3
    for i in range(R):
        ans[r[i]] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if b:
            v = b.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
elif B <= n//3:
    tmp = 3
    for i in range(B):
        ans[b[i]] = tmp
        f[tmp] = 1
        tmp += 3
    for i in range(1,n+1):
        if f[i]:
            continue
        if r:
            v = r.pop()
            ans[v] = i
            f[i] = 1
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i    
        break
else:
    for i in range(1,n+1):
        if i % 3 == 1:
            if r:
                v = r.pop()
                ans[v] = i
                f[i] = 1
                continue
        elif i % 3 == 2:
            if b:
                v = b.pop()
                ans[v] = i
                f[i] = 1
                continue
    for i in range(1,n+1):
        if f[i]:
            continue
        ans[0] = i
        break
print(*ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
ans = ""
for i in range(N-1):
  ans += "3 "
ans += "3"

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
G = [[0]*N for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1][b-1] = G[b-1][a-1] = 1

def bfs(i, j) :
    stack = [i]
    dist = [-1]*N
    dist[i] = 0
    while stack :
        now = stack.pop()
        for k in range(N) :
            if G[now][k] == 1 :
                if dist[k] == -1 :
                    dist[k] = dist[now] + 1
                    if j == k :
                        return dist[k]
                    stack.append(k)
                if k in stack :
                    continue

pair = []
for i in range(N) :
    for j in range(i+1,N) :
        if bfs(i, j) == 3 :
            pair.append([i, j])

print(pair)

import itertools
for ans in itertools.permutations(range(1,N+1)) :
    flg = True
    for p in pair :
        if (ans[p[0]] + ans[p[1]])%3 != 0 and (ans[p[0]] + ans[p[1]])%3 != 0 :
            flg = False
    if flg == True :
        print(ans)
        exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

sys.setrecursionlimit(10**9)


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

flag = [0]*n
def dfs(cur, par,f):
    flag[cur] = f
    for to in G[cur]:
        if to != par:
            dfs(to, cur, f^1)

dfs(0, -1, 0)

Submission status: Wrong Answer

Solution code:
from collections import deque
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)
    graph[b - 1].append(a - 1)
color = [-1 for _ in range(n)]
color[0] = 0
def coloring(x):
    for i in graph[x]:
        if color[x] != -1:
            continue
        color[i] = 1 - color[x]
        coloring(i)
coloring(0)
A, B = [], []
ans = [0 for _ in range(n)]
for i in range(n):
    if color[i] == 0:
        A.append(i)
    else:
        B.append(i)
if len(A) > len(B):
    A, B = B, A
if len(A) <= n // 3:
    qq = deque([i for i in range(3, n + 1, 3)] +
               [i for i in range(1, n + 1, 3)] + [i for i in range(2, n + 1, 3)])
    for i in A:
        ans[i] = qq.popleft()
    for i in B:
        ans[i] = qq.popleft()
    print(*ans)
else:
    qq = deque([i for i in range(1, n + 1, 3)] +
               [i for i in range(2, n + 1, 3)] + [i for i in range(3, n + 1, 3)])
    for i in A:
        ans[i] = qq.popleft()
    for i in B:
        ans[i] = qq.popleft()
    print(*ans)