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 heapq import heappop, heappush
from collections import deque


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

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


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


root = 0
visited = [-1] * n
def dfs(root):
    q = deque([root])
    visited[0] = 0
    while q:
        v = q.pop()
        for nxt_v in tree[v]:
            if visited[nxt_v] != -1:
                continue
            else:
                visited[nxt_v] = (visited[v] + 1) % 2
                q.append(nxt_v)

for i in range(n):
    if distance2[i] < 3:
        visited[i] = -1

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

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

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


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

set1 = set()
set2 = set()
set3 = set()
for i in range(1, n + 1):
    if i % 3 == 0:
        set3.add(i)
    elif i % 3 == 1:
        set1.add(i)
    elif i % 3 == 2:
        set2.add(i)

ans = [0] * n
num147 = 0
num258 = 0
num369 = 0
for i in range(n):
    if visited[i] == -1:
        continue
    elif visited[i] == 0:
        num = num147 * 3 + 1
        if num > n:
            num = num369 * 3 + 3
            ans[i] = num
            if num > n:
                print(-1)
                exit()
            set3.remove(num)
            num369 += 1
            continue
        ans[i] = num # 1, 4, 7, 10, ...
        set1.remove(num)
        num147 += 1
    else:
        num = num258 * 3 + 2 
        if num > n:
            num = num369 * 3 + 3
            if num > n:
                print(-1)
                exit()
            ans[i] = num
            set3.remove(num)
            num369 += 1
            continue
        ans[i] = num # 2, 5, 8, 11, ...
        set2.remove(num)
        num258 += 1

for i in range(n):
    if ans[i] == 0:
        if set1:
            ans[i] = set1.pop()
        elif set2:
            ans[i] = set2.pop()
        elif set3:
            ans[i] = set3.pop()
print(*ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
ans=[0 for i in range(n+1)]
od=[1]
ev=[]
q=[1]
c=[1 for i in range(n+1)]
c[1]=0
t=0
while q:
    tl=q[:]
    q=[]
    for i in tl:
        for j in edge[i]:
            if c[j]:
                q.append(j)
                c[j]=0
                if t:
                    od.append(j)
                else:
                    ev.append(j)
    t^=1
if len(od)>len(ev):
    od,ev=ev,od
if len(od)<=n//3:
    t=3
    for i in od:
        ans[i]=t
        t+=3
    x=0
    for i,j in enumerate(ans):
        if j==0:
            ans[i]=x
            x+=1
            if x%3==0 and x<=t:
                x+=1
else:
    t=0
    for i in range(1,n+1,3):
        ans[ev[t]]=i
        t+=1
    t=0
    for i in range(2,n+1,3):
        ans[od[t]]=i
        t+=1
    t=0
    for i,j in enumerate(ans):
        if j==0:
            ans[i]=t
            t+=3
print(" ".join(map(str,ans[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)
a = d.count(0)
b = d.count(1)
a, b = max(a, b), min(a, b)
if a > b:
    tmp = 0
else:
    tmp = 1
ans = [0] * n
if a - b <= n // 3:
    p = 1
    q = 2
    t = 3
    for i in range(n):
        if d[i] == tmp:
            if t <= n:
                ans[i] = t
                t += 3
            else:
                ans[i] = p
                p += 3
        else:
            ans[i] = q
            q += 3
else:
    t = 3
    k = 1
    for i in range(n):
        if d[i] == tmp:
            ans[i] = k
            k += 1
            if k % 3 == 0:
                k += 1
        else:
            ans[i] = t
            t += 3
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"

#処理内容
def main():
	N = int(input())
	#1-Nの数を3で割った数の個数(あまり)
	a0 = int(N // 3)
	a1 = int((N + 2) // 3)
	a2 = int((N + 1) // 3)

	#グラフ構築
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#直径2以下の除外処理
	jjj = "Yes"
	BFj = BFS(G, 0, N)
	dist1 = BFj.dist
	val = 0
	pre_node = None
	for i in range(N):
		if dist1[i] > val:
			val = dist1[i]
			pre_node = i

	BFj2 = BFS(G, pre_node, N)
	dist2 = BFj2.dist
	dia = 0
	for i in range(N):
		if dist2[i] > dia:
			dia = dist2[i]

	if dia < 3:
		ans = [i + 1 for i in range(N)]
		print(" ".join(map(str, ans)))
		return

	#偶奇で判断 可能性判定	
	BF = BFS(G, 0, N)
	dist = BF.dist
	dis_even = 0
	dis_odd = 0
	for i in range(N):
		if dist[i] % 2 == 0:
			dis_even += 1
		else:
			dis_odd += 1

	# print(dist)
	# print(dis_odd)
	# print(dis_even)

	ans = [0] * N
	judge = "No"
	if a2 <= dis_odd and a1 <= dis_even:
		judge = "Yes"
		c1 = 0
		c2 = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				if c1 < a2:
					ans[i] = c1 * 3 + 2
					c1 += 1
			else:
				if c2 < a1:
					ans[i] = c2 * 3 + 1
					c2 += 1

		cnt = 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = 3 * cnt
				cnt += 1

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

	elif a1 <= dis_odd and a2 <= dis_even:
		judge = "Yes"
		c1 = 0
		c2 = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				if c1 < a1:
					ans[i] = c1 * 3 + 2
					c1 += 1
			else:
				if c2 < a2:
					ans[i] = c2 * 3 + 1
					c2 += 1

		cnt = 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = 3 * cnt
				cnt += 1

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

	if judge == "No":
		print(-1)

if __name__ == '__main__':
	main()

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 = [i for i in range(1,N+1)]

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

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

	print(ans)
	sys.exit()
	san = []
	for i in range(N):
		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:
import sys
input = sys.stdin.readline
n = int(input())
C = [list(map(int,input().split())) for i in range(n-1)]

V = [0] * (n+1)
PP = [[] for i in range(n+1)]

M = [[] for i in range(n+1)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])

# 1始まりの場合
Q = [[1,-1,-1]]
s = 0
V[1] = 1
while s < len(Q):
    i = Q[s][0]
    p = Q[s][1]
    pp = Q[s][2]
    if pp >= 0:
        for y in M[pp]:
            if y != p:
                PP[y].append(i)
                PP[i].append(y)

    for x in M[i]:
        if V[x] == 0:
            V[x] = 1
            Q.append([x, i, p])
    s += 1
# print(PP)
vv = -1
V = [0] * (n+1)
for i in range(len(PP)):
    if len(PP[i]) == 0:
        vv += 1
        V[i] = -1
# print(vv)
mi = vv

J = [n//3 for i in range(3)]
if n%3==1:
    J[1] += 1
elif n%3==2:
    J[1] += 1
    J[2] += 1
# print(J)
# J[1] = max(0, J[1] - vv//2)
# J[2] = max(0, J[2] - vv//2)
# if vv%2==1:
#     J[1] = max(0, J[1] - 1)
# print(J)

# print("V",V)
# r = -1
# R = [[], []]
QQ = [[] for i in range(n+1)]
for ii in range(n+1):
    if V[ii] == 0:
        # r += 1
        Q = [[ii,1]]
        s = 0
        V[ii] = 1
        while s < len(Q):
            # print(Q)
            i = Q[s][0]
            cc = Q[s][1]
            # if p >= 0:
            #     for y in PP[p]:
            #         if y != i:
            #             QQ[y].append(i)
            #             R[r].append(y)
            #             # QQ[i].append(y)

            for x in PP[i]:
                if V[x] == 0:
                    V[x] = 2 if cc==1 else 1
                    Q.append([x,V[x]])
            s += 1
# print("V",V)

# print(QQ)
R = [[],[]]
for i in range(n+1):
    if V[i] >= 1:
        R[V[i]-1].append(i)

if len(R[1]) > len(R[0]):
    R = [R[1], R[0]]


# print("R",R)
if max(0, J[1]-len(R[0])) + max(0, J[2]-len(R[1])) <= mi:
    ANS = [-1] * n
    for i in R[0]:
        if J[1]==0:
            break
        ANS[i-1] = 1
        J[1] -= 1

    for i in R[1]:
        if J[2] == 0:
            break
        ANS[i-1] = 2
        J[2] -= 1
        
    tt = 0
    # print(ANS)
    for i in range(len(ANS)):
        if ANS[i] == -1:
            while J[tt] == 0:
                tt += 1
            ANS[i] = tt
            J[tt] -= 1
    # print(J)
    # print(ANS)

    K = [1,0,0]
    for i in range(len(ANS)):
        ANS[i] += K[ANS[i]%3] * 3
        K[ANS[i]%3] += 1
    # print(ANS)
    print(" ".join([str(i) for i in ANS]))
else:
    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 not p[i]:
            ans[i] = ind1
            ind1 += 3
            if ind1 > n:
                break
    for i in range(1,n+1):
        if 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 range(1,n+1)))
    print(' '.join(str(num) for num in ans[1:]))



f()

Submission status: Wrong Answer

Solution code:
N = int(input())

a = [0]*(N-1)
b = [0]*(N-1)

x = [0]*N
hoge = []
nyoro = 1
for i in range(N-1):
    a[i], b[i] = map(int, input().split())
    
    if x[a[i]-1] != 0 and x[b[i]-1] == 0:
        x[b[i]-1] = x[a[i]-1] + 1
        if x[b[i]-1] % 2 == 0:
            nyoro += 1
    elif x[a[i]-1] == 0 and x[b[i]-1] != 0:
        x[a[i]-1] = x[b[i]-1] + 1
        if x[a[i]-1] % 2 == 0:
            nyoro += 1
    elif x[a[i]-1] == 0 and x[b[i]-1] == 0:
        if i == 0:
            x[a[i]-1] = 1
            x[b[i]-1] = 2
        else:
            hoge.append(i)

if len(hoge) > 0:
    j = 0
    while len(hoge) > 0:
        i = hoge[j]
        if x[a[i]-1] != 0 and x[b[i]-1] == 0:
            x[b[i]-1] = x[a[i]-1] + 1
            if x[b[i]-1] % 2 == 0:
                nyoro += 1
            hoge.pop(j)
        elif x[a[i]-1] == 0 and x[b[i]-1] != 0:
            x[a[i]-1] = x[b[i]-1] + 1
            if x[a[i]-1] % 2 == 0:
                nyoro += 1
            hoge.pop(j)
        elif x[a[i]-1] == 0 and x[b[i]-1] == 0:
            if j < len(hoge) - 1:
                j += 1
            else:
                j = 0

if abs(N - nyoro * 2) > (N // 3):
    print("-1")
else:
    p = 0
    q = 0
    r = 1
    for i in range(N):
        if x[i] % 2 == 1 and 3 * p + 1 <= N:
            print(3 * p + 1)
            p += 1
        elif x[i] % 2 == 0 and 3 * q + 1 <= N:
            print(3 * q + 2)
            q += 1
        else:
            print(3 * r)
            r += 1

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


zero = 0
one = 0
two = 0
for i in range(1, n+1):
    if ans[i] == 0:
        ans[i] = zero*3+1
        zero += 1
    elif ans[i] == 1:
        ans[i] = one*3+2
        one += 1

three = 0
for i in range(1, n+1):
    if ans[i] > n:
        ans[i] = three*3+3
        three += 1
print(" ".join(map(str, ans[1:])))

Submission status: Wrong Answer

Solution code:
# たしかめさせてくれ〜〜〜〜〜〜〜〜〜！！！！！！！！！！！
print(-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [[] for i in range(N)]
pair1 = [set() for i in range(N)]
pair2 = [set() 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] = set(nowlist)
    for i in nowlist:
        if i < now:
            pair2[now] |= pair1[i]-set([now])
        else:
            for j in ab[i]:
                if j != now:
                    pair2[now].add(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:
import sys
import math
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()


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

d = [[float("inf")]*N for i in range(N)]

for i in range(N-1):
    x, y = map(int, input().split())
    d[x-1][y-1] = 1
    d[y-1][x-1] = 1
for i in range(N):
    d[i][i] = 0 #自身のところに行くコストは０

W = warshall_floyd(d)

index = []

for i in range(len(W)):
    for j in range(i+1, len(W)):
        if W[i][j] == 3:
            tmp = [i, j]
            index.append(tmp)

p = ['1'] * N
for i in index:
    p[i[0]] = '3'
    p[i[1]] = '3'
print(' '.join(p))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))


def main():
    N = INT()
    mat = [[] for _ in range(N+1)]

    for _ in range(N-1):
        a,b = MAP()
        mat[a].append(b)
        mat[b].append(a)
    
    # 各頂点から距離3の頂点を格納、ただし自分より大きいもの
    dist_three = [[] for _ in range(N+1)]

    for root in range(1,N+1):
        queue = deque([(root,0)])
        isVisited = [False]*(N+1)
        while queue:
            node,count = queue.popleft()
            if count == 3 and root < node:
                dist_three[root].append(node)
            elif count == 4:
                break
            isVisited[node] = True

            for next in mat[node]:
                if isVisited[next]:
                    continue
                queue.append((next,count+1))

    answer = [0]*(N+1)

    # multiple_three = []
    # mod1_num = []
    # mod2_num = []
    # for i in range(1,N+1):
    #     if i%3==0:
    #         multiple_three.append(i)
    #     elif i%3==1:
    #         mod1_num.append(i)
    #     else:
    #         mod2_num.append(i)
    # all_num = set(range(1,N+1))

    # for i in range(1,N+1):
    #     if not dist_three[i]:
    #         continue
    #     if dist_three[i] and multiple_three:
    #         answer[i] = multiple_three.pop()
    #     elif dist_three[i] and not multiple_three:
    #         if len(mod1_num) > len(dist_three[i]):
    #             answer[i] = mod2_num.pop()
    #             for next_node in dist_three[i]:
    #                 answer[next_node] = mod1_num.pop()
    #         else:
    #             answer[i] = mod1_num.pop()
    #             for next_node in dist_three[i]:
    #                 answer[next_node] = mod2_num.pop()
        
    # amari_num = list(all_num-set(answer))

    # for i in range(1,N+1):
    #     if answer[i]==0:
    #         answer[i] = amari_num.pop()

    # print(*answer[1:])
    return

if __name__ == '__main__':
    main()

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

if len(q) == 0:
    print(-1)
    exit()


#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]
        elif not chk[now[1]]:
            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]
        else:
            print(-1)
            exit()
print(*ans, sep=" ")

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())

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

inf=float("inf")

prv=[inf]*n
prv[0]=-1
depth=[inf]*n
depth[0]=0
stack=[0]
while stack:
  cur=stack.pop()
  for next in edge[cur]:
    if prv[next]==inf:
      prv[next]=cur
      depth[next]=depth[cur]+1
      stack.append(next)
C=[-1]*n
C2=[-1]*n
def ch(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C[x]=0
    return C[x]
  else:
    for e in edge[x]:
      if e==prv[x]:
        continue
      else:
        ret+=1
    C[x]=ret
    return C[x]
def ch2(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C2[x]=0
    return C2[x]
  else:
    for e in edge[x]:
      if e==prv[x]:
        continue
      else:
        ret+=C[e]
    C2[x]=ret
    return C2[x]
for i in range(n):
  ch(i)
for i in range(n):
  ch2(i)

TH=[0]*n
for i in range(n):
  if i==0:
    cur=0
  elif depth[i]==1:
    cur=C2[prv[i]]-C[i]
  else:
    cur=C2[prv[i]]+C[prv[prv[i]]]-C[i]-1
  if depth[i]>=3:
    cur+=1
  for e in edge[i]:
    if e==prv[i]:
      continue
    else:
      cur+=C2[e]
  TH[i]=cur
TH2=[0]*n
for i in range(n):
  TH2[i]=TH[i]*(10**6)+i
TH2.sort(reverse=True)
Ans=[0]*n
ct1,ct2,ct3=0,0,0
for i in range(3,n,3):
  Ans[TH2[i//3-1]%(10**6)]=i
  ct3+=1
for i in range(n):
  if Ans[i]!=0:
    continue
  else:
    if depth[i]%2==0:
      if 3*ct1+1<=n:
        Ans[i]=3*ct1+1
        ct1+=1
      elif 3*ct3+3<=n:
        Ans[i]=3*ct3+3
        ct3+=1
      else:
        Ans[i]=3*ct2+2
        ct2+=1
    else:
      if 3*ct2+2<=n:
        Ans[i]=3*ct2+2
        ct2+=1
      elif 3*ct3+3<=n:
        Ans[i]=3*ct3+3
        ct3+=1
      else:
        Ans[i]=3*ct1+1
        ct1+=1
if max(Ans)>n:
  print(-1)
else:
  print(*Ans)