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

depth=[0]*N
def dfs(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            depth[nv]=depth[v]+1
            dfs(nv,v)

dfs(0,-1)

even=0
odd=0
for i in range(N):
    if depth[i]%2==0:
        even+=1
    else:
        odd+=1

ans=[0 for i in range(N)]

if N%3==0:
    if min(even,odd)>=N//3:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==0:
                if N//3>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif N//3>even:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==0:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==1:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
    else:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==1:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==0:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
elif N%3==2:
    if min(even,odd)>=N//3+1:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==0:
                if N//3+1>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3+1>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif N//3+1>even:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==0:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==1:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
    else:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==1:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==0:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
else:
    if even>=N//3+1 and odd>=N//3:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==0:
                if N//3+1>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif even>=N//3 and odd>=N//3+1:
        evencount=0
        oddcount=0
        allcount=0
        for i in range(N):
            if depth[i]%2==1:
                if N//3+1>evencount:
                    ans[i]=evencount*3+1
                    evencount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
            else:
                if N//3>oddcount:
                    ans[i]=oddcount*3+2
                    oddcount+=1
                else:
                    ans[i]=(allcount+1)*3
                    allcount+=1
        print(*ans)
    elif N//3>=even:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==0:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==1:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)
    else:
        allcount=0
        d=1
        for i in range(N):
            if depth[i]%2==1:
                ans[i]=3*allcount+3
                allcount+=1
        for i in range(N):
            if depth[i]%2==0:
                if N//3>allcount:
                    ans[i]=3*allcount+3
                    allcount+=1
                else:
                    ans[i]=d
                    if d%3==1:
                        d+=1
                    else:
                        d+=2
        print(*ans)

Submission status: Runtime Error

Solution code:
g = {}
n=int(input())
m = [-1]*n

def dfs(graph,node,height):
    global m
    global zeros
    global ones
    m[node-1]=height
    if height==0:
      zeros+=1
    if height==1:
      ones+=1
    for n in graph[node]:
      if m[n-1]==-1:
        dfs(graph,n,1-height)

zeros=0
ones=0
for i in range(n-1):
  a,b=map(int,input().split())
  if not a in g:
    g[a]=[b]
  else:
    g[a].append(b)
  if not b in g:
    g[b]=[a]
  else:
    g[b].append(a)
dfs(g,1,0)
print(1)

Submission status: Runtime Error

Solution code:
g = {}
n=int(input())
m = [-1]*n

def dfs(graph,node,height):
    global m
    global zeros
    global ones
    m[node-1]=height
    if height==0:
      zeros+=1
    if height==1:
      ones+=1
    for n in graph[node]:
      if m[n-1]==-1:
        dfs(graph,n,1-height)

zeros=0
ones=0
for i in range(n-1):
  a,b=map(int,input().split())
  if not a in g:
    g[a]=[b]
  else:
    g[a].append(b)
  if not b in g:
    g[b]=[a]
  else:
    g[b].append(a)
dfs(g,1,0)
ans=[0]*n
used=[0]*n
r=n//3
if 3*(r+1)<=n:
  r+=1
if zeros<=r:
  current=3
  for i in range(n):
    if m[i]==0:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==1:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
elif ones<=r:
  current=3
  for i in range(n):
    if m[i]==1:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==0:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
else:
  print(a)

Submission status: Runtime Error

Solution code:
g = {}
n=int(input())
m = [-1]*n

def dfs(graph,node,height):
    global m
    global zeros
    global ones
    m[node-1]=height
    if height==0:
      zeros+=1
    if height==1:
      ones+=1
    for n in graph[node]:
      if m[n-1]==-1:
        dfs(graph,n,1-height)

zeros=0
ones=0
for i in range(n-1):
  a,b=map(int,input().split())
  if not a in g:
    g[a]=[b]
  else:
    g[a].append(b)
  if not b in g:
    g[b]=[a]
  else:
    g[b].append(a)
dfs(g,1,0)
ans=[0]*n
used=[0]*n
r=n//3
if 3*(r+1)<=n:
  r+=1
if zeros<=r:
  current=3
  for i in range(n):
    if m[i]==0:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==1:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
elif ones<=r:
  current=3
  for i in range(n):
    if m[i]==1:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==0:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
else:
  if zeros<ones:
    current=1
    for i in range(n):
      if m[i]==0:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
    counter=0
    for i in range(n):
      if m[i]==1:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
  else:
    current=1
    for i in range(n):
      if m[i]==1:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
      counter=0
    for i in range(n):
      if m[i]==0:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
for i in ans:
  print(i)

Submission status: Runtime Error

Solution code:
g = {}
n=int(input())
m = [-1]*n

def dfs(graph,node,height):
    global m
    global zeros
    global ones
    m[node-1]=height
    if height==0:
      zeros+=1
    if height==1:
      ones+=1
    for n in graph[node]:
      if m[n-1]==-1:
        dfs(graph,n,1-height)

zeros=0
ones=0
for i in range(n-1):
  a,b=map(int,input().split())
  if not a in g:
    g[a]=[b]
  else:
    g[a].append(b)
  if not b in g:
    g[b]=[a]
  else:
    g[b].append(a)
dfs(g,1,0)
ans=[0]*n
used=[0]*n
if zeros<=n//3:
  current=3
  for i in range(n):
    if m[i]==0:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==1:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
elif ones<=n//3:
  current=3
  for i in range(n):
    if m[i]==1:
      ans[i]=current
      used[current-1]=1
      current+=3
  counter=0
  for i in range(n):
    if m[i]==0:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          counter+=1
          break
        counter+=1
else:
  if zeros<ones:
    current=1
    for i in range(n):
      if m[i]==0:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
    counter=0
    for i in range(n):
      if m[i]==1:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
  else:
    current=1
    for i in range(n):
      if m[i]==1:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
      counter=0
    for i in range(n):
      if m[i]==0:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
for i in ans:
  print(i)

Submission status: Runtime Error

Solution code:
g = {}
n=int(input())
m = [-1]*n

def dfs(graph,node,height):
    global m
    global zeros
    global ones
    m[node-1]=height
    if height==0:
      zeros+=1
    if height==1:
      ones+=1
    for n in graph[node]:
      if m[n-1]==-1:
        dfs(graph,n,1-height)

zeros=0
ones=0
for i in range(n-1):
  a,b=map(int,input().split())
  if not a in g:
    g[a]=[b]
  else:
    g[a].append(b)
  if not b in g:
    g[b]=[a]
  else:
    g[b].append(a)
dfs(g,1,0)
ans=[0]*n
used=[0]*n
if zeros<=n//3:
  current=3
  for i in range(n):
    if m[i]==0:
      ans[i]=current
      current+=3
      used[current-1]=1
  counter=0
  for i in range(n):
    if m[i]==1:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          break
        counter+=1
elif ones<=n//3:
  current=3
  for i in range(n):
    if m[i]==1:
      ans[i]=current
      current+=3
      used[current-1]=1
  counter=0
  for i in range(n):
    if m[i]==0:
      while True:
        if used[counter]==0:
          ans[i]=counter+1
          break
        counter+=1
else:
  if zeros<ones:
    current=1
    for i in range(n):
      if m[i]==0:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
    counter=0
    for i in range(n):
      if m[i]==1:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
  else:
    current=1
    for i in range(n):
      if m[i]==1:
        ans[i]=current
        used[current-1]=1
        current+=3
        if current>n:
          current=3
      counter=0
    for i in range(n):
      if m[i]==0:
        while True:
          if used[counter]==0:
            ans[i]=counter+1
            counter+=1
            break
          counter+=1
for i in ans:
  print(i)

Submission status: Runtime Error

Solution code:
import collections
n = int(input())
one = collections.deque([1])
two = collections.deque([])
three = collections.deque([])
graph = [[] for _ in range(n)]

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    if i % 3 == 0: two.append(i + 2)
    elif i % 3 == 1: three.append(i + 2)
    else: one.append(i + 2)

que = collections.deque([0])
num = [0] * n
dist = [-1] * n
parity = [0] * 2
dist[0] = 0
flag = True
while len(que) != 0:
    i = que.popleft()
    parity[dist[i] % 2] += 1
    for j in graph[i]:
        if dist[j] != -1: continue
        dist[j] = dist[i] + 1
        que.append(j)

if parity[0] <= n // 3 or parity[1] <= n // 3:
    rem = 0 if parity[0] < parity[1] else 1
    for i, v in enumerate(dist):
        if v % 2 == rem:
            num[i] = str(three.popleft())
        else:
            if len(one) != 0: str(one.popleft())
            elif len(two) != 0: str(two.popleft())
            else: str(three.popleft())
else:
    for i, v in enumerate(dist):
        if v % 2 == 0:
            if len(one) != 0: num[i] = str(one.popleft())
            elif len(three) != 0: num[i] = str(three.popleft())
            else:
                flag = False
                break
        else:
            if len(two) != 0: num[i] = str(two.popleft())
            elif len(three) != 0: num[i] = str(three.popleft())
            else:
                flag = False
                break

print(' '.join(num))

Submission status: Runtime Error

Solution code:
import collections
n = int(input())
one = collections.deque([1])
two = collections.deque([])
three = collections.deque([])
graph = [[] for _ in range(n)]

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    if i % 3 == 0: two.append(i + 2)
    elif i % 3 == 1: three.append(i + 2)
    else: one.append(i + 2)

que = collections.deque([0])
num = [0] * n
dist = [-1] * n
parity = [0] * 2
dist[0] = 0
flag = True
while len(que) != 0:
    i = que.popleft()
    parity[dist[i] % 2] += 1
    for j in graph[i]:
        if dist[j] != -1: continue
        dist[j] = dist[i] + 1
        que.append(j)

if parity[0] <= n // 3 or parity[1] <= n // 3:
    rem = 0 if parity[0] < parity[1] else 1
    for i, v in enumerate(dist):
        if v % 2 == rem: num[i] = str(three.popleft())
    else:
        if len(one) != 0: str(one.popleft())
        elif len(two) != 0: str(two.popleft())
        else: str(three.popleft())
else:
    for i, v in enumerate(dist):
        if v % 2 == 0:
            if len(one) != 0: num[i] = str(one.popleft())
            elif len(three) != 0: num[i] = str(three.popleft())
            else:
                flag = False
                break
        else:
            if len(two) != 0: num[i] = str(two.popleft())
            elif len(three) != 0: num[i] = str(three.popleft())
            else:
                flag = False
                break

print(' '.join(num))

Submission status: Runtime Error

Solution code:
n=int(input())
es=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
color=[-1]*n
from collections import deque
q=deque([])
q.append(0)
color[0]=0
while q:
    now=q.popleft()
    c=color[now]
    for e in es[now]:
        if color[e]==-1:
            color[e]=c^1
            q.append(e)
red=sum(color)
blue=n-red

num_0=deque([i for i in range(3, n+1, 3)])
num_1=deque([i for i in range(1, n+1, 3)])
num_2=deque([i for i in range(2, n+1, 3)])
ans=[0]*n
if red>n//3 and blue>n//3:
    for i in range(n):
        if color[i]==0 and num_1:
            b=num_1.popleft()
            ans[i]=b
        elif color[i]==1 and num_2:
            r=num_2.popleft()
            ans[i]=r
        else:
            x=num_0.popleft()
            ans[i]=x
elif red<=n//3:
    for i in range(n):
        if color[i]==1:
            r=num_2.popleft()
            ans[i]=r
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]==0:
            b=nums.popleft()
            ans[i]=b
else:
    for i in range(n):
        if color[i]==0:
            b=num_1.popleft()
            ans[i]=b
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]==1:
            r=nums.popleft()
            ans[i]=r
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
n=int(input())
es=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
color=[-1]*n
from collections import deque
q=deque([])
q.append(0)
color[0]=0
while q:
    now=q.popleft()
    c=color[now]
    for e in es[now]:
        if color[e]==-1:
            color[e]=c^1
            q.append(e)

red=sum(color)
blue=n-red

num_0=deque([i for i in range(3, n+1, 3)])
num_1=deque([i for i in range(1, n+1, 3)])
num_2=deque([i for i in range(2, n+1, 3)])
ans=[0]*n

if red>n/3 and blue>n/3:
    for i in range(n):
        if color[i]==0 and num_1:
            b=num_1.popleft()
            ans[i]=b
        elif color[i]==1 and num_2:
            r=num_2.popleft()
            ans[i]=r
    nums=deque(num_1+num_2+num_0)
    for i in range(n):
        if ans[i]!=0:
            x=nums.popleft()
            ans[i]=x
elif red<=n/3:
    for i in range(n):
        if color[i]==1:
            r=num_2.popleft()
            ans[i]=r
    nums=deque(num_0+num_1+num_2)
    for i in range(n):
        if color[i]!=1:
            b=nums.popleft()
            ans[i]=b
elif blue<=n/3:
    for i in range(n):
        if color[i]==0:
            b=num_1.popleft()
            ans[i]=b
    nums=deque(num_0+num_1+num_2)
    for i in range(n):
        if color[i]!=0:
            r=nums.popleft()
            ans[i]=r
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
n=int(input())
es=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
color=[-1]*n
from collections import deque
q=deque([])
q.append(0)
color[0]=0
while q:
    now=q.popleft()
    c=color[now]
    for e in es[now]:
        if color[e]==-1:
            color[e]=c^1
            q.append(e)

red=sum(color)
blue=n-red

num_0=deque([i for i in range(3, n+1, 3)])
num_1=deque([i for i in range(1, n+1, 3)])
num_2=deque([i for i in range(2, n+1, 3)])
ans=[0]*n

if red>n/3 and blue>n/3:
    for i in range(n):
        if color[i]==0 and num_1:
            b=num_1.popleft()
            ans[i]=b
        elif color[i]==1 and num_2:
            r=num_2.popleft()
            ans[i]=r
    nums=num_1+num_2+num_0
    for i in range(n):
        if ans[i]!=0:
            x=nums.popleft()
            ans[i]=x
elif red<=n/3:
    for i in range(n):
        if color[i]==1:
            r=num_2.popleft()
            ans[i]=r
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]!=1:
            b=nums.popleft()
            ans[i]=b
elif blue<=n/3:
    for i in range(n):
        if color[i]==0:
            b=num_1.popleft()
            ans[i]=b
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]!=0:
            r=nums.popleft()
            ans[i]=r
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
n=int(input())
es=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
color=[-1]*n
from collections import deque
q=deque([])
q.append(0)
color[0]=0
while q:
    now=q.popleft()
    c=color[now]
    for e in es[now]:
        if color[e]==-1:
            color[e]=c^1
            q.append(e)
if -1 in color:
    print(-1)
    exit()            
red=sum(color)
blue=n-red

num_0=deque([i for i in range(3, n+1, 3)])
num_1=deque([i for i in range(1, n+1, 3)])
num_2=deque([i for i in range(2, n+1, 3)])
ans=[0]*n

if red>n/3 and blue>n/3:
    for i in range(n):
        if color[i]==0 and num_1:
            b=num_1.popleft()
            ans[i]=b
        elif color[i]==1 and num_2:
            r=num_2.popleft()
            ans[i]=r
        else:
            x=num_0.popleft()
            ans[i]=x
elif red<=n/3:
    for i in range(n):
        if color[i]==1:
            r=num_2.popleft()
            ans[i]=r
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]!=1:
            b=nums.popleft()
            ans[i]=b
elif blue<=n/3:
    for i in range(n):
        if color[i]==0:
            b=num_1.popleft()
            ans[i]=b
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]!=0:
            r=nums.popleft()
            ans[i]=r
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
n=int(input())
es=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
color=[-1]*n
from collections import deque
q=deque([])
q.append(0)
color[0]=0
while q:
    now=q.popleft()
    c=color[now]
    for e in es[now]:
        if color[e]==-1:
            color[e]=c^1
            q.append(e)
            
red=sum(color)
blue=n-red

num_0=deque([i for i in range(3, n+1, 3)])
num_1=deque([i for i in range(1, n+1, 3)])
num_2=deque([i for i in range(2, n+1, 3)])
ans=[0]*n

if red>n/3 and blue>n/3:
    for i in range(n):
        if color[i]==0 and num_1:
            b=num_1.popleft()
            ans[i]=b
        elif color[i]==1 and num_2:
            r=num_2.popleft()
            ans[i]=r
        else:
            x=num_0.popleft()
            ans[i]=x
elif red<=n/3:
    for i in range(n):
        if color[i]==1:
            r=num_2.popleft()
            ans[i]=r
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]!=1:
            b=nums.popleft()
            ans[i]=b
elif blue<=n/3:
    for i in range(n):
        if color[i]==0:
            b=num_1.popleft()
            ans[i]=b
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]!=0:
            r=nums.popleft()
            ans[i]=r
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
n=int(input())
es=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
color=[10**10]*n
from collections import deque
q=deque([])
q.append(0)
color[0]=0
while q:
    now=q.popleft()
    c=color[now]
    for e in es[now]:
        if color[e]>c+1:
            color[e]=c+1
            q.append(e)
color=[i%2 for i in color]
red=sum(color)
blue=n-red

num_0=deque([i for i in range(3, n+1, 3)])
num_1=deque([i for i in range(1, n+1, 3)])
num_2=deque([i for i in range(2, n+1, 3)])
ans=[0]*n

if red>n/3 and blue>n/3:
    for i in range(n):
        if color[i]==0 and num_1:
            b=num_1.popleft()
            ans[i]=b
        elif color[i]==1 and num_2:
            r=num_2.popleft()
            ans[i]=r
        else:
            x=num_0.popleft()
            ans[i]=x
elif red<=n/3:
    for i in range(n):
        if color[i]==1:
            r=num_2.popleft()
            ans[i]=r
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]==0:
            b=nums.popleft()
            ans[i]=b
else:
    for i in range(n):
        if color[i]==0:
            b=num_1.popleft()
            ans[i]=b
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]==1:
            r=nums.popleft()
            ans[i]=r
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
n=int(input())
es=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
color=[-1]*n
from collections import deque
q=deque([])
q.append(0)
color[0]=0
while q:
    now=q.popleft()
    c=color[now]
    for e in es[now]:
        if color[e]==-1:
            color[e]=c^1
            q.append(e)

red=sum(color)
blue=n-red

num_0=deque([i for i in range(3, n+1, 3)])
num_1=deque([i for i in range(1, n+1, 3)])
num_2=deque([i for i in range(2, n+1, 3)])
ans=[0]*n

if red>n/3 and blue>n/3:
    for i in range(n):
        if color[i]==0 and num_1:
            b=num_1.popleft()
            ans[i]=b
        elif color[i]==1 and num_2:
            r=num_2.popleft()
            ans[i]=r
        else:
            x=num_0.popleft()
            ans[i]=x
elif red<=n/3:
    for i in range(n):
        if color[i]==1:
            r=num_2.popleft()
            ans[i]=r
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]==0:
            b=nums.popleft()
            ans[i]=b
else:
    for i in range(n):
        if color[i]==0:
            b=num_1.popleft()
            ans[i]=b
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]==1:
            r=nums.popleft()
            ans[i]=r
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
n=int(input())
es=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
color=[-1]*n
from collections import deque
q=deque([])
q.append(0)
color[0]=0
while q:
    now=q.pop()
    c=color[now]
    for e in es[now]:
        if color[e]==-1:
            color[e]=c^1
            q.append(e)
red=sum(color)
blue=n-red

num_0=deque([i for i in range(3, n+1, 3)])
num_1=deque([i for i in range(1, n+1, 3)])
num_2=deque([i for i in range(2, n+1, 3)])
ans=[0]*n
if red>n/3 and blue>n/3:
    for i in range(n):
        if color[i]==0 and num_1:
            b=num_1.popleft()
            ans[i]=b
        elif color[i]==1 and num_2:
            r=num_2.popleft()
            ans[i]=r
        else:
            x=num_0.popleft()
            ans[i]=x
elif red<=n/3:
    for i in range(n):
        if color[i]==1:
            r=num_2.popleft()
            ans[i]=r
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]==0:
            b=nums.popleft()
            ans[i]=b
else:
    for i in range(n):
        if color[i]==0:
            b=num_1.popleft()
            ans[i]=b
    nums=num_0+num_1+num_2
    for i in range(n):
        if color[i]==1:
            r=nums.popleft()
            ans[i]=r
print(' '.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque
    from itertools import chain
    import sys
    input = sys.stdin.readline

    N = int(input())

    graph = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        a, b = (int(x) - 1 for x in input().split())
        graph[a].add(b)
        graph[b].add(a)

    bipartite = [-1] * N
    bipartite[0] = 0

    dq = deque([0])
    while dq:
        v = dq.popleft()
        nb = bipartite[v] ^ 1
        for u in graph[v]:
            if ~bipartite[u]: continue
            bipartite[u] = nb
            dq.append(u)

    s0 = bipartite.count(0)
    s1 = N - s0

    it1 = iter(range(1, N + 1, 3))
    it2 = iter(range(2, N + 1, 3))
    it3 = iter(range(3, N + 1, 3))
    it12 = chain(it1, it2)
    it13 = chain(it1, it3)
    it23 = chain(it2, it3)

    ans = [-1] * N
    K = N // 3
    if s0 <= K:
        for v in range(N):
            if bipartite[v] == 0:
                ans[v] = next(it3)
            else:
                ans[v] = next(it12)
    elif s1 <= K:
        for v in range(N):
            if bipartite[v] == 1:
                ans[v] = next(it3)
            else:
                ans[v] = next(it12)
    else:
        for v in range(N):
            if bipartite[v] == 0:
                ans[v] = next(it13)
            else:
                ans[v] = next(it23)

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from functools import cmp_to_key
import itertools
 
N, T = map(int, readline().split())
m = map(int, read().split())
AB0 = []
AB1 = []
for a,b in zip(m,m):
    if a == 0:
        AB0.append(b)
    else:
        AB1.append((a,b))
 
def sort_func(ab0, ab1):
    a0, b0 = ab0
    a1, b1 = ab1
    return a1*(1+b0) - a0*(1+b1)
 
AB0.sort()
AB1.sort(key=cmp_to_key(sort_func))
AB0, AB1
 
def compute_0():
    INF = T + 1
    dp = [INF] * 40
    dp[0] = 0
    for a,b in AB1:
        for n in range(39, -1, -1):
            if dp[n] > T:
                continue
            x = (dp[n] + 1) * (a + 1) + b
            if x < dp[n+1]:
                dp[n+1] = x
    return dp
 
def compute_1():
    return [0] + list(itertools.accumulate(x + 1 for x in AB0))
 
dp0 = compute_0()
dp1 = compute_1()
 
R = len(dp1) - 1
answer = 0
for i,x in enumerate(dp0):
    if x > T:
        break
    while x + dp1[R] > T:
        R -= 1
    value = i + R
    if answer < value:
        answer = value
 
print(answer)