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:
from collections import deque
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)

x1, x2, x3 = [], [], []
for n in range(1, N + 1):
    if n % 3 == 1:
        x1.append(n)

    elif n % 3 == 2:
        x2.append(n)

    elif n % 3 == 0:
        x3.append(n)


ans = [-1] * N


def allocate(i, pop_target):
    if pop_target == 1:
        if x1:
            ans[i] = x1.pop()

    else:
        if x2:
            ans[i] = x2.pop()


def bfs(s):
    que = deque([(s, 0)])
    pop_target = 1 if len(x1) >= len(x2) else 2

    while que:
        n, depth = que.pop()
        if depth == 3:
            continue

        if ans[n] < 0:
            allocate(n, pop_target)
        for to in T[n]:
            que.appendleft((to, depth + 1))


for n in range(N):
    if ans[n] > 0:
        continue
    bfs(n)

for n in range(N):
    if ans[n] < 0:
        ans[n] = x3.pop()

print(*ans, sep=' ')

Submission status: Wrong Answer

Solution code:
#  --*-coding:utf-8-*--

N = int(input())
E = [set() for _ in range(N+1)]

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


L = [None]*(N+1)
L[1] = 0

Q = [1]
while len(Q) > 0:
    q = Q.pop()
    nextL = (L[q] + 1)%2

    for subNode in E[q]:
        if L[subNode] == None:
            L[subNode] = nextL
            Q.append(subNode)
            

g1 = 0
g2 = 0
g3 = 1

g1Max = (N+2)//3
g2Max = (N+1)//3
    
X = [None]*(N+1)

for i in range(1, N+1):
    if L[i] == 0:
        if g1 < g1Max:
            X[i] = g1*3 + 1
            g1 += 1
        else:
            X[i] = g3*3
            g3 += 1
    else:
        if g2 < g2Max:
            X[i] = g2*3 + 2
            g2 += 1
        else:
            X[i] = g3*3
            g3 += 1

print(' '.join(map(str, X[1:])))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    ab = [tuple(map(int, input().split())) for _ in range(N - 1)]

    to = [[] for _ in range(N)]
    for a, b in ab:
        to[a - 1].append(b - 1)
        to[b - 1].append(a - 1)

    c1 = list(range(1, N + 1, 3))
    c2 = list(range(2, N + 1, 3))
    c3 = list(range(3, N + 1, 3))

    color = [0] * N

    for root in range(N):
        if len(to[root]) == 1:
            break

    queue = set([root])
    color[root] = 1
    # done = set()
    while queue:
        v = queue.pop()
        color_v = color[v]

        for i in to[v]:
            if color[i] == 0:
                color[i] = 3 - color_v
                queue.add(i)
        # done.add(v)

    ans = [0] * N
    for i in range(N):
        if (color[i] == 1) and c1:
            ans[i] = c1.pop(-1)
        elif (color[i] == 2) and c2:
            ans[i] = c2.pop(-1)
        elif not c3:
            print(-1)
            return
        else:
            ans[i] = c3.pop(-1)

    print(*ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(250000)
l=[None]*N
g=[1,0]
def hu(n,c):
    for i in s[n]:
        if l[i]==None:
            l[i]=c
            g[c%2]+=1
            hu(i,c+1)
l[0]=0
hu(0,1)
a=[1,2,3]
if min(g)>N//3:
    b,c=0,1
    for i in l:
        if i%2:
            print(a[b],end=" ")
            a[b]+=3    
            if a[b]>N:
                b=2
        else:
            print(a[c],end=" ")
            a[c]+=3
            if a[c]>N:
                c=2
else:
    if g[0]<g[1]:
        b,c=2,0
        for i in l:
            if i%2:
                print(a[b])
                a[b]+=3
                if a[b]>N:
                    if b==2:
                        b=1
                    else:
                        b=0
            else:
                print(a[c])
                a[c]+=3
    else:
        b,c=0,2
        for i in l:
            if not i%2:
                print(a[b])
                a[b]+=3
                if a[b]>N:
                    if b==2:
                        b=1
                    else:
                        b=0
            else:
                print(a[c])
                a[c]+=3

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

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

grand_sum = [0 for _ in range(n)]
for i in range(n):
	grand_sum[i] = sum([len(adj[x]) for x in adj[i]]) - len(adj[i])

if n <= 3:
	print(*list(range(1, n+1)))
	sys.exit()

ans = [-1 for _ in range(n)]
#ONE, TWO = n//3 + (n%3 > 0), n//3 + (n%3 > 1)

tri = [0 for _ in range(n)]
for a, b in edges:
	tri[b] += grand_sum[a] - len(adj[b]) + 1
	tri[a] += grand_sum[b] - len(adj[a]) + 1
	#print(a, b)
	#print(tri_a, tri_b)
	#print("---")
#print(tri)

THREE = 3
for i, t in enumerate(tri):
	if t >= n - (n//3):
		if THREE > n:
			print(-1)
			sys.exit()
		ans[i] = THREE
		THREE += 3

#parity = [0, 0]
signs = [-1 for _ in range(n)]
def dfs(x):
	for v in adj[x]:
		if signs[v] < 0:
			signs[v] = 1 ^ signs[x]
			dfs(v)

signs[0] = 0
dfs(0)
num1 = sum(signs)
num2 = n - num1

#print(signs)

M, m = max(num1, num2), min(num1, num2) 
#if max(num1, num2) > n - (n // 3):
#	print(-1)
#	sys.exit()
#else:
if num1 > num2:
	one, two = num1, num2
	more = 1
else:
	one, two = num2, num1
	more = 0
cur = [2, 1, THREE]
for i in range(n):
	if ans[i] > 0:
		continue
	if signs[i] == more:
		if cur[1] > n and cur[2] <= n: 
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[1] > n and cur[2] > n:
			ans[i] = cur[0]
			cur[0] += 3
		else:
			ans[i] = cur[1]
			cur[1] += 3
	else:
		if cur[0] > n and cur[2] <= n:
			ans[i] = cur[2]
			cur[2] += 3
		elif cur[0] > n and cur[2] > n:
			ans[i] = cur[1]
			cur[1] += 3
		else:
			ans[i] = cur[0]
			cur[0] += 3
print(*ans)

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==0:
            if n3<len(mod3):
                p[v]=mod3[n3]
                n3+=1
            elif n2<len(mod2):
                p[v]=mod2[n2]
                n2+=1
            else:
                p[v]=mod1[n1]
                n1+=1
            
        elif 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 deque
import sys
sys.setrecursionlimit(10**6)
def dfs(tree, cursor, parent):
  print(cursor, parent)
  rtn = deque()
  for child in tree[cursor]:
    notme = deque()
    for c2 in tree[cursor]:
      if child != c2:
        notme.append(c2)
    for mago in tree[child]:
      if parent != 0:
        rtn.append((parent, mago))
        rtn += deque([(c2, mago) for c2 in notme])
    rtn += dfs(tree, child, cursor)
  return rtn

N = int(input())
T = [deque() for _ in range(N+1)]
seen = [False]*(N+1)
a, b = map(int, input().split())
a, b = min(a, b), max(a, b)
T[a].append(b)
seen[a] = True
seen[b] = True
for _ in range(N-2):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  if not seen[a]:
    T[b].append(a)
  else:
    T[a].append(b)
  seen[a] = True
  seen[b] = True
dist3s = dfs(T, 1, 0) 
print(dist3s)

Submission status: Wrong Answer

Solution code:
N=int(input())
con=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    con[a-1].append(b-1)
    con[b-1].append(a-1)
import numpy as np
dis3=[[] for _ in range(N)]
for i in range(N):
    visited=[0]*N
    visited[i]=1
    for j in range(len(con[i])):
        if visited[con[i][j]]==0:
            visited[con[i][j]]=1
            for k in range(len(con[con[i][j]])):
                if visited[con[con[i][j]][k]]==0:
                    visited[con[con[i][j]][k]]=1
                    for l in range(len(con[con[con[i][j]][k]])):
                        if visited[con[con[con[i][j]][k]][l]]==0:
                            visited[con[con[con[i][j]][k]][l]]=1
                            dis3[i].append(con[con[con[i][j]][k]][l])
box=np.array([i+1 for i in range(N)], dtype=int)
ans=[0]*N
for i in range(N):
    if ans[i]!=0:
        continue
    d=dis3[i]
    if d==[]:
        continue
    m=min(box)
    ans[i]=m
    for j in range(len(box)):
        if box[j]==m:
            box=np.delete(box,j)
            break
    for j in d:
        if ans[j]!=0:
            continue
        for k in range(len(box)):
            if (ans[i]+box[k])%3==0 or (ans[i]*box[k])%3==0:
                ans[j]=box[k]
                box=np.delete(box,k)
                break

box=list(box)
for i in range(N):
    if ans[i]==0:
        try:
            ans[i]=box.pop()
        except IndexError:
            print('-1')
            exit()

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

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d = [i % 2+1 for i in d]
    d2 = [0]*n
    j = 1
    for i in range(n):
        if d[i] == 1:
            d2[i] = j
            j += 3
    j = 2
    for i in range(n):
        if d[i] == 2:
            d2[i] = j
            j += 3
    j = 3
    for i in range(n):
        if d2[i] > n:
            d2[i] = j
            j += 3
    print(*d2)


main()

Submission status: Wrong Answer

Solution code:
import collections


def bfs(i, G, N):
    flag = [-1 for _ in range(N)]
    flag[i] = 0
    que = collections.deque([i])
    while que:
        target = que.popleft()
        for g in G[target]:
            if flag[g] == -1:
                flag[g] = flag[target] + 1
                que.append(g)

    return flag


def main():
    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)

    F = bfs(0, G, N)
    start = F.index(max(F))
    F = bfs(start, G, N)

    if max(F) < 3:
        res = [i + 1 for i in range(N)]
        print(" ".join(map(str, res)))
        return 0
    kisuu = 0
    for f in F:
        if f % 2 == 1:
            kisuu += 1
    if kisuu >= N - kisuu:
        t0, t1, t2 = 3, 1, 2
    else:
        t0, t1, t2 = 3, 2, 1
    res = [0 for _ in range(N)]
    for i in range(N):
        if F[i] % 2 == 1:
            if t1 <= N:
                res[i] = t1
                t1 += 3
            elif t0 <= N:
                res[i] = t0
                t0 += 3
            else:
                print(-1)
                return 0
        else:
            if t2 <= N:
                res[i] = t2
                t2 += 3
            elif t0 <= N:
                res[i] = t0
                t0 += 3
            else:
                print(-1)
                return 0
    print(" ".join(map(str, res)))
    return 0


main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())


# p = [[] for _ in range(N)]
# c = [[] for _ in range(N)]
p = defaultdict(int)
c = defaultdict(set)

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] = a
    c[a].add(b)

three = set()
for i in range(N):
    if not i in p:
        continue
    parent = p[i]
    for j in list(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:
n = int(input())
S = list(range(1, n+1))
for i in range(n-1):
  a, b = map(int, input().split())
  x = S.index(a) 
  y = S.index(b)
  S[x] = b
  S[y] = a
T = map(str, S)
print(''.join(T))

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)])

print(-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:
#!/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 >= 2):
                        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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap





@mt
def slv(N, AB):
    G = defaultdict(set)
    for a, b in AB:
        G[a].add(b)
        G[b].add(a)

    def bfs(s):
        q = deque([s])
        done = {s: 0}
        d3 = []
        while q:
            u = q.popleft()
            for v in G[u]:
                if v not in done:
                    done[v] = done[u] + 1
                    if done[v] == 3 and s < v:
                        d3.append(v)
                    elif done[v] < 3:
                        q.append(v)
        return d3

    l3e = []
    rg = defaultdict(set)
    for u in range(1, N+1):
        for v in bfs(u):
            l3e.append((u, v))
            rg[u].add(v)
            rg[v].add(u)


    def dfs(a, unused_num, rem_v):
        if not rem_v:
            return a
        u, count = rem.pop()
        for c in unused_num:
            for v in rg[u]:
                if a[v] == -1:
                    pass
                elif (c + a[v]) % 3 != 0 and (c * a[v]) % 3 != 0:
                    break
            else:
                a[u] = c
                unused_num.remove(c)
                r = dfs(a, unused_num, rem)
                if r:
                    return r
                a[u] = -1
                unused_num.add(c)
        return False


    rem = [(k, len(rg[k])) for k in rg]
    rem.sort()
    ans = [-1] * (N+1)
    r = dfs(ans, set(range(1, N+1)), rem)
    if not r:
        return -1

    unused = set(range(1, N+1)) - set(r)
    for i in range(1, N+1):
        if ans[i] == -1:
            ans[i] = unused.pop()
    return ans[1:]


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    print(*slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
def dfs(tree, cursor, parent):
  print(cursor, parent)
  rtn = deque()
  for child in tree[cursor]:
    for mago in tree[child]:
      if parent != 0:
        rtn.append((parent, mago))
      for c2 in tree[cursor]:
        if child != c2:
          rtn.append((c2, mago))
    rtn += dfs(tree, child, cursor)
  return rtn

N = int(input())
T = [deque() for _ in range(N+1)]
seen = [False]*(N+1)
a, b = map(int, input().split())
a, b = min(a, b), max(a, b)
T[a].append(b)
seen[a] = True
seen[b] = True
for _ in range(N-2):
  a, b = map(int, input().split())
  a, b = min(a, b), max(a, b)
  if not seen[a]:
    T[b].append(a)
  else:
    T[a].append(b)
  seen[a] = True
  seen[b] = True
dist3s = dfs(T, 1, 0) 
print(dist3s)

Submission status: Wrong Answer

Solution code:
import random
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
ans=[str(i+1) for i in range(n)]
random.shuffle(ans)
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
# coding: utf-8

n = input()
abl = [map(int, raw_input().split()) for _ in xrange(n - 1)]

ps = range(1, n+1)
confirmed = [False] * n

def get_edges_startat(xi):
    return [edge for edge in abl if edge[0] == xi]

def get_edges_endat(xi):
    return [edge for edge in abl if edge[1] == xi]

def condcheck(i, j):
    ret = (ps[i-1] + ps[j-1]) % 3 == 0 or  (ps[i-1] * ps[j-1]) % 3 == 0
    #print 'condcheck', i, j, '=>',ret
    return ret

def tryit(i, j):
    #print 'try'
    # 未確定で条件を満たすものを見つけてswap
    for k in xrange(i+1,n+1):
        if not confirmed[k-1]:
            if condcheck(i, k):
                #print 'swap', j, k
                ps[j-1], ps[k-1] = ps[k-1], ps[j-1]
                confirmed[j-1] = True
                #print ps
                #print confirmed
                return True
    return False

_es = []
def main():
    for i in xrange(1, n+1):
        #print 'ni=',i
        # uddのパターンを抽出
        for e1 in get_edges_endat(i):
            for e2 in get_edges_startat(e1[0]):
                # ループバックの検出
                if e2[1] == i:
                    #print 'stop loop back',e1,e2
                    continue
                for e3 in get_edges_startat(e2[1]):
                    #print 'udd', i, '->', e1[0], '->', e2[1], '->', e3[1]
                    _es.append((i, e3[1]))

                    # 条件を満たすかチェック
                    j = e3[1]
                    if not condcheck(i, j):
                        ret = tryit(i, j)
                        if not ret:
                            return False

        # dddのパターンを抽出
        for e1 in get_edges_startat(i):
            for e2 in get_edges_startat(e1[1]):
                for e3 in get_edges_startat(e2[1]):
                    #print 'ddd', i, '->', e1[1], '->', e2[1], '->', e3[1]
                    _es.append((i, e3[1]))

                    # 条件を満たすかチェック
                    j = e3[1]
                    if not condcheck(i, j):
                        ret = tryit(i, j)
                        if not ret:
                            return False
        
        confirmed[i-1] = True

    return True

if main():
    print ' '.join(map(str, ps))
    #print 'dist 3 nodes:'
    #for i, j in _es:
    #    if (ps[i-1]+ps[j-1])%3==0:
    #        print i,j,',',ps[i-1],'+',ps[j-1],'=',ps[i-1]+ps[j-1]
    #    if (ps[i-1]*ps[j-1])%3==0:
    #        print i,j,',',ps[i-1],'*',ps[j-1],'=',ps[i-1]*ps[j-1]
else:
    print -1

Submission status: Wrong Answer

Solution code:
N = int(input())
from collections import defaultdict
flag = [0 for i in range(N)]
G = defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

numbers1 = [i for i in range(1, N+1) if i % 3 == 1]
numbers2 = [i for i in range(1, N+1) if i % 3 == 2]
numbers3 = [i for i in range(1, N+1) if i % 3 == 0]


ansl = []
try:
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            if numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
except:
    print(-1)

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]]])
    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:
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)


# First bfs to find a leaf
source = 1
dist = {}
q = deque()
q.append(source)
dist[source] = 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

source = node
dist = {}
q = deque()
q.append(source)
dist[source] = 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

if max(dist.values()) <= 2:
    print(" ".join(map(str, range(1, N + 1))))
    exit()

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:
import sys
from collections import defaultdict, deque
readline = sys.stdin.readline

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    deg[a] += 1
    deg[b] += 1


def dist_3(i):
    q = deque([i])
    pair = []
    for a in G[i]:
        for b in G[a]:
            for c in G[b]:
                pair.append(c)
    return pair


ans = list(range(1, n+1))
idx = sorted(range(n), key=lambda x:deg[x])
#for i in range(n//3):
 #   ans[idx[i]], ans[(i+1)*3] = ans[(i+1)*3], ans[idx[i]]
print(*ans)