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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return input().split()
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    def f(point, pre):
        p = lis[point]
        for nex in edg[point]:
            if nex == pre:
                continue
            lis[nex] = p + 1
            f(nex, point)
        return
    n = II()
    ab = LIR_(n - 1)
    lis = [-1] * n
    edg = [[] for _ in range(n)]
    for a, b in ab:
        edg[a].append(b)
        edg[b].append(a)
    lis[0] = 1
    f(0, -1)
    d = [0, 0]
    for i in lis:
        d[i & 1] += 1
    ans = [None] * n
    if d[0] <= n // 3:
        t = 1
        for i in range(n):
            if lis[i] & 1:
                continue
            ans[i] = str(t * 3)
            t += 1
        m = t * 3
        t = 1
        for i in range(n):
            if ans[i]:
                continue
            ans[i] = str(t)
            t += 1
            if t >= m:
                continue
            if t % 3 == 0:
                t += 1
    elif d[1] <= n // 3:
        t = 1
        for i in range(n):
            if not lis[i] & 1:
                continue
            ans[i] = str(t * 3)
            t += 1
        m = t * 3
        t = 1
        for i in range(n):
            if ans[i]:
                continue
            ans[i] = str(t)
            t += 1
            if t >= m:
                continue
            if t % 3 == 0:
                t += 1
    else:
        t = n // 3
        odd = 1
        even = 2
        for i in range(n):
            if t:
                if lis[i] & 1:
                    if d[1] <= n // 3 + (n % 3 >= 1):
                        ans[i] = str(odd)
                        odd += 3
                    else:
                        ans[i] = str(3 * t)
                        t -= 1
                else:
                    if d[0] <= n // 3 + (n % 3 >= 1):
                        ans[i] = str(even)
                        even += 3
                    else:
                        ans[i] = str(3 * t)
                        t -= 1
            else:
                if lis[i] & 1:
                    ans[i] = str(odd)
                    odd += 3
                else:
                    ans[i] = str(even)
                    even += 3
    print(" ".join(ans))


    return


#main
if __name__ == '__main__':
    solve()

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))
    Safe = [True] * N
    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
                Safe[nowNode] = False
            else:
                f = Par[nowNode]
                g = Par[f]
                if not Safe[g]:
                    print(-1)
                    break
                else:
                    possible = True
                    for u in Son[g]:
                        if u != f and not Safe[u]:
                            possible = False
                            break
                    if possible:
                        Ans[nowNode] = 3 * modIndex[dType ^ 1] + (dType ^ 1) + 1
                        modIndex[dType ^ 1] += 1
                        Safe[nowNode] = False
                    else:
                        print(-1)
                        break
    else:
        print(" ".join(map(str, Ans)))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

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

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

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

q = deque([])

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

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


def bfs(start):
    q.append([start, 0])
    dist = [-1] * (N + 1)

    if start == 1:
        node_p[start] = 1

    while q:
        now, prev = q.popleft()
        dist[now] = dist[prev] + 1

        if dist[now] > 3:
            return

        if dist[now] == 3:
            if node_p[now] == 0:
                modfit(now, start)
            elif (node_p[start] + node_p[now]) % 3 != 0:
                dummy2(-1)
                dummy()
            else:
                continue

        for nxt in graph[now]:
            if dist[nxt] == -1:
                q.append([nxt, now])


def modfit(now, start):
    if node_p[start] % 3 == 0:
        if mod1:
            node_p[now] = mod1.pop()
        elif mod2:
            node_p[now] = mod2.pop()
        elif mod0:
            node_p[now] = mod0.pop()

    elif node_p[start] % 3 == 1:
        if mod2:
            node_p[now] = mod2.pop()
        elif mod0:
            node_p[now] = mod0.pop()
        else:
            dummy2(-1)
            dummy()

    else:
        if mod1:
            node_p[now] = mod1.pop()
        elif mod0:
            node_p[now] = mod0.pop()
        else:
            dummy2(-1)
            dummy()


def dummy():
    return


def dummy2(n):
    return


for i in range(1, N + 1):
    bfs(i)

for i in range(1, N + 1):
    if node_p[i] == 0:
        if mod1:
            node_p[i] = mod1.pop()
        elif mod0:
            node_p[i] = mod0.pop()
        elif mod2:
            node_p[i] = mod2.pop()

for i in range(1, N + 1):
    print(node_p[i], end=" ")

print()

Submission status: Wrong Answer

Solution code:
n=int(input())
l1=[set() for i in range(n+1)]
l2=[set() for i in range(n+1)]
l3=[set() for i in range(n+1)]

for i in range(n-1):
    a,b=[int(j) for j in input().split()]
    l1[a].add(b)
    l1[b].add(a)

for i in range(1,1+n):
    for j in l1[i]:
        l2[i]^=l1[j]
    if i in l2[i]:
        l2[i].remove(i)

for i in range(1,1+n):
    for j in l2[i]:
        l3[i]^=l1[j]
    l3[i]-=l1[i]

l=set()
for i in range(1,1+n):
    for j in l3[i]:
        p,q=min(i,j),max(i,j)
        l.add((p-1,q-1))

ans=[0]*n
s1=list(range(1,n+1,3))
s2=list(range(2,n+1,3))
s3=list(range(3,n+1,3))
p,q,r=0,0,0
s,t,u=len(s1),len(s2),len(s3)
for i,j in l:
    if ans[i]==0 and ans[j]==0:
        if p<s and q<t:
            ans[i]=s1[p]
            ans[j]=s2[q]
            p+=1
            q+=1
        else:
            if p<s:
                ans[i]=s1[p]
                p+=1
                if r<u:
                    ans[j]=s3[r]
                    r+=1
                else:
                    print(-1)
                    exit()
            elif q<t:
                ans[j]=s1[p]
                p+=1
                if r<u:
                    ans[i]=s3[r]
                    r+=1
                else:
                    print(-1)
                    exit()
            else:
                if r<u-1:
                    ans[i]=s3[r]
                    ans[j]=s3[r+1]
                    r+=2
                else:
                    print(-1)
                    exit()

for i in range(n):
    if ans[i]==0:
        if p<s:
            ans[i]=s1[p]
            p+=1
        elif q<t:
            ans[i]=s2[q]
            q+=1
        elif r<u:
            ans[i]=s3[r]
            r+=1
        else:
            print(-1)
            exit()


print(*ans)

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]:
        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:
N = int(input())
A = [i+1 for i in range(N)]
print(*A)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
pair = [[] for i in range(N)]
def bfs(now):
    que = deque()
    que.append(now)
    alr = [-1 for i in range(N)]
    alr[now] = 0
    ans = []
    while que:
        q = que.popleft()
        c = alr[q]
        if c == 3:
            ans.append(q)
            continue
        for i in ab[q]:
            if alr[i] == -1:
                alr[i] = c+1
                que.append(i)
    return ans
for i in range(N):
    pair[i] = bfs(i)
print(pair)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
from collections import deque


class Tree():
    def __init__(self,n,edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append((e[1] - 1, 1))
            self.tree[e[1] - 1].append((e[0] - 1, 1))
    def setroot(self,root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.distance = [None for _ in range(self.n)]
        self.distance[root] = 0
        stack = [root]
        while stack:
            node = stack.pop()
            for adj,cost in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node]+1
                    self.distance[adj] = self.distance[node]+cost
                    stack.append(adj)
    def diam(self):
        u = self.distance.index(max(self.distance))
        dist_u = [None for _ in range(N)]
        dist_u[u] = 0
        stack = [u]
        while stack:
            node = stack.pop()
            for adj,cost in self.tree[node]:
                if dist_u[adj] is None:
                    dist_u[adj] = dist_u[node]+cost
                    stack.append(adj)
        d = max(dist_u)
        v = dist_u.index(d)
        return d,u,v
    def construct_lca(self):
        L = (self.n-1).bit_length()
        self.k_parent = [self.parent]
        prev = self.parent
        for k in range(L):
            array = [0 for _ in range(self.n)]
            for i in range(self.n):
                if prev[i] == -1: continue
                array[i] = prev[prev[i]]
            self.k_parent.append(array)
            prev = array
    def lca(self,u,v):
        d = self.depth[v]-self.depth[u]
        if d < 0: u,v,d = v,u,-d
        for k in self.k_parent:
            if d & 1: v = k[v]
            d >>= 1
        if u == v: return u
        for k in reversed(self.k_parent):
            pu,pv = k[u],k[v]
            if pu != pv: u,v = pu,pv
        return self.k_parent[0][u]
    def dist(self,u,v):
        l = self.lca(u,v)
        return self.distance[u]+self.distance[v]-2*self.distance[l]

      
n = int(input())
N = n
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)


t = Tree(n, info)
t.setroot(0)
t.construct_lca()
d,u,v = t.diam()
distance2 = []
for i in range(n):
    distance2.append(max(t.dist(i,u), t.dist(i,v)))


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)
for i in range(n):
    if distance2[i] < 3:
        visited[i] = -1

cnt1 = n // 3 
cnt2 = n // 3
cnt3 = n // 3
if n % 3 >= 1:
   cnt1 += 1
if n % 3 >= 2:
   cnt2 += 1

# print(visited)
# print(cnt1, cnt2, cnt3)

cnt = [0, 0]
for i in range(n):
    if visited[i] == 0:
        cnt[0] += 1
    elif visited[i] == 1:
        cnt[1] += 1

#if cnt[0] >= cnt[1]:
#    pass
#else:
#    for i in range(n):
#        if visited[i] == 0:
#            visited[i] = 1
#        elif visited[i] == 1:
#            visited[i] = 0

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)

ans = [0] * n
num147 = 0
num258 = 0
num369 = 0
for i in range(n):
    if visited[i] == -1:
        continue
    elif 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()
        else:
            error
print(*ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

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

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

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

q = deque([])

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

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


def bfs(start):
    q.append([start, 0])
    dist = [-1] * (N + 1)

    if start == 1:
        node_p[start] = 1

    while q:
        now, prev = q.popleft()
        dist[now] = dist[prev] + 1

        if dist[now] > 3:
            return

        if dist[now] == 3:
            if node_p[now] == 0:
                modfit(now, start)
            elif (node_p[start] + node_p[now]) % 3 != 0:
                dummy2(-1)
                dummy()
            else:
                continue

        for nxt in graph[now]:
            if dist[nxt] == -1:
                q.append([nxt, now])


def modfit(now, start):
    if node_p[start] % 3 == 0:
        if mod1:
            node_p[now] = mod1.pop()
        elif mod2:
            node_p[now] = mod2.pop()
        elif mod0:
            node_p[now] = mod0.pop()

    elif node_p[start] % 3 == 1:
        if mod2:
            node_p[now] = mod2.pop()
        elif mod0:
            node_p[now] = mod0.pop()
        else:
            dummy2(-1)
            dummy()

    else:
        if mod1:
            node_p[now] = mod1.pop()
        elif mod0:
            node_p[now] = mod0.pop()
        else:
            dummy2(-1)
            dummy()


def dummy():
    return


def dummy2(n):
    return


for i in range(1, N + 1):
    bfs(i)

for i in range(1, N + 1):
    if node_p[i] == 0:
        if mod1:
            node_p[i] = mod1.pop()
        elif mod0:
            node_p[i] = mod0.pop()
        elif mod2:
            node_p[i] = mod2.pop()

for i in range(1, N + 1):
    print(node_p, end=" ")

print()

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict

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

pa = defaultdict(int)
pa[-1] = -1
pa[0] = -1
que = deque([(-1,0)])
while que:
    pre,now = que.popleft()
    for child in G[now]:
        if child == pre:continue
        pa[child] = now
        que.append((now,child))

Graph = []
for i in range(n):
    if pa[pa[i]] != -1:
        Graph.append(G[pa[pa[i]]].copy())
    else:
        Graph.append([])
G = [[] for _ in range(n)]
for i in range(n):
    for j in Graph[i]:
        if j == pa[i]:continue
        G[i].append(j)
        G[j].append(i)
#print(G)
ans = [-1 for i in range(n)]
num = [[len(G[i]),i] for i in range(n)]
num.sort(reverse=True)
#print(num)
i = 1
while 3*i <= n:
    ans[num[i-1][1]] = 3*i
    i += 1


use = [1, 2]
for i in range(n):
    #print(ans)
    if ans[i] != -1: continue
    queue = deque([])
    if use[0] + 1 <= max(use[1], n):
        ans[i] = use[0]
        use[0] += 3
        queue.append((i,1))
    elif use[1] <= max(use[0] + 1, n):
        ans[i] = use[1]
        use[1] += 3
        queue.append((i,2))
    while queue:
        now,num = queue.popleft()
        for to in G[now]:
            if ans[to] != -1:continue
            if num == 1:
                if use[1] > n:
                    print(-1)
                    exit()
                ans[to] = use[1]
                use[1] += 3
                queue.append((to,2))
            else:
                if use[0] > n:
                    print(-1)
                    exit()
                ans[to] = use[0]
                use[0] += 3
                queue.append((to,1))

print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return input().split()
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    def f(point, pre):
        p = lis[point]
        for nex in edg[point]:
            if nex == pre:
                continue
            lis[nex] = p + 1
            f(nex, point)
        return
    n = II()
    ab = LIR_(n - 1)
    lis = [-1] * n
    edg = [[] for _ in range(n)]
    for a, b in ab:
        edg[a].append(b)
        edg[b].append(a)
    lis[0] = 1
    f(0,-1)
    d = [0,0]
    for i in lis:
        d[i & 1] += 1
    ans = [None] * n
    if d[0] <= n // 3:
        t = 1
        for i in range(n):
            if lis[i] & 1:
                continue
            ans[i] = str(t * 3)
            t += 1
        m = t * 3
        t = 0
        for i in range(n):
            if ans[i]:
                continue
            ans[i] = str(t)
            t += 1
            if t >= m:
                continue
            if t % 3 == 0:
                t += 1
    elif d[1] <= n // 3:
        t = 1
        for i in range(n):
            if not lis[i] & 1:
                continue
            ans[i] = str(t * 3)
            t += 1
        m = t * 3
        t = 0
        for i in range(n):
            if ans[i]:
                continue
            ans[i] = str(t)
            t += 1
            if t >= m:
                continue
            if t % 3 == 0:
                t += 1
    else:
        t = n // 3
        odd = 1
        even = 2
        for i in range(n):
            if t:
                if lis[i] & 1:
                    if d[1] <= n // 3 + (n % 3 >= 1):
                        ans[i] = str(odd)
                        odd += 3
                    else:
                        ans[i] = str(3 * t)
                        t -= 1
                else:
                    if d[0] <= n // 3 + (n % 3 >= 1):
                        ans[i] = str(even)
                        even += 3
                    else:
                        ans[i] = str(3 * t)
                        t -= 1
            else:
                if lis[i] & 1:
                    ans[i] = str(odd)
                    odd += 3
                else:
                    ans[i] = str(even)
                    even += 3
    print(" ".join(ans))


    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

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


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

Submission status: Wrong Answer

Solution code:
def main():
  import sys
  from collections import deque
  
  n = int(input())
  t = [[] for _ in range(n+1)]
  p = [i for i in range(n+1)]

  
  for e in sys.stdin:
    a, b = map(int, e.split())
    t[a].append(b)
    t[b].append(a)
  
  for i in range(1,n+1):
    
    if len(t[i]) == 0:
      continue
 
    que0 = deque(t[i])
    filt = set(t[i])
    que1 = set([])
    
    while(que0):
      point = que0.pop()
      que1 = que1 | set([point])
      
    que1 = deque(que1)
    que2 = set([])
    
    while(que1):
      point = que1.pop()
      que2 = que2 | set(t[point])
        
    que2 = deque( que2 - filt )
    filt = filt | set(que2)
    que3 = set([])
    
    while(que2):
      point = que2.pop()
      que3 = que3 | set(t[point])

    que3 = deque( que3 - filt )

    while(que3):
      point = que3.pop()
      p[i], p[point] = 6, 6
    
  for x in p[1:]:
    print(x, end=' ')
    
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
N = int(input())

Result = [3 for i in range(N)]
for i in range(N - 1):
    A, B = map(int, input().split())


for i in range(N):
    print(Result[i], end=' ')

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def eulerian_trail(tree, max_v, root=0):
    """
    木のオイラー路; オイラーツアー
    :param list of (list of (int, int)) tree:
    :param int max_v:
    :param int root:
    :return: (trails, depths, weights)
    :rtype: (list of int, list of int, list of int)
    """
    seen = [False] * (max_v + 1)
    # 頂点の履歴
    trails = []
    # 深さの履歴
    depths = []
    # 距離の履歴
    weights = []
    # Overflow 回避のためループで
    stack = [(root, 0, 0, True)]
    while stack:
        v, d, w, forward = stack.pop()
        seen[v] = True
        trails.append(v)
        depths.append(d)
        weights.append(w)
        if not forward:
            continue

        for u, w in tree[v]:
            if not seen[u]:
                stack.append((v, d, -w, False))
                stack.append((u, d + 1, w, True))
    return trails, depths, weights


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]

# AB = generate_tree(N)
# plot_graph(AB)
# for a, b in AB:
#     graph[a].append((b, 1))
#     graph[b].append((a, 1))

for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append((b, 1))
    graph[b].append((a, 1))

vs, _, _ = eulerian_trail(graph, N - 1)
for n in [1, 2]:
    counts = [N // 3, (N + 2) // 3, (N + 1) // 3]
    # 交互に割り当てる
    ansmod = [-1] * N
    for i, v in enumerate(vs):
        if ansmod[v] < 0 and counts[n] > 0:
            counts[n] -= 1
            ansmod[v] = n
        n = 1 if n == 2 else 2
    if counts[1] == counts[2] == 0:
        break
else:
    print(-1)
    exit()

ans = []
M = [3, 1, 2]
for a in ansmod:
    if a == -1:
        a = 0
    ans.append(M[a])
    M[a] += 3
print(*ans)

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 = set()
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.add((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] = str(3 * idx)
        used.add(3 * idx)


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

print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10**6)

def dfs(i, depth):
    visited[i] = True
    oe = depth%2
    if base[oe] > N:
        ans[i-1] = str(base[2])
        base[2] += 3
    else:
        ans[i-1] = str(base[oe])
        base[oe] += 3
    nodes = tree[i]
    for node in nodes:
        if visited[node]:
            continue
        dfs(node, depth+1)
    


N = int(input())
ans = ['']*N
tree = [[] for i in range(N+1)]
visited = [False]*(N+1)
base = [1, 2, 3]
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a] += [b]
    tree[b] += [a]
dfs(1, 0)
print(' '.join(ans))

Submission status: Wrong Answer

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

# process
# 距離3の頂点を抽出
pair = []
for i in range(N):
    for j in Tree[i]:
        for k in Tree[j]:
            if k == i:
                continue
            for l in Tree[k]:
                if l == j or i > l:
                    continue
                pair.append((i,l))

# 順列を求める
def getAddNum(x, ans):
    t = 0
    for i in range(N):
        if (x+i)%3 == 0:
            t = i

    l = [x for x in range(t, N, 3)]
    for y in l:
        if not y in ans:
            return y

    return -1

def getMulNum(x, ans):
    l = []
    if x%3 == 0:
        l = [n for n in range(1, N+1)]

    else:
        l = [n*3 for n in range(1, N//3+1)]

    for y in l:
        if not y in ans:
            return y

    return -1

def getNextNum(x, ans):
    for y in range(x+1, N+1):
        if not y in ans:
            return y
    
ans = [-1 for _ in range(1, N+1)]
n = 0
for a, b in pair:
    a -= 1
    b -= 1
    if ans[a] == -1:
        ans[a] = getNextNum(n, ans)
    
    t = getAddNum(ans[a], ans)
    if t > 0:
        ans[b] = t
    else:
        t = getMulNum(ans[a], ans)
        ans[b] = t

for i in range(N):
    if ans[i] == -1:
        ans[i] = getNextNum(n, ans)

# output
# print(pair)
print(" ".join(map(str, ans)))