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
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)
one = sum(bi)
two = n - one
if one < two:
  one, two = two, one
  bi = [1-x for x in bi]
  
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())
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 = [-1] * (N+1)

q = [[1,1]]

cap_mod0, amari = divmod(N,3)
if amari == 2:
	cap_mod1 = cap_mod0
	cap_mod2 = cap_mod0
elif amari == 1:
	cap_mod1 = cap_mod0
	cap_mod2 = cap_mod0-1
else:
	cap_mod1 = cap_mod0-1
	cap_mod2 = cap_mod0-1

mod0,mod1,mod2 = 1,0,0

while q:
	cp,cd = q.pop(0)
	if cd % 2 == 0:
		if mod1 <= cap_mod1:
			ans[cp] = 1 + 3*mod1
			mod1 += 1
		else:
			ans[cp] = 3 * mod0
			mod0 += 1
	else:
		if mod2 <= cap_mod2:
			ans[cp] = 2 + 3*mod2
			mod2 += 1
		else:
			ans[cp] = 3 * mod0
			mod0 += 1

	for np in E[cp]:
		if ans[np] == -1:
			q.append([np,cd+1])

ans = ans[1:]
print(*ans)

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)
one = sum(bi)
two = n - one
if one < two:
  one, two = two, one
  bi = [1-x for x in bi]
print(bi)
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:
from collections import deque

n = int(input())
t = [list(map(int, input().split())) for i in range(n-1)]

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

#n:頂点数　w:辺の数
d = [[float("inf")]*n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n-1):
    x,y = t[i]
    d[x-1][y-1] = 1
    d[y-1][x-1] = 1
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

q = deque()
d = warshall_floyd(d)

for i in range(n-1):
    for j in range(i,n):
        if d[i][j] == 3:
            q.append((i, j))

#print(q, sep='\n')

ans = [i+1 for i in range(n)]
chk = [False for i in range(n)]

while q:
    now = q.popleft()
    if (ans[now[0]] + ans[now[1]])%3 == 0 or (ans[now[0]]+ans[now[1]])%3 == 0:
        chk[now[0]] = True
        chk[now[1]] = True
        pass
    else:
        if not chk[now[0]]:
            for i in range(n):
                if not chk[i]:
                    ans[now[0]], ans[i] = ans[i], ans[now[0]]
                    if (ans[now[0]] + ans[i])%3 == 0 or (ans[now[0]]+ans[i])%3 == 0:
                        chk[now[0]] = True
                        chk[i] = True
                        pass
                    else:
                        ans[i], ans[now[0]] = ans[now[0]], ans[i]
        else:
            for i in range(n):
                if not chk[i]:
                    ans[now[1]], ans[i] = ans[i], ans[now[1]]
                    if (ans[now[1]] + ans[i])%3 == 0 or (ans[now[1]]+ans[i])%3 == 0:
                        chk[now[1]] = True
                        chk[i] = True
                        pass
                    else:
                        ans[i], ans[now[1]] = ans[now[1]], ans[i]
print(*ans, sep=" ")

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)

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)

#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, 3]
	for i in range(n):
		if signs[i] == more:
			if cur[1] > n:
				ans[i] = cur[2]
				cur[2] += 3
			else:
				ans[i] = cur[1]
				cur[1] += 3
		else:
			if cur[0] > n:
				ans[i] = cur[2]
				cur[2] += 3
			else:
				ans[i] = cur[0]
				cur[0] += 3
	print(*ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [[] for i in range(n)]
m1 = 0
m2 = 0
m3 = 0
ans = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)

visited = set([0])
to_search = [0]
mod_mode = 1
while True:
    temp = []
    for v in to_search:
        if mod_mode == 1:
            if m1*3+1 <= n:
                ans[v] = m1*3+1
                m1 += 1
            else:
                ans[v] = m3*3+3
                m3 += 1
        else:
            if m2*3+2 <= n:
                ans[v] = m2*3+2
                m2 += 1
            else:
                ans[v] = m3*3+3
                m3 += 1
        nex = edge[v]
        for vv in nex:
            if vv not in visited:
                temp.append(vv)
                visited.add(vv)
    if len(temp) == 0:
        break
    to_search = temp

    mod_mode *= -1

for i in range(n-1):
    print(ans[i],end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [map(int,input().split()) for i in range(n-1)]

c = [[] for i in range(n)]

for item in ab:
    a,b = item
    c[a-1].append(b-1)
    c[b-1].append(a-1)

l3_pair = []
cnt = [0 for i in range(n)]

for i in range(n):
    for x in c[i]:
        if x == i:
            continue
        for y in c[x]:
            if y == i or y == x:
                continue
            for z in c[y]:
                if z == i or z == x or z == y:
                    continue
                if (z,i) not in l3_pair:
                    l3_pair.append((i,z))
                    cnt[i] += 1
                    cnt[z] += 1

ans = [i+1 for i in range(n)]

for i in range(n):
    if cnt[i] > 1 and ans[i] % 3 != 0:
        for j in range(i+1,n):
            if ans[j] % 3 == 0:
                tmp = ans[i]
                ans[i] = ans[j]
                ans[j] = tmp

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

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [[] for i in range(n)]
m1 = 0
m2 = 0
m3 = 0
ans = [0 for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)

visited = set([0])
to_search = [0]
mod_mode = 1
while True:
    temp = []
    for v in to_search:
        if mod_mode == 1:
            if m1*3+1 <= n:
                ans[v] = m1*3+1
                m1 += 1
            else:
                ans[v] = m3*3+3
                m3 += 1
        else:
            if m2*3+2 <= n:
                ans[v] = m2*3+2
                m2 += 1
            else:
                ans[v] = m3*3+3
                m3 += 1
        nex = edge[v]
        for vv in nex:
            if vv not in visited:
                temp.append(vv)
                visited.add(vv)
    if len(temp) == 0:
        break
    to_search = temp

    mod_mode *= -1


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
q = [1]
ans2 = [None]*(n+1)
if ans[1] == 1:
    ans2[1] = 2
    ans[1] = -1
    one += 1
else:
    ans2[1] = 1
    ans[1] = -1
    zero += 1


while q:
    now = q.pop()
    for next in tree[now]:
        if ans[next] != -1:
            q.append(next)
            if ans[next] == 1 and one <= b-1:
                ans2[next] = one*3+2
                one += 1
            elif ans[next] == 0 and zero <= a-1:
                ans2[next] = zero*3+1
                zero += 1
            else:
                ans2[next] = two*3+3
                two += 1
            ans[next] = -1


print(" ".join(map(str, ans2[1:])))

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
visited = [False]*N
q = deque([0])  # 始まりのノード
visited[0] = True
distant = [0]*N
distant[0] = 0
while len(q):
    # vは数字, 親のノードのインデックス
    v = q.pop()
    color = 1

    for e in tree[v]:
        if visited[e]:  # 到達済みなら次のノードへ
            continue
        visited[e] = True
        distant[e] = (distant[v] + 1) % 3
        q.append(e)

mod_dict = defaultdict(deque)
for i in range(2, N+1):
    mod_dict[i%3].append(i)
# print(mod_dict)
ans = [1]
for i in range(1, N):
    if len(mod_dict[distant[i]]) > 0:
        ans.append(mod_dict[distant[i]].popleft())
    elif len(mod_dict[distant[0]]) > 0:
        ans.append(mod_dict[distant[0]].popleft())
    else:
        print('-1')
        exit()
print(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from queue import Queue
N=int(input())
G=[[] for i in range(N)]
T=[[] for i in range(N)]
INF=10**9

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

for i in range(N):
    d=[INF for i in range(N)]
    q=[]
    q.append(i)
    d[i]=0
    
    while q:
        u=q.pop(0)
        for j in range(len(G[u])):
            if d[G[u][j]]==INF:
                d[G[u][j]]=d[u]+1
                q.append(G[u][j])
            if d[G[u][j]]==3:
                T[i].append(G[u][j])
            if d[G[u][j]]==4:
                break
print(T)

Submission status: Wrong Answer

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

def search(now):
    global pair1
    global pair2
    nowlist = ab[now]
    pair1[now] = nowlist
    for i in nowlist:
        if i < now:
            p = pair1[i].copy()
            p.remove(now)
            pair2[now] += p
        else:
            for j in ab[i]:
                if j != now:
                    pair2[now].append(j)
for i in range(N):
    search(i)
for i in range(N):
    a = set()
    for j in pair2[i]:
        if j > i:
            a |= set(pair1[j])
    a -= set(pair1[i])
    pair3.append(a)
print(pair1)
print(pair2)
print(pair3)

Submission status: Wrong Answer

Solution code:
def f():
    n = int(input())
    if n <= 3:
        print(' '.join(str(i) for i in range(1,n+1)))
        return
    # n >= 4
    neibors = [[] for i in range(n+1)]
    for i in range(n-1):
        u, v = [int(s) for s in input().split()]
        neibors[u].append(v)
        neibors[v].append(u)
    p = [0]*(n+1)
    flag = 0
    lastLayer = [1]
    p[1] = flag
    while lastLayer:
        flag ^= 1
        thisLayer = []
        for node in lastLayer:
            for nb in neibors[node]:
                if not p[nb]:
                    p[nb] = flag
                    thisLayer.append(nb)
        lastLayer = thisLayer
    # print(p)
    ans = [0]*(n+1)
    ind1 = 1
    ind2 = 2
    ind0 = 3
    for i in range(1,n+1):
        if p[i]:
            ans[i] = ind1
            ind1 += 3
            if ind1 > n:
                break
    for i in range(1,n+1):
        if not p[i]:
            ans[i] = ind2
            ind2 += 3
            if ind2 > n:
                break
    for i in range(1,n+1):
        if not ans[i]:
            ans[i] = ind0
            ind0 += 3
    print(' '.join(str(num) for num in ans[1:]))



f()

Submission status: Wrong Answer

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

for i in range(n):
    print(3,end = " ")

"""r = [[0 for _ in range(n+1)]for o in range(n)]

for i in range(n-1):
    r[a[i]-1][b[i]-1] = 1
    r[b[i]-1][a[i]-1] = 1

dis = [[0 for _ in range(n+1)]for p in range(n+1)]

count = 0

while(count != n):
    dis[a[i]-1][b[i]-1] += 1
    dis[b[i]-1][a[i]-1] += 1
    count += 1"""

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)

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)

#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

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, 3]
	for i in range(n):
		if signs[i] == more:
			if cur[1] > n:
				ans[i] = cur[2]
				cur[2] += 3
			else:
				ans[i] = cur[1]
				cur[1] += 3
		else:
			if cur[0] > n:
				ans[i] = cur[2]
				cur[2] += 3
			else:
				ans[i] = cur[0]
				cur[0] += 3
	print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  a, b = map(int, input().split())
  vec[a-1].append(b-1)
  vec[b-1].append(a-1)
  
q = [(0, -1, 0)]
dist = [0] * N
while q :
  cur, pre, cost = q.pop()
  dist[cur] = cost
  for nex in vec[cur] :
    if nex != pre :
      q.append((nex, cur, cost ^ 1))

one = 1
two = 2
three = 3
for i in range(N) :
  if dist[i] == 0 and one <= N :
    dist[i] = one
    one += 3
  elif dist[i] == 1 and two <= N :
    dist[i] = two
    two += 3
  else :
    dist[i] = three
    three += 3
    
print(*dist)

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)])
    V = set()
    T = set()
    while que:
        now, depth = que.pop()
        V.add(now)

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

        for to in edges[now]:
            if not to in V:
                que.append((to, depth + 1))
    E[s] = (s, T)

print(-1)

Submission status: Wrong Answer

Solution code:
def f():
    n = int(input())
    if n <= 3:
        print(' '.join(str(i) for i in range(1,n+1)))
        return
    # n >= 4
    neibors = [[] for i in range(n+1)]
    for i in range(n-1):
        u, v = [int(s) for s in input().split()]
        neibors[u].append(v)
        neibors[v].append(u)
    p = [0]*(n+1)
    flag = 0
    lastLayer = [1]
    p[1] = flag
    while lastLayer:
        flag ^= 1
        thisLayer = []
        for node in lastLayer:
            for nb in neibors[node]:
                if not p[nb]:
                    p[nb] = flag
                    thisLayer.append(nb)
        lastLayer = thisLayer
    # print(p)
    ans = [0]*(n+1)
    ind1 = 1
    ind2 = 2
    ind0 = 3
    for i in range(1,n+1):
        if p[i]:
            ans[i] = ind1
            ind1 += 3
            if ind1 > n:
                break
    for i in range(1,n+1):
        if not p[i]:
            ans[i] = ind2
            ind2 += 3
            if ind2 > n:
                break
    for i in range(1,n+1):
        if not ans[i]:
            ans[i] = ind0
            ind0 += 3
    print(' '.join(str(num) for num in ans[1:]))



f()

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 and len(mem[k][0])==0:
            break
        if len(mem[k][i%3]):
            j = mem[k][i%3].pop()
        else:
            j = mem[k][0].pop()
        ans[j] = i
    else:
        print(*ans)
        exit()
print(-1)

Submission status: Wrong Answer

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


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

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

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

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

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

        return dis3


    dis3_dict = {i: None for i in range(N)}
    dis3_counts = [0] * N
    for n in range(N):
        ret_calc_dis3 = calc_dis3(n)
        dis3_dict[n] = ret_calc_dis3
        dis3_counts[n] = len(ret_calc_dis3)


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


    # 残ったやつをいい感じにset
    x1 = [n for n in range(1, N + 1) if n % 3 == 1]
    x2 = [n for n in range(1, N + 1) if n % 3 == 2]
    for n in range(N):
        if ans[n] > 0:
            continue

        px = 1 if len(x1) >= len(x2) else 2
        if px == 1:
            ans[n] = x1.pop()
        else:
            ans[n] = x2.pop()

        for to in dis3_dict[n]:
            if (n > to) or (ans[to] > 0):
                continue

            if px == 1:
                if not x2:
                    continue
                ans[to] = x2.pop()
            else:
                if not x1:
                    continue
                ans[to] = x1.pop()

    remains = x1 + x2
    for n in range(N):
        if ans[n] > 0:
            continue
        ans[n] = remains.pop()


    def check(s):
        stack = [(s, 1)]
        visited = [0] * N

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

            if depth == 4:
                continue

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

                if depth + 1 == 4:
                    if not (((ans[s] * ans[to]) % 3) == 0 or ((ans[s] + ans[to]) % 3 == 0)):
                        print(n, to)
                        print(-1)
                        exit()
                stack.append((to, depth + 1))

    for n in range(N):
        check(n)

    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

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)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append((b, 1))
    graph[b].append((a, 1))

counts = [N // 3, (N + 2) // 3, (N + 1) // 3]
vs, _, _ = eulerian_trail(graph, N - 1)
ansmod = [-1] * N
n = 1
while counts[1] > 0 or counts[2] > 0:
    n = 1 if counts[1] >= counts[2] else 2
    i = 0
    while i < N:
        if ansmod[vs[i]] < 0:
            break
        i += 1
    else:
        break
    while i < N:
        v = vs[i]
        if ansmod[v] < 0 and counts[n] > 0:
            counts[n] -= 1
            ansmod[v] = n
        n = 1 if n == 2 else 2
        i += 3

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:
print(*list(range(1, int(input()) + 1)))

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)

use = [1,2,3]

flag = True
ans = []
for i in range(N):

    nex = use[dis[i] % 2]
    use[dis[i] % 2] += 3
    if nex > N:
        nex = use[2]
        use[2] += 3

    if nex > N:
        flag = False
        break
    ans.append(nex)

if flag:
    print (" ".join(map(str,ans)))
    sys.exit()

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

    nex = use[dis[i] % 2]
    use[dis[i] % 2] += 3
    if nex > N:
        nex = use[2]
        use[2] += 3

    if nex > N:
        flag = False
        break
    ans.append(nex)

if flag:
    print (" ".join(map(str,ans)))
    sys.exit()

print (-1)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(20000000)
n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
# 0-2: amari
for i in range(1, n+1):
    nums[i%3].append(i)

ans = [0 for _ in range(n)]
def dfs(step, idx, pre_3, pre_2, pre_1):
    pre_3_mod = pre_3 % 3
    if pre_3 == -1:
        if len(nums[step%3]) > 0:
            out = nums[step%3].pop()
        else:
            for i in [1, 2, 0]:
                if len(nums[i]) > 0:
                    out = nums[i].pop()
                    break
    else:
        if pre_3_mod != 0:
            if len(nums[3 - (pre_3_mod)]) > 0:
                out = nums[3 - (pre_3_mod)].pop()
            else:
                if len(nums[0]) > 0:
                    out = nums[0].pop()
                else:
                    print(-1)
                    exit()
        else:
            if len(nums[0]) > 0:
                out = nums[0].pop()
            else:
                if len(nums[1]) > len(nums[2]) and len(nums[1]) > 0:
                    out = nums[1].pop()
                else:
                    out = nums[2].pop()
    ans[idx-1] = out
    for k in edges[idx].keys():
        if ans[k-1] == 0:
            dfs(step+1, k, pre_2, pre_1, out)

dfs(1, 1, -1, -1, -1)

print(" ".join(list(map(str, ans))))

Submission status: Wrong Answer

Solution code:
from collections import deque
import random
isdebug=0
if isdebug==0:
    N=int(input())
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
else:
    N=10**5
    G=[[] for i in range(N)]
    for i in range(N-1):
        a,b=random.randrange(i+1),i+1
        G[a].append(b)
        G[b].append(a)
H=[[] for i in range(N)]
for i in range(N):
    q=deque([i])
    dist=dict()
    dist[i]=0
    while(len(q)>0):
        r=q.popleft()
        for p in G[r]:
            if p in dist:
                continue
            dist[p]=dist[r]+1
            if dist[p]<3:
                q.append(p)
            else:
                H[i].append(p)
#print(H)
I=[len(H[i]) for i in range(N)]
for i in range(N):
    H[i].sort(key=lambda x:-I[x])
P=[0 for i in range(N)]
X=[]
Y=[]
Z=[]
for i in range(1,N+1):
    if i%3==0:
        X.append(i)
    elif i%3==1:
        Y.append(i)
    else:
        Z.append(i)
J=sorted(range(N),key=lambda x:-I[x])
for j in J:
    q=deque([j])
    if P[j]!=0:
        continue
    if len(X)>0:
        P[j]=X[-1]
        X.pop()
    elif len(Y)>0:
        P[j]=Y[-1]
        Y.pop()
    else:
        P[j]=Z[-1]
        Z.pop()
    while(len(q)>0):
        r=q.pop()
        for p in H[r]:
            if P[p]!=0:
                continue
            if P[r]%3==0:
                if random.randrange(2)==0:
                    if len(Y)>0:
                        P[p]=Y[-1]
                        Y.pop()
                    elif len(Z)>0:
                        P[p]=Z[-1]
                        Z.pop()
                    else:
                        P[p]=X[-1]
                        X.pop()
                else:
                    if len(Z)>0:
                        P[p]=Z[-1]
                        Z.pop()
                    elif len(Y)>0:
                        P[p]=Y[-1]
                        Y.pop()
                    else:
                        P[p]=X[-1]
                        X.pop()
            elif P[r]%3==1:
                if len(Z)>0:
                    P[p]=Z[-1]
                    Z.pop()
                elif len(X)>0:
                    P[p]=X[-1]
                    X.pop()
                else:
                    print(-1)
                    exit()
            else:
                if len(Y)>0:
                    P[p]=Y[-1]
                    Y.pop()
                elif len(X)>0:
                    P[p]=X[-1]
                    X.pop()
                else:
                    print(-1)
                    exit()
print(*P)