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
from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis

N = int(input())

lis = [[] for i in range(N)]
for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

dis,plis = NC_Dij(lis,0)
nums = [0,0]
zt = [N//3]*3
if N % 3 == 1:
    zt[1] += 1
if N % 3 == 2:
    zt[1] += 1
    zt[2] += 1

for i in range(N):
    nums[dis[i] % 2] += 1

#print (zt,nums)
if max(zt[1],zt[2]) > max(nums):
    print (-1)
    sys.exit()

if nums[0] < nums[1]:
    sub = 1
else:
    sub = 0

use = [1,2,3]
ans = []
flag = True
for i in range(N):

    nex = use[(dis[i]+sub) % 2]
    use[(dis[i]+sub) % 2] += 3
    if nex > N:
        ans.append(use[2])
        use[2] += 3
        if ans[-1] > N:
            print (-1)
            sys.exit()
    else:
        ans.append(nex)
        
print (" ".join(map(str,ans)))

Submission status: Wrong Answer

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

N = int(input())
AB = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(N - 1)]

edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

E = [0] * N

for s in range(N):
    que = deque([(s, 0)])
    visited = [False] * N
    T = []
    while que:
        now, depth = que.pop()
        visited[now] = True

        if depth == 3:
            T.append(now)
            continue

        for to in edges[now]:
            if not visited[to]:
                que.append((to, depth + 1))
    E[s] = (s, T)
E.sort(key=lambda a: len(a[1]), reverse=True)

ans = [-1] * N

now = 3
canUse = set(range(1, N + 1))
for s, T in E:
    if len(T) == 1:
        break
    ans[s] = now
    now += 3

canUse = deque(canUse)
for i, a in enumerate(ans):
    if a != -1:
        continue
    ans[i] = canUse.pop()

print(*ans)

Submission status: Wrong Answer

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

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

a, b, c = n//3, n//3, n//3
if n%3 == 1:
    a += 1
elif n%3 == 2:
    a += 1
    b += 1

zero = 0
one = 0
two = 0
for i in range(1, n+1):
    if ans[i] == 0 and zero <= a-1:
        ans[i] = zero*3+1
        zero += 1
    elif ans[i] == 1 and one <= b-1:
        ans[i] = one*3+2
        one += 1
    else:
        ans[i] = two*3+3
        two += 1
print(" ".join(map(str, ans[1:])))

Submission status: Wrong Answer

Solution code:
n = int(input())
connect = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

mark = [0] * n
color = 0
todo = {(0, 0, -1)}
while todo:
    v, color, pre = todo.pop()
    mark[v] = color
    for child in connect[v]:
        if child != pre:
            todo.add((child, 1 - color, v))
numberofone = sum(mark)
numberofzero = n - numberofone
if numberofone > numberofzero:
    numberofone, numberofzero = numberofzero, numberofone

zero = n // 3
one = (n + 2) // 3
two = (n + 1) // 3
ans = []
for m in mark:
    if m == 0 and one > 0:
        ans.append(one*3-2)
        one -= 1
    elif m == 1 and two > 0:
        ans.append(two*3-1)
        two -= 1
    else:
        if zero < 0:
            print(-1)
            exit()
        ans.append(zero*3)
        zero -= 1
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

used = [False] * (N + 1)
nodes = [0] * (N + 1)
used[1] = True
nodes[1] = 1
for i in range(1, N):
    q = [(n, i, i, 1) for n in links[i]]
    while q:
        n, b, p, h = q.pop()
        if h == 3:
            if nodes[n] != 0:
                continue
            for i in range(1, N + 1):
                if used[i]:
                    continue
                if (b + i) % 3 == 0 or (b * i) % 3 == 0:
                    nodes[n] = i
                    used[i] = True
                    break
        else:
            for nn in links[n]:
                if nn != p:
                    q.append((nn, i, n, h + 1))

k = 1
for i in range(1, N + 1):
    if nodes[i] != 0:
        continue
    for j in range(k, N + 1):
        if used[j]:
            continue
        nodes[i] = j
        k = j

print(*nodes[1:])

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)]
    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)
    distType = [0, 0]
    zero, one, two = N // 3, N // 3, N // 3
    if N % 3 == 1: one += 1
    elif N % 3 == 2:
        one += 1
        two += 1

    while q:
        nowNode, preNode, dist = q.popleft()
        Dist[nowNode] = dist
        distType[dist % 2] += 1
        for nextNode in Edge[nowNode]:
            if nextNode != preNode: q.append((nextNode, nowNode, dist + 1))
    
    Ans = [-1] * N
    modZero = 0
    modOne = 0
    modTwo = 0
    for i, d in enumerate(Dist):
        if d % 2 == 0:
            if modOne < one: 
                Ans[i] = 3 * modOne + 1
                modOne += 1
            elif modZero < zero:
                Ans[i] = 3 * modZero + 3
                modZero += 1
            else:
                print(-1)
                break
        else:
            if modTwo < one:
                Ans[i] = 3 * modTwo + 2
                modTwo += 1
            elif modZero < zero:
                Ans[i] = 3 * modZero + 3
                modZero += 1
            else:
                print(-1)
                break
    else:
        print(" ".join(map(str, Ans)))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#C
#入力
N=int(input())
X=[list(map(int,input().split())) for i in range(N-1)]

#前提関数
def c_1(X,n,j):#nとの距離がiのノードを返す
    t=X[n-1]
    s=[]
    for i in range(len(t)):
        if t[i]==j:
            s.append(i+1)
    return s

#処理
Y=[ [ -1 for i in range(N)] for j in range(N)]
Z=[ [ 0 for i in range(N)] for j in range(N)]
for i in range(N):
    Y[i][i]=0
for i in X:
    Y[i[0]-1][i[1]-1]=1
    Y[i[1]-1][i[0]-1]=1

for i in range(2):#三段探索する
    
    for j in range(N):#一列づつ見る
        t=c_1(Y,j+1,i+1)
        for l in t:
            s=c_1(Y,l,1)
            for m in s:
                if Y[j][m-1]==-1:
                    Y[j][m-1]=i+2

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
ed = [tuple(map(int, input().split())) for _ in range(n-1)]
g = [list() for _ in range(n)]
for a,b in ed:
  g[a-1].append(b-1)
  g[b-1].append(a-1)
bi = [0]*n

def dfs(v, p):
  for x in g[v]:
    if x == p: continue
    bi[x] = 1 ^ bi[v]
    dfs(x, v)
  return

dfs(0,-1)

if sum(bi)*2 < n:
  bi = [1^x for x in bi]
  
one = sum(bi)
two = n - one
if two > n//3 and max(0, one - (n//3) - (n%3 > 0)) + max(0, two - (n//3) - (n%3 > 1)) > n // 3:
  print(-1); exit(0)
on = 1
tw = 2
th = 3
ans = [0]*n
if two <= n//3:
  for i in range(n):
    if bi[i]:
      if on > n:
        ans[i] = tw
        tw += 3
      else:
        ans[i] = on
        on += 3
    else:
      ans[i] = th
      th += 3
  print(*ans)
  exit(0)

for i in range(n):
  if bi[i]:
    if on > n:
      ans[i] = th
      th += 3
    else:
      ans[i] = on
      on += 3
  else:
    if tw > n:
      ans[i] = th
      th += 3
    else:
      ans[i] = tw
      tw += 3
print(*ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
d = [-1] * n
s = [0]
d[0] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            d[node] = (d[p] + 1) % 2
            s.append(node)
p = 1
q = 2
t = 3
ans = [0] * n
for i in range(n):
    if p <= n and d[i] == 0:
        ans[i] = p
        p += 3
    elif q <= n and d[i] == 1:
        ans[i] = q
        q += 3
    else:
        ans[i] = t
        t += 3
if t > n + 3:
    p = 1
    q = 2
    t = 3
    ans = [0] * n
    for i in range(n):
        if p <= n and d[i] == 1:
            ans[i] = p
            p += 3
        elif q <= n and d[i] == 0:
            ans[i] = q
            q += 3
        else:
            ans[i] = t
            t += 3
    if t > n + 3:
        print(-1)
        exit(0)
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n=int(input())
for i in range(n-1):
    a=input()

ans=["3" for i in range(n)]

a=' '.join(ans)
print(a)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
T = [deque() for _ in range(N+1)]
TA = [[0 for _ in range(N+1)] for __ in range(N+1)]
for _ in range(N-1):
  a, b = map(int, input().split())
  T[a].append(b)
  T[b].append(a)
  TA[a][b] = 1
  TA[b][a] = 1
dist3s = deque()
i = 1
while i <= N:
  dist1 = T[i]
  dist2 = deque()
  for d1 in dist1:
    for d2 in T[d1]:
      if d2 != i and i < d2:
        dist2.append(d2)
  for d1 in dist1:
    for d2 in dist2:
      if TA[d1][d2] == 0:
        dist3s.append(sorted([d1, d2]))
  i += 1
print(dist3s)

Submission status: Wrong Answer

Solution code:
print("3 3 3 3 3")

Submission status: Wrong Answer

Solution code:
print("1 2 5 4 3")

Submission status: Wrong Answer

Solution code:
N = int(input())
e = [list(map(int, input().split())) for _ in range(N-1)]

ans = []
for i in range(1, N+1):
    ans.append(str(3 * i))

print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

mem = [[[] for _ in range(3)] for _ in range(6)]
for i,d in enumerate(depth):
    if d%3==0:
        mem[0][0].append(i)
        mem[3][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[0][1].append(i)
            mem[3][2].append(i)
        else:
            mem[0][2].append(i)
            mem[3][1].append(i)
    else:
        if (d//3)%2:
            mem[0][2].append(i)
            mem[3][1].append(i)
        else:
            mem[0][1].append(i)
            mem[3][2].append(i)
    d += 1
    if d%3==0:
        mem[1][0].append(i)
        mem[4][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[1][1].append(i)
            mem[4][2].append(i)
        else:
            mem[1][2].append(i)
            mem[4][1].append(i)
    else:
        if (d//3)%2:
            mem[1][2].append(i)
            mem[4][1].append(i)
        else:
            mem[1][1].append(i)
            mem[4][2].append(i)
    d += 1
    if d%3==0:
        mem[2][0].append(i)
        mem[5][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[2][1].append(i)
            mem[5][2].append(i)
        else:
            mem[2][2].append(i)
            mem[5][1].append(i)
    else:
        if (d//3)%2:
            mem[2][2].append(i)
            mem[5][1].append(i)
        else:
            mem[2][1].append(i)
            mem[5][2].append(i)

for k in range(6):
    ans = [None] * N
    for i in range(1,N+1):
        if len(mem[k][i%3])==0:
            break
        j = mem[k][i%3].pop()
        ans[j] = i
    else:
        print(*ans)
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
for i in range(n-1):
    a,b = map(int,input().split())

print(-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
for _ in range(N - 1):
    input()

for i in range(N):
    if i == N - 1:
        print(3, end="")
    else:
        print(3, end=" ")

Submission status: Wrong Answer

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

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N)]
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
connect = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

mark = [0] * n
color = 0
todo = {(0, 0, -1)}
while todo:
    v, color, pre = todo.pop()
    mark[v] = color
    for child in connect[v]:
        if child != pre:
            todo.add((child, 1 - color, v))

zero = n // 3
one = (n + 2) // 3
two = (n + 1) // 3
ans = []
for m in mark:
    if m == 0 and one > 0:
        ans.append(one*3-2)
        one -= 1
    elif m == 1 and two > 0:
        ans.append(two*3-1)
        two -= 1
    else:
        ans.append(zero*3)
print(*ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse.csgraph import floyd_warshall

N = int(input())

edge = [[-1]*(N+2)for i in range(N+2)]

for i in range(N-1):
  a,b=map(int,input().split())
  edge[a][b] = 1
  edge[b][a] = 1 
  
G = csgraph_from_dense(edge, null_value=-1)
d = floyd_warshall(G)
print(d)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


n,*ab = [int(i)-1 for i in read().split()]
n += 1
mp = iter(ab)

g = [[] for _ in range(n)]
for a,b in zip(mp,mp):
    g[a].append(b)
    g[b].append(a)

q = [0]
parent = [-1]*n
depth = [0]*n
#order = []

while q:
    v = q.pop()
    d = depth[v]
    #order.append(v)
    for c in g[v]:
        if c != parent[v]:
            q.append(c)
            parent[c] = v
            depth[c] = d+1

odd = [i for i,d in enumerate(depth) if d&1]
even = [i for i,d in enumerate(depth) if d&1==0]

s0 = list(range(3,n+1,3))
s1 = list(range(1,n+1,3))
s2 = list(range(2,n+1,3))

ans = [0]*n

m = n//3
if len(even) <= m:
    odd,even = even,odd

s2 += s1+s0
#print(s0,s1,s2)
#print(odd)
#print(even)
#print(s0)
for i in odd:
    ans[i] = s2.pop()
for i in even:
    ans[i] = s2.pop()

print(*ans)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    edge = [[] 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)
    
    for i in range(N):
        if len(edge[i]) == 1:
            start = i
            break

    rest = [[] for _ in range(3)]
    go = [False for _ in range(N)]
    rest[0].append(start)
    go[start] = True
    q = deque([start])
    use = 1
    while q:
        now = q.popleft()
        for fol in edge[now]:
            if not go[fol]:
                rest[use%3].append(fol)
                go[fol] = True
                q.append(fol)
        use += 1
    
    t = rest[0]+rest[1]+rest[2]
    ans = [0 for _ in range(N)]
    for x,num in enumerate(t):
        ans[num] = x+1
        
    print(*ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# Author: cr4zjh0bp
# Created: Sun Mar  8 12:25:37 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N = ni()
ab = nan(N - 1)

for i in range(N):
    if i >= 1:
        print(" ", end="")
    print(3, end="")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


n,*ab = [int(i)-1 for i in read().split()]
n += 1
mp = iter(ab)

g = [[] for _ in range(n)]
for a,b in zip(mp,mp):
    g[a].append(b)
    g[b].append(a)

q = [0]
parent = [-1]*n
depth = [0]*n
#order = []

while q:
    v = q.pop()
    d = depth[v]
    #order.append(v)
    for c in g[v]:
        if c != parent[v]:
            q.append(c)
            parent[c] = v
            depth[c] = d+1

odd = [i for i,d in enumerate(depth) if d&1]
even = [i for i,d in enumerate(depth) if d&1==0]

s0 = list(range(3,n+1,3))
s1 = list(range(1,n+1,3))
s2 = list(range(2,n+1,3))

ans = [0]*n

m = n//3
if len(even) <= m:
    odd,even = even,odd

s2 += s1+s0
#print(s0,s1,s2)
#print(odd)
#print(even)
#print(s0)
for i in odd:
    ans[i] = s2.pop()
for i in even:
    ans[i] = s2.pop()

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
from collections import defaultdict as dd
dic = dd(lambda: [])
for i in range(n-1):
  a, b = map(int, input().split())
  dic[a] += [b]
  dic[b] += [a]

Pairs = []
for i in range(1, n + 1):
  len1 = dic[i]
  len2 = []
  for node in len1:
    for cand in dic[node]:
      if cand != i:
        len2.append(cand)
  len3 = []
  for node in len2:
    for cand in dic[node]:
      if cand != i and cand not in len1 and cand not in len2:
        len3.append(cand)
  #print(i, len3)
  
  for cand in len3:
    if i <= cand:
      Pairs.append([i, cand])
#print(Pairs)
for i in range(n-1):
  print(3, end=" ")
print(3)

Submission status: Wrong Answer

Solution code:
n = int(input())
connect = [set() for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

mark = [0] * n
color = 0
todo = {(0, 0, -1)}
while todo:
    v, color, pre = todo.pop()
    mark[v] = color
    for child in connect[v]:
        if child != pre:
            todo.add((child, 1 - color, v))

zero = n // 3
one = (n + 2) // 3
two = (n + 1) // 3
ans = []
for m in mark:
    if m == 0 and one > 0:
        ans.append(one*3-2)
        one -= 1
    elif m == 1 and two > 0:
        ans.append(two*3-1)
        two -= 1
    else:
        ans.append(zero*3)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
for _ in range(N - 1):
    input()

for i in range(N):
    if i == N - 1:
        print(3)
    else:
        print(3, end=" ")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [-1]*N
depth[0] = 0
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)

mem = [[[] for _ in range(3)] for _ in range(3)]
for i,d in enumerate(depth):
    if d%3==0:
        mem[0][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[0][1].append(i)
        else:
            mem[0][2].append(i)
    else:
        if (d//3)%2:
            mem[0][2].append(i)
        else:
            mem[0][1].append(i)
    d += 1
    if d%3==0:
        mem[1][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[1][1].append(i)
        else:
            mem[1][2].append(i)
    else:
        if (d//3)%2:
            mem[1][2].append(i)
        else:
            mem[1][1].append(i)
    d += 1
    if d%3==0:
        mem[2][0].append(i)
    elif d%3==1:
        if (d//3)%2:
            mem[2][1].append(i)
        else:
            mem[2][2].append(i)
    else:
        if (d//3)%2:
            mem[2][2].append(i)
        else:
            mem[2][1].append(i)

for k in range(3):
    ans = [None] * N
    for i in range(1,N+1):
        if len(mem[k][i%3])==0:
            break
        j = mem[k][i%3].pop()
        ans[j] = i
    else:
        assert None not in ans
        print(*ans)
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
d = [-1] * n
s = [0]
d[0] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            d[node] = (d[p] + 1) % 2
            s.append(node)
p = 1
q = 2
t = 3
ans = [0] * n
for i in range(n):
    if p <= n and d[i] == 0:
        ans[i] = p
        p += 3
    elif q <= n and d[i] == 1:
        ans[i] = q
        q += 3
    else:
        ans[i] = t
        t += 3
if t > n:
    print(-1)
else:
    print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import numpy as np
from queue import Queue
import sys

N=int(input())
W={}
for i in range(N):
  W[i]=[]
for i in range(N-1):
  a,b=map(int, input().split())
  W[a-1].append(b-1)
  W[b-1].append(a-1)
  

def Adj(u):
  adj=[]
  for v in range(N):
    if v in W[u]:
    	adj.append(v)
  return adj

def DFS_VISIT(u,time):
  visited[u]=1
  time+=1
  if time>=3:
    print([3]*N)
    sys.exit()
  for v in W[u]:
    if visited[v]:
      continue
    DFS_VISIT(v,time)
      
visited=np.zeros(N,dtype=int)
for s in range(N):
  if visited[s]:
    continue
  DFS_VISIT(s,0)
print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()

	tr = [[] for _ in range(N)]
	ans = [3 for _ in range(N)]

	for i in range(N-1):
		a,b = inputMap()
		a -= 1
		b -= 1

		tr[a].append(b)
		tr[b].append(a)

	#print(tr)
	san = []
	for i in range(N):
		if len(tr[i]) == 0:
			continue
		for j in tr[i]:
			if j == i:
				continue
			for k in tr[j]:
				if k == j or k == i:
					continue
				for ii in tr[k]:
					if ii == j or ii == k or ii == i:
						continue
					if (ii,i) in san:
						continue
					san.append((i,ii))
	print(ans)
	sys.exit()
	#print(san)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
d = [-1] * n
s = [0]
d[0] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            d[node] = (d[p] + 1) % 2
            s.append(node)
p = 1
q = 2
t = 3
ans = [0] * n
for i in range(n):
    if p <= n and d[i] == 0:
        ans[i] = p
        p += 3
    elif q <= n and d[i] == 1:
        ans[i] = q
        q += 3
    else:
        ans[i] = t
        t += 3
print(' '.join(map(str, ans)))

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=[0]*3
g[0]=1
def hu(n,c):
    for i in s[n]:
        if l[i]==None:
            l[i]=c
            g[c%3]+=1
            hu(i,c+1)
l[0]=0
hu(0,1)
if N%3==0:
    if g[0]==g[1]==g[2]:
        a=[1,2,3]
        for i in l:
            print(a[i%3],end=" ")
            a[i%3]+=3
    else:
        print(-1)
elif N%3==1:
    if max(g)-min(g)==1:
        if g[0]==N//3+1:
            a=[1,2,3]
        elif g[1]==N//3+1:
            a=[2,1,3]
        else:
            a=[2,3,1]
        for i in l:
            print(a[i%3],end=" ")
            a[i%3]+=3
    else:
        print(-1)
else:
    if max(g)-min(g)==1:
        if g[0]==N//3:
            a=[3,1,2]
        elif g[1]==N//3:
            a=[1,3,2]
        else:
            a=[1,2,3]
        for i in l:
            print(a[i%3],end=" ")
            a[i%3]+=3
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
for i in range(n-1):
    a, b = list(map(int, input().split()))
if n == 2:
    print(1, 1)
else:
    ans = [3]*n
    print(*ans)

Submission status: Wrong Answer

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

N = int(input())
AB = [tuple(map(lambda a: int(a) - 1, input().split())) for _ in range(N - 1)]

edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a].append(b)
    edges[b].append(a)

E = [0] * N

for s in range(N):
    que = deque([(s, 0)])
    visited = [False] * N
    T = []
    while que:
        now, depth = que.pop()
        visited[now] = True

        if depth == 3:
            T.append(now)
            continue

        for to in edges[now]:
            if not visited[to]:
                que.append((to, depth + 1))
    E[s] = (s, T)
E.sort(key=lambda a: len(a[1]), reverse=True)

ans = [-1] * N
canUse = set(range(1, N + 1))

now = 3
for s, T in E:
    if len(T) == 0:
        continue
    if now <= N:
        ans[s] = now
        canUse.remove(now)
        now += 3
    else:
        L = canUse.copy()
        for to in T:
            if ans[to] == -1 or ans[to] % 3 == 0:
                continue
            K = set()
            for l in L:
                if (l + ans[to]) % 3 != 0:
                    K.add(l)
            L -= K
        if len(L) == 0:
            print(-1)
            exit()
        for l in L:
            ans[s] = l
            break
        canUse.remove(ans[s])

for i in range(N):
    if ans[i] == -1:
        for n in canUse:
            ans[i] = n
            break
        canUse.remove(n)

print(*ans)

Submission status: Wrong Answer

Solution code:
def main():
    N=int(input())
    AB=[list(map(int, input().split())) for _ in range(N-1)]
    G=[[]for _ in range(N)]
    for a,b in AB:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    ans=[0]*N
    S=[[],[],[]]
    for i in range(N+1):
        S[i%3].append(i)
    stack=[(0,-1,0)]
    while stack:
        u,p,d=stack.pop()
        if d%2==0:
            if S[1]:
                ans[u]=S[1].pop()
            elif S[0]:
                ans[u]=S[0].pop()
            else:
                print(-1)
                return
        else:
            if S[2]:
                ans[u]=S[2].pop()
            elif S[0]:
                ans[u]=S[0].pop()
            else:
                print(-1)
                return
        for v in G[u]:
            if v!=p:
                stack.append((v,u,d+1))
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [tuple(map(int, input().split())) for _ in range(n-1)]
if n == 2:
    ans = ['1', '2']
else:
    ans = ['3']*n
    
print(*ans)