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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, a: "List[int]", b: "List[int]"):
    mat = [[] for _ in range(N+1)]

    for i in range(N-1):
        mat[a[i]].append(b[i])
        mat[b[i]].append(a[i])
    
    # 各頂点から距離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(mod2_num):
                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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, groupby
from math import sqrt, factorial, log
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop
import sys
stdin = sys.stdin
mod = 10**9 + 7

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

N = ni()
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = na()
    a -= 1; b -= 1
    G[a].append(b)

node = deque([0])
a = [[] for _ in range(N)]
a[0] = 0
while node:
    j = node.pop()
    ai = (a[j] + 1) % 3
    for i in G[j]:
        node.append(i)
        a[i] = ai

c = Counter(a)
values, counts = zip(*c.most_common())
if N % 3 == 0:
    if set(counts) != set([N//3]):
        print(-1)
        quit()
    z, o, t = 1, 2, 3
    ans = list()
    for i in range(N):
        if a[i] == 0:
            ans.append(z)
            z += 3
        elif a[j] == 1:
            ans.append(o)
            o += 3
        else:
            ans.append(t)
            t += 3

else:
    if set(counts) != set([N//3, N//3+1]):
        print(set(counts), set([N//3, N//3+1]))
        print(-1)
        quit()
    z, o, t = 1, 2, 3
    ans = list()
    for i in range(N):
        if a[i] == values[0]:
            ans.append(z)
            z += 3
        elif a[i] == values[1]:
            ans.append(o)
            o += 3
        else:
            ans.append(t)
            t += 3
print(*ans)

Submission status: Runtime Error

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 nubmerofone > 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: Runtime Error

Solution code:
from collections import Counter
def main():
    N=int(input())
    AB=[list(map(int, input().split())) for _ in range(N-1)]
    G=[[]for _ in range(N)]
    cnt=[0]*N
    for a,b in AB:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        cnt[a-1]+=1
        cnt[b-1]+=1
    CI=sorted(((c,i) for i,c in enumerate(cnt)), reverse=True)
    ans=[0]*N
    C=[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()
        for v in G[u]:
            if v!=p:
                stack.append((v,u,d^1))
                C[v]=d
    X=sum(C)
    use=[False]*N
    for j,(c,i) in enumerate(CI[:N//3],1):
        ans[i]=j*3
        for u in G[i]:
            use[u]=True
    k=[i for i in range(1,N+1,3)]
    l=[i for i in range(2,N+1,3)]
    for i,c in enumerate(C):
        if c and not use[u]:
            if not k:
                print(-1)
                return
            ans[i]=k.pop()
            k+=3
        if not c and not use[u]:
            if not l:
                print(-1)
                return
            ans[i]=l.pop()
            l+=3
    for i in range(N):
        if ans[i]==0:
            if k:
                ans[i]=k.pop()
            elif l:
                ans[i]=l.pop()
            else:
                print(-1)
                return
    print(*ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
from collections import defaultdict
import sys
N=int(input())
G=defaultdict(list)
for i in range(N-1):
  a,b=map(int,input().split())
  G[a].append(b)
  G[b].append(a)
  
def dfs(N):
  ans=defaultdict(list)
  for i in range(1,N+1):
    s=i
    stack=[]
    stack.append(s)
    seen=[]
    seen.append(s)
    prev=defaultdict(list)
    while len(stack)!=0:
      u=stack.pop()
      if u!=s and prev[u][1]==3:
        if u in ans[s] or s in ans[u]:
          pass
        else:
          s,u=min(s,u),max(s,u)
          ans[s].append(u)
      elif u!=s and prev[u][1]>3:
        pass
      else:
        if u==s:
          for v in G[u]:
            if v not in seen:
              seen.append(v)
              stack.append(v)
              prev[v]=[u,1]
        else:
          for v in G[u]:
            if v not in seen:
              seen.append(v)
              stack.append(v)
              prev[v]=[u,prev[u][1]+1]
  return ans

three=dfs(N)

init=1
P=[str(i) for i in range(1,N+1)]
for i in three.keys():
  for j in three[i]:
    if (i+j)%3==0 or (i*j)%3==0:
      pass
    else:
      P[j-1]=str(3*init)
      P[3*init-1]=str(j)
      init+=1
print(' '.join(P))

Submission status: Runtime Error

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_2, pre_1):
    pre_2_mod = pre_2 % 3
    if pre_2 == -1:
        for i in [1, 2, 0]:
            if len(nums[i]) > 0:
                out = nums[i].pop()
                break
    else:
        if pre_2_mod != 0:
            if len(nums[3 - (pre_2_mod)]) > 0:
                out = nums[3 - (pre_2_mod)].pop()
            else:
                if len(nums[0]) > 0:
                    out = nums[0].pop()
                else:
                    print(-1)
                    exit()
        else:
            if len(nums[1]) > len(nums[2]):
                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_1, out)

dfs(1, 1, -1, -1)
print(" ".join(list(map(str, ans))))

Submission status: Runtime Error

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

ans=["3" for i in range(n)]
print(ans)
a=' '.join(ans)
print(a)

Submission status: Runtime Error

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

print(-1)

Submission status: Runtime Error

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

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
L = [-1]*n
dist = [-1]*n
F_1 = [i for i in range(1, n+1) if i%3==1]
F_2 = [i for i in range(1, n+1) if i%3==2]
F_0 = [i for i in range(1, n+1) if i%3==0]
def dfs_1(v):
  stack = [v]
  D = [-1]*n
  D[v] = 0
  while stack:
    i = stack.pop()
    for nv in T[i]:
      if D[nv] == -1:
        D[nv] = D[i] + 1
        stack.append(nv)
  return D.index(max(D))
s = dfs_1(0)
dist[s] = 0
def dfs_2():
  S = [s]
  while S:
    v = S.pop()
    if dist[v]%2:
      if F_1:
        L[v] = F_1.pop()
      else:
        L[v] = F_0.pop()
    else:
      if F_2:
        L[v] = F_2.pop()
      else:
        L[v] = F_0.pop()
    for nv in T[v]:
      if dist[nv] == -1:
        dist[nv] = dist[v] + 1
        S.append(nv)
dfs_2()
print(*L)

Submission status: Runtime Error

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

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

print(" ".join(ans))

Submission status: Runtime Error

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

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

print(" ".join(ans))

Submission status: Runtime Error

Solution code:
import sys
import collections
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

b=bfs(0)
for i in range(n):
  b[i]%=3

c=collections.Counter(b)
v=list(c.values())
if max(v)-min(v)>=2:
  print(-1)
  sys.exit()

ans=[]
l1=[]
l2=[]
l3=[]
for i in range(1,n+1):
  if i%3==1:
    l1.append(i)
  elif i%3==2:
    l2.append(i)
  else:
    l3.append(i)
ct1=0
ct2=0
ct3=0

if n%3==0:
  for i in range(n):
    if b[i]%3==0:
      ans.append(l1[ct1])
      ct1+=1
    if b[i]%3==1:
      ans.append(l2[ct2])
      ct2+=1
    if b[i]%3==2:
      ans.append(l3[ct3])
      ct3+=1

if n%3==1:
  x=v.index(max(v))
  for i in range(n):
    if b[i]%3==x:
      ans.append(l1[ct1])
      ct1+=1
    if b[i]%3==(x+1)%3:
      ans.append(l2[ct2])
      ct2+=1
    if b[i]%3==(x+2)%3:
      ans.append(l3[ct3])
      ct3+=1

if n%3==2:
  x=v.index(min(v))
  for i in range(n):
    if b[i]%3==(x+1)%3:
      ans.append(l1[ct1])
      ct1+=1
    if b[i]%3==(x+2)%3:
      ans.append(l2[ct2])
      ct2+=1
    if b[i]%3==x:
      ans.append(l3[ct3])
      ct3+=1

for i in range(n):
  ans[i]=str(ans[i])
print(' '.join(ans))

Submission status: Runtime Error

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

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
L = [-1]*n
dist = [-1]*n
dist[0] = 0
F_1 = [i for i in range(1, n+1) if i%3==1]
F_2 = [i for i in range(1, n+1) if i%3==2]
F_0 = [i for i in range(1, n+1) if i%3==0]
def dfs(v):
  if dist[v]%2:
    if F_1:
      L[v] = F_1.pop()
    else:
      L[v] = F_0.pop()
  else:
    if F_2:
      L[v] = F_2.pop()
    else:
      L[v] = F_0.pop()
  for nv in T[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v] + 1
      dfs(nv)
dfs(0)
print(*L)

Submission status: Runtime Error

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)
Ans=[0]*n
Ans[0]=1
ct1,ct2,ct3=1,0,0
for i in range(1,n):
  if depth(i)%2==0:
    if 3*ct1+1<=n:
      Ans[i]=3*ct1+1
      ct1+=1
    else:
      Ans[i]=3*ct3+3
      ct3+=1
  else:
    if 3*ct2+2<=n:
      Ans[i]=3*ct2+2
      ct2+=1
    else:
      Ans[i]=3*ct3+3
      ct3+=1
if max(Ans)>n:
  print(-1)
else:
  print(*Ans)

Submission status: Runtime Error

Solution code:
n = int(input())

edge = [[] for i in range(n)]
ans = [-1] * n
odd = []
even =[]
nums = [[],[],[]]
for i in range(1,n+1):
    nums[i % 3].append(i)

def dfs(x, last = -1, d = 0):
    if d % 2 == 0: even.append(x)
    else: odd.append(x)
    for nxt in edge[x]:
        if nxt == last:continue
        dfs(nxt, x, d + 1)

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

dfs(0)

zerocnt = len(nums[0])

if len(even) <= zerocnt:
    for even_node in even:
        ans[even_node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for odd_node in odd:
        ans[odd_node] = rest.pop()

elif len(odd) <= zerocnt:
    for odd_node in odd:
        ans[odd_node] = nums[0].pop()
    rest = nums[0] + nums[1] + nums[2]
    for even_node in even:
        ans[even_node] = rest.pop()

else:
    for num in nums[1]:
        ans[even.pop()] = num
    for num in nums[2]:
        ans[odd.pop()] = num
    rest = nums[0]
    for even_node in even:
        ans[even_node] = rest.pop()
    for odd_node in odd:
        ans[odd_node] = rest.pop()

print(*ans)

Submission status: Runtime Error

Solution code:
def examA():
    S = SI()
    if len(S)%2==1:
        print("No")
        return
    for i in range(len(S)//2):
        if S[i*2:i*2+2]!="hi":
            print("No")
            return
    print("Yes")
    return

def examB():
    a, b, M = LI()
    A = LI()
    B = LI()
    D = [LI()for _ in range(M)]
    ans = min(A) + min(B)
    for x,y,c in D:
        cur = A[x-1]+B[y-1]-c
        ans = min(ans,cur)
    print(ans)
    return

def examC():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    L = bfs(N,0,V)
    #print(L)
    odd = 0
    for l in L:
        if l==-1:
            print(-1)
            return
        if l%2==1:
            odd += 1
    G = []
    if odd*2<N:
        for i in range(N):
            if L[i]%2==1:
                G.append(i)
    else:
        for i in range(N):
            if L[i]%2==0:
                G.append(i)

    used = [False]*(N+1)
    ans = [0]*N
    if N//3>=len(G):
        cur = 3
        for g in G:
            ans[g] = cur
            used[cur] = True
            cur += 3
        cur = 1
        for i in range(N):
            if ans[i]!=0:
                continue
            while(used[cur]):
                cur += 1
            ans[i] = cur
            used[cur] = True
    else:
        cur = 1
        for g in G:
            ans[g] = cur
            used[cur] = True
            cur += 3
        cur = 1
        for i in range(N):
            if ans[i]!=0:
                continue
            while(used[cur]):
                cur += 1
            ans[i] = cur
            used[cur] = True
    print(" ".join(map(str,ans)))
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int llo;
#define a first
#define  b second
#define endl "\n"
vector<llo> adj[200001];
llo tot=3;
llo tot2=1;
llo col[200001];
llo dfs(llo no,llo co=0,llo par=-1){
	col[no]=co;
	for(auto j:adj[no]){
		if(j==par){
			continue;
		}
		dfs(j,(co+1)%2,no);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo aa,bb;
	llo n;
	cin>>n;
	for(llo i=0;i<n-1;i++){
		cin>>aa>>bb;
		adj[aa-1].pb(bb-1);
		adj[bb-1].pb(aa-1);
	}
	dfs(0);
	llo ans[n];
	memset(ans,0,sizeof(ans));
	for(llo i=0;i<n;i++){
		if(col[i]==0){
			if(tot<=n){
				ans[i]=tot;
				tot+=3;
			}
			else{
				ans[i]=tot2;
				tot2+=3;
			}
		}
	}
	llo tot3=2;
	for(llo i=0;i<n;i++){
		if(col[i]==1){
			if(tot2<=n){
				ans[i]=tot2;
				tot2+=3;
			}
			else{
				ans[i]=tot3;
				tot3+=3;
			}
		}
	}
	for(llo i=0;i<n;i++){
		cout<<ans[i]<<" ";
	}












	return 0;
}