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: Accepted

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

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
'''
p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''


#a = list(map(int, input().split()))


n = int(input())
es = []
nb = [[] for i in range(n)]

for i in range(n-1):
    aa,bb = list(map(int, input().split()))
    a,b = aa-1,bb-1
    nb[a].append(b)
    nb[b].append(a)
#print(nb)

side = [[],[]]
checked = [-1 for i in range(n)]

queue = [0]
side[0].append(0)
checked[0] = 0
fin = 0

while(True):
    if(len(queue) == fin):
        break
    seeing = queue[fin]
    fin+=1
    
    for j in range(len(nb[seeing])):
        nextval = nb[seeing][j]
        if(checked[nextval]==-1):
            nextside =1 - checked[seeing]
            checked[nextval] = nextside
            side[nextside].append(nextval)
            queue.append(nextval)

#print(side)
nums3 = [n//3,n//3,n//3]

if(n%3 >= 1):
    nums3[0]+=1
if(n%3 == 2):
    nums3[1]+=1

#print(nums3)


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

if(len(side[0]) <= nums3[2]):
    
    cou0 = len(side[0])
    cou1 = len(side[1])
    
    non3 = []
    for i in range(n):
        if((i+1)%3 != 0):
            non3.append(i+1)
    
    for i in range(cou0):
        ans[side[0][i]] = 3 + 3*i
    for j in range(nums3[2] - cou0):
        ans[side[1][j]] = 3 + 3*(j+cou0)
    startnum = nums3[2] - cou0
    for j in range(cou1 - startnum):
        ans[side[1][startnum+j]] = non3[j]
    
    #print("side0")
    
elif(len(side[1]) <= nums3[2]):
    
    cou0 = len(side[0])
    cou1 = len(side[1])
    
    non3 = []
    for i in range(n):
        if((i+1)%3 != 0):
            non3.append(i+1)
    
    for i in range(cou1):
        ans[side[1][i]] = 3 + 3*i
    for j in range(nums3[2] - cou1):
        ans[side[0][j]] = 3 + 3*(j+cou1)
    startnum = nums3[2] - cou1
    for j in range(cou0 - startnum):
        ans[side[0][startnum+j]] = non3[j]
        #print("now",startnum+j,non3[j])

    #print("side1")
else:
    
    cou0 = len(side[0])
    cou1 = len(side[1])
    
    for i in range(nums3[0]):
        ans[side[0][i]] = 1 + 3*i
        
    for i in range(nums3[1]):
        ans[side[1][i]] = 2 + 3*i
        
    start0 = nums3[0]
    done0 = cou0 - nums3[0]
    start1 = nums3[1]
    done1 = cou1 - nums3[1]
    for i in range(done0):
        ans[side[0][start0 + i]] = 3 + 3 * i
    for i in range(done1):
        ans[side[1][start1 + i]] = 3 + 3 * (i + done0)

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

Submission status: Accepted

Solution code:
n=int(input())
ans=[0]*n
three=n//3
two=(n-three)//2
one=n-three-two
t=[[]for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  t[a].append(b)
  t[b].append(a)
th=[]
Q=[0]
visited={0}
ma=0
thi=-1
while Q:
  th.append(Q)
  if len(Q)>ma:
    ma=len(Q)
    thi=len(th)-1
  P=[]
  for j in Q:
    for i in t[j]:
      if i not in visited:
        P.append(i)
        visited.add(i)
  Q=P
odd=even=0
for i in range(len(th)):
  if i%2==1:odd+=len(th[i])
  else:even+=len(th[i])
if odd>one+three:
  flag="error"
  d=0
elif even>one+three:
  flag="error"
  d=1
else:
  flag="normal"

if flag=="error":
  sudenideta=set()
  num=3
  for i in range(d,len(th),2):
    for j in th[i]:
      ans[j]=num
      sudenideta.add(num)
      num+=3
  num=1
  for i in range(d^1,len(th),2):
    for j in th[i]:
      while num in sudenideta:num+=1
      ans[j]=num
      sudenideta.add(num)
      num+=1
else:
  odd_num=2
  even_num=1
  three_num=3
  for i in range(len(th)):
    for j in th[i]:
      if i%2==1:
        if odd_num>n:
          ans[j]=three_num
          three_num+=3
        else:
          ans[j]=odd_num
          odd_num+=3
      else:
        if even_num>n:
          ans[j]=three_num
          three_num+=3
        else:
          ans[j]=even_num
          even_num+=3
print(*ans)

Submission status: Accepted

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
cnt = [0, 0]
while q :
  cur, pre, cost = q.pop()
  dist[cur] = cost
  cnt[cost] += 1
  for nex in vec[cur] :
    if nex != pre :
      q.append((nex, cur, cost ^ 1))

one = 1
two = 2
three = 3
if cnt[0] < (N + 2) // 3 :
  for i in range(N) :
    if dist[i] == 0 :
      dist[i] = three
      three += 3
    elif one <= N :
      dist[i] = one
      one += 3
    elif two <= N :
      dist[i] = two
      two += 3
    else :
      dist[i] = three
      three += 3
      
elif cnt[1] < (N + 1) // 3 :
  for i in range(N) :
    if dist[i] == 1 :
      dist[i] = three
      three += 3
    elif one <= N :
      dist[i] = one
      one += 3
    elif two <= N :
      dist[i] = two
      two += 3
    else :
      dist[i] = three
      three += 3
      
else :
  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: Accepted

Solution code:
class Tree:
    def __init__(self, N):
        self.N = N # #vertices
        self.D = (self.N-1).bit_length() # #iterations in doubling
        self.E = [{} for _ in range(N)]
    
    def add_edge(self, init, end, weight, undirected=False):
        self.E[init][end] = weight
        if undirected: self.E[end][init] = weight
    
    def lca_initialize(self):
        self.dfs(0)
        self.doubling()
    
    def dfs(self, root):
        # parents[v]: the parent of the vertex v
        # depth[v]: the depth of the vertex v from the root
        # dist[v]: the distance of the vertex v from the root.
        self.parent = [None] * self.N
        self.depth = [None] * self.N
        self.dist = [float('inf')] * self.N
        self.parent[root] = -1; self.depth[root] = 0; self.dist[root] = 0;
        stack = [root]
        while stack:
            v = stack.pop()
            for u, d in self.E[v].items():
                if self.depth[u] is not None: continue
                self.parent[u] = v
                self.depth[u] = self.depth[v] + 1
                self.dist[u] = self.dist[v] + d
                stack.append(u)
    
    def doubling(self):
        # O(N log N) time
        self.next = [[-1] * self.N for _ in range(self.D)]
        for v in range(self.N):
            self.next[0][v] = self.parent[v]
        for d in range(self.D - 1):
            for v in range(self.N):
                if self.next[d][v] != -1:
                    self.next[d + 1][v] = self.next[d][self.next[d][v]]
    
    def lca(self, u, v):
        # O(log N) time
        # the depth of v is set to be no less than that of u
        if self.depth[u] > self.depth[v]: u, v = v, u
        # find the ancestor of v with the same depth as that of u
        diff = self.depth[v] - self.depth[u]
        for i in range(diff.bit_length()):
            if diff & (1 << i): v = self.next[i][v]
        if u == v: return u
        for i in range(self.depth[u].bit_length() - 1, -1, -1):
            pu, pv = self.next[i][u], self.next[i][v]
            if pu != pv: u, v = pu, pv
        return self.next[0][u]

N = int(input())
tr = Tree(N)
for _ in range(N-1):
    a, b = map(int, input().split())
    tr.add_edge(a-1, b-1, 1, undirected=True)
tr.dfs(0)
d_odd, d_even = [], []
rem = [[] for _ in range(3)]
for i in range(N):
    if tr.depth[i] % 2 == 0: d_even.append(i)
    else: d_odd.append(i)
    rem[(i+1)%3].append(i+1)
P = [0] * N
if len(d_odd) < len(d_even):
    if len(d_odd) <= len(rem[0]):
        for i in d_odd: P[i] = rem[0].pop()
    else:
        for i in d_odd:
            if rem[2]:
                P[i] = rem[2].pop()
            else:
                P[i] = rem[0].pop()
    temp = rem[2] + rem[0] + rem[1]
    for i in d_even: P[i] = temp.pop()
else:
    if len(d_even) <= len(rem[0]):
        for i in d_even: P[i] = rem[0].pop()
    else:
        for i in d_even:
            if rem[2]:
                P[i] = rem[2].pop()
            else:
                P[i] = rem[0].pop()
    temp = rem[2] + rem[0] + rem[1]
    for i in d_odd: P[i] = temp.pop()
print(*P)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return input().split()
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    def f(point, pre):
        p = lis[point]
        for nex in edg[point]:
            if nex == pre:
                continue
            lis[nex] = p + 1
            f(nex, point)
        return
    n = II()
    ab = LIR_(n - 1)
    lis = [-1] * n
    edg = [[] for _ in range(n)]
    for a, b in ab:
        edg[a].append(b)
        edg[b].append(a)
    lis[0] = 1
    f(0, -1)
    d = [0, 0]
    for i in lis:
        d[i & 1] += 1
    ans = [None] * n
    if d[0] <= n // 3:
        t = 1
        for i in range(n):
            if lis[i] & 1:
                continue
            ans[i] = str(t * 3)
            t += 1
        m = t * 3
        t = 1
        for i in range(n):
            if ans[i]:
                continue
            ans[i] = str(t)
            t += 1
            if t >= m:
                continue
            if t % 3 == 0:
                t += 1
    elif d[1] <= n // 3:
        t = 1
        for i in range(n):
            if not lis[i] & 1:
                continue
            ans[i] = str(t * 3)
            t += 1
        m = t * 3
        t = 1
        for i in range(n):
            if ans[i]:
                continue
            ans[i] = str(t)
            t += 1
            if t >= m:
                continue
            if t % 3 == 0:
                t += 1
    else:
        t = n // 3
        odd = 1
        even = 2
        for i in range(n):
            if t:
                if lis[i] & 1:
                    if d[1] <= n // 3 + (n % 3 >= 1):
                        ans[i] = str(odd)
                        odd += 3
                    else:
                        ans[i] = str(3 * t)
                        t -= 1
                        d[1] -= 1
                else:
                    if d[0] <= n // 3 + (n % 3 >= 2):
                        ans[i] = str(even)
                        even += 3
                    else:
                        ans[i] = str(3 * t)
                        t -= 1
                        d[0] -= 1 
            else:
                if lis[i] & 1:
                    ans[i] = str(odd)
                    odd += 3
                else:
                    ans[i] = str(even)
                    even += 3
    print(" ".join(ans))


    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    from collections import deque
    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    one_num = 0
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] ^ 1
                if seen[u]:
                    one_num += 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()
    two_num = N - one_num

    one = list(range(1, N+1, 3))
    two = list(range(2, N+1, 3))
    three = list(range(3, N+1, 3))
    three_num = N // 3

    ans = [0] * (N+1)
    if one_num <= three_num:
        for v in range(1, N+1):
            if seen[v]:
                ans[v] = three.pop()
            else:
                if one:
                    ans[v] = one.pop()
                elif two:
                    ans[v] = two.pop()
                else:
                    ans[v] = three.pop()
    elif two_num <= three_num:
        for v in range(1, N+1):
            if not seen[v]:
                ans[v] = three.pop()
            else:
                if one:
                    ans[v] = one.pop()
                elif two:
                    ans[v] = two.pop()
                else:
                    ans[v] = three.pop()
    else:
        for v in range(1, N+1):
            if seen[v]:
                if one:
                    ans[v] = one.pop()
                else:
                    ans[v] = three.pop()
            else:
                if two:
                    ans[v] = two.pop()
                else:
                    ans[v] = three.pop()
    print(*ans[1:])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(u=0,pu=-1,color=0):
        cc[u]=color
        cntc[color]+=1
        for cu in to1[u]:
            if pu==cu:continue
            dfs(cu,u,1-color)


    n=II()
    to1=[set() for _ in range(n)]
    cc=[0]*n
    cntc=[0]*2
    for _ in range(n-1):
        a,b=MI1()
        to1[a].add(b)
        to1[b].add(a)
    dfs()
    #print(cc)
    #print(cntc)
    m1=(n-1)//3+1
    m2=(n-2)//3+1
    m3=n//3
    #print(m1,m2,m3)
    if cntc[0]<cntc[1]:mnc=0
    else:mnc=1
    p1=list(range(1,n+1,3))
    p2=list(range(2,n+1,3))
    p3=list(range(3,n+1,3))
    ans=[-1]*n
    if cntc[mnc]<=m3:
        #mncの色に3の倍数、あと自由
        for u in range(n):
            if cc[u]==mnc:ans[u]=p3.pop()
            else:
                if p1:ans[u]=p1.pop()
                elif p2:ans[u]=p2.pop()
                else:ans[u]=p3.pop()
    elif cntc[1-mnc]>m1+m3:
        print(-1)
        exit()
    else:
        #多い方にm1、少ない方にm2を振って、残りをm3で埋める
        for u in range(n):
            if cc[u]==mnc:
                if p2:ans[u]=p2.pop()
                else:ans[u]=p3.pop()
            else:
                if p1:ans[u]=p1.pop()
                else:ans[u]=p3.pop()
    print(*ans)

main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
P=[0 for i in range(N+1)]

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

d1=[10**9 for i in range(N+1)]
d1[1]=0
Q=[]
for i in L[1]:
    Q.append([i,1])
#print(Q)
#print(d1)
for i in range(N-1):
    d1[Q[i][0]]=Q[i][1]
    for j in L[Q[i][0]]:
        if d1[j]==10**9:
            Q.append([j,Q[i][1]+1])
#print(d1)
ODD=0
EVE=0
for i in range(1,N+1):
    if d1[i]%2==0:
        EVE+=1
    else:
        ODD+=1
#print(ODD,EVE)
M1=[]
M2=[]
M3=[]
for i in range(1,N+1):
    if i%3==1:
        M1.append(i)
    elif i%3==2:
        M2.append(i)
    else:
        M3.append(i)
if min(ODD,EVE)*2<max(ODD,EVE):
    if ODD<EVE:
        D={}
        ans=[0 for i in range(N+1)]
        cnt=0
        for i in range(1,N+1):
            if d1[i]%2==1:
                ans[i]=M3[cnt]
                D[M3[cnt]]=1
                cnt+=1
        num=1
        for i in range(1,N+1):
            #print(D)
            if d1[i]%2==0:
                if num in D:
                    #print(True)
                    num+=1
                ans[i]=num
                num+=1
    else:
        D={}
        ans=[0 for i in range(N+1)]
        cnt=0
        for i in range(1,N+1):
            if d1[i]%2==0:
                ans[i]=M3[cnt]
                D[M3[cnt]]=1
                cnt+=1
        num=1
        for i in range(1,N+1):
            #print(D)
            if d1[i]%2==1:
                if num in D:
                    #print(True)
                    num+=1
                ans[i]=num
                num+=1
    print(*ans[1:])
else:
    ans=[0 for i in range(N+1)]
    m1=0
    m2=0
    m3=0
    for i in range(1,N+1):
        if d1[i]%2==0:
            if m1<len(M1):
                ans[i]=M1[m1]
                m1+=1
            else:
                ans[i]=M3[m3]
                m3+=1
        else:
            if m2<len(M2):
                ans[i]=M2[m2]
                m2+=1
            else:
                ans[i]=M3[m3]
                m3+=1
    print(*ans[1:])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
class Tree:
  C, RL = {}, {}
  R, N, D, S, P, T = None, None, None, None, None, None
  TL = None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N #各ノードのランク
    s.R[root] = 1
    s.RL[1] = [root] #各ランクのノード
    s.S = {} #各ノードの子ノード
    s.P = [-1] * s.N #各ノードの親ノード
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i
      s.D += 1
      F = Ft
  def dfs(s, x, y, r): #xからyまでの道O(M)
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False
  def dist(s, x): #最遠のノード,距離
    t = [-1] * s.N
    S = [x]
    ans = x
    ansn = 0
    t[x] = 0
    while S != []:
      k = S.pop()
      for i in s.C[k]:
        if t[i] == -1:
          t[i] = t[k] + 1
          S.append(i)
          if t[i] > ansn:
            ansn = t[i]
            ans = i
    return ans, ansn
  def getDi(s, x = 0): #直径
    a, _ = s.dfs(x)
    b, ans = s.dfs(a)
    return ans
  def getDeep(s, x): #xの子孫のうち一番深い深さ
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n): #xのn世代前の親
    if n == 0:
      return x
    if s.P[x] == -1:
      return -n
    return s.getParent(s.P[x], n - 1)
  def abList(s):
    A = []
    B = []
    for i in range(s.N):
      if s.R[i] % 2 == 0:
        A.append(i)
      else:
        B.append(i)
    if len(A) > len(B):
      return [B, A]
    else:
      return [A, B]



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

A = []
B = []
C = []

for i in range(1, N + 1):
  if i % 3 == 0:
    C.append(i)
  elif i % 3 == 1:
    A.append(i)
  else:
    B.append(i)

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

T.makeRank(0)

A, B = T.abList()

c = N // 3

Ans = [0] * N
if len(A) <= c:
  t = 3
  k = 1
  for i in A:
    Ans[i] = t
    t += 3
    c -= 1
  for i in range(N):
    if Ans[i] == 0:
      if c != 0:
        Ans[i] = t
        c -= 1
        t += 3
      else:
        Ans[i] = k
        k += 1
        if k % 3 == 0:
          k += 1
else:
  t = 3
  n = N // 3
  if N % 3 != 0:
    n += 1
  k = 1
  for i in range(n):
    Ans[A[i]] = k
    k += 3
  for i in range(n, len(A)):
    Ans[A[i]] = t
    t += 3
  n = N // 3
  if N % 3 == 2:
    n += 1
  k = 2
  for i in range(n):
    Ans[B[i]] = k
    k += 3
  for i in range(n, len(B)):
    Ans[B[i]] = t
    t += 3

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

Submission status: Accepted

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: Accepted

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 and tw > n:
        ans[i] = th
        th += 3
      elif 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: Accepted

Solution code:
import sys
import numpy as np
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 1 mod 3のグループを先に決めてあとは順番に

N = ir()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

root = 1
rank = [0] * (N+1) # 1-indexed
rank[1] = 1
parent = [0] * (N+1) # 1-indexed
order = []
stack = [root]
while stack:
    cur = stack.pop()
    r = rank[cur]
    order.append(cur)
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        rank[next] = r + 1
        stack.append(next)

counter = [0, 0]
for x in rank[1:]:
    counter[x%2] += 1
num0mod3 = N // 2
num1mod3 = (N+2) // 3
num2mod3 = (N+1) // 3
answer = [0] * (N+1)
if max(counter) >= num1mod3 + num2mod3:
    #この時ここに1mod3、2mod3を全部入れる
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N+1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 1
            if cur % 3 == 0:
                cur += 1
            if cur > N:
                break
    cur = 1
    for j in range(1, N+1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)
else:
    #ここではcounterの多い方にnum1mod3を入れる
    if counter[0] > counter[1]:
        index = 0
    else:
        index = 1
    cur = 1
    used = set()
    for i in range(1, N+1):
        if rank[i] % 2 == index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 2
    for i in range(1, N+1):
        if rank[i] % 2 == 1-index:
            answer[i] = cur
            used.add(cur)
            cur += 3
            if cur > N:
                break
    cur = 1
    for j in range(1, N+1):
        while cur in used:
            cur += 1
        if answer[j] == 0:
            answer[j] = cur
            used.add(cur)

print(*answer[1:])

Submission status: Accepted

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

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

E = [[] for _ in [0]*N]
for a,b in AB:
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)


D = dist_bfs(N,E,0)

e = []
o = []
cnt = 0
for i,d in enumerate(D):
    if d%2==0:
        e.append(i)
        cnt += 1
    else:
        o.append(i)
if cnt > N-cnt:
    e,o = o,e
    cnt = N-cnt
ans = [0]*N
if cnt <= N//3:
    done = set()
    j = 3
    for i in e:
        ans[i] = j
        done.add(j)
        j += 3
    j = 1
    for i in o:
        ans[i] = j
        j += 1
        while j in done:
            j += 1
else:
    done = set()
    j = 1
    for i in e:
        ans[i] = j
        done.add(j)
        j += 3
        if j > N: j = 3
    j = 2
    for i in o:
        ans[i] = j
        j += 1
        while j in done:
            j += 1
print(*ans)

Submission status: Accepted

Solution code:
import sys


def part(s, links):
    grp = [set(), set()]
    q = [(s, -1, 0)]
    while q:
        v, p, g = q.pop()
        grp[g].add(v)
        for u in links[v]:
            if u == p:
                continue
            q.append((u, v, g ^ 1))
    return grp


def solve(n, links):
    grp = part(0, links)
    can = [[], [], []]
    for i in range(1, n + 1):
        can[i % 3].append(i)
    # print(grp)
    # print(can)

    if len(grp[0]) > len(grp[1]):
        grp[0], grp[1] = grp[1], grp[0]
    if len(can[1]) > len(can[2]):
        can[1], can[2] = can[2], can[1]

    ans = [0] * n

    if len(grp[0]) <= len(can[0]):
        for i, v in enumerate(grp[0]):
            ans[v] = can[0].pop()
        can = can[0] + can[1] + can[2]
        for i, v in enumerate(grp[1]):
            ans[v] = can.pop()
        return ans

    for i, v in enumerate(grp[0]):
        if can[1]:
            ans[v] = can[1].pop()
        else:
            ans[v] = can[0].pop()
    for i, v in enumerate(grp[1]):
        if can[2]:
            ans[v] = can[2].pop()
        else:
            ans[v] = can[0].pop()
    return ans


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print(*solve(n, links))

Submission status: Accepted

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

if len(odd) <= m:
    s2 += s1+s0
else:
    s2 += s0+s1

for i in odd:
    ans[i] = s2.pop()
for i in even:
    ans[i] = s2.pop()
    

print(*ans)