Problem p02749 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

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

#%%
# 1-indexed
adj_list = [[] for _ in range(N+1)]

for a,b in ab:
    adj_list[a].append(b)
    adj_list[b].append(a)

# DFSで各頂点を1，2に割り当てる．

group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    # 頂点vからpar以外の子へ遷移
    # grpで頂点vのグループを持つ
    
    nxt_grp = grp^3
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    

if min(group_num) <= N//3:
    if min(group_num) == group_num[0]:
        minidx = 1
    else:
        minidx = 2
    
    idx = 3
    idx_n = 1
    for i,g in enumerate(group):
        if i==0:continue
        if g==minidx:
            ans[i] = idx            
            used[idx] = True
            idx += 3

    for i,g in enumerate(group):
        if i==0:continue
        if ans[i]!=0:continue
        while used[idx_n]:
            idx_n += 1
        ans[i] = idx_n
        used[idx_n] = True
        idx_n += 1
    
    print(*ans[1:])

else:
    idx_1 = 1
    idx_2 = 2
    for i,g in enumerate(group):
        if i==0:continue
        if g==1:
            if idx_1>N:continue
            ans[i] = idx_1
            used[idx_1] = True
            idx_1 += 3
        else:
            if idx_2>N:continue
            ans[i] = idx_2
            used[idx_2] = True
            idx_2 += 3

    idx = 3
    for i in range(1,N+1):
        if ans[i]==0:
            while used[idx]:
                idx += 3
            ans[i] = idx
            used[idx] = True

    print(*ans[1:])

Buggy submission (verdict: Runtime Error):
import sys

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

#%%
# 1-indexed
adj_list = [[] for _ in range(N+1)]

for a,b in ab:
    adj_list[a].append(b)
    adj_list[b].append(a)

# DFSで各頂点を1，2に割り当てる．

group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    # 頂点vからpar以外の子へ遷移
    # grpで頂点vのグループを持つ
    
    nxt_grp = grp^3
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    
print(*ans[1:])
sys.exit()

if min(group_num) <= N//3:
    if min(group_num) == group_num[0]:
        minidx = 1
    else:
        minidx = 2
    
    idx = 3
    idx_n = 1
    for i,g in enumerate(group):
        if i==0:continue
        if g==minidx:
            ans[i] = idx            
            used[idx] = True
            idx += 3

    for i,g in enumerate(group):
        if i==0:continue
        if ans[i]!=0:continue
        while used[idx_n]:
            idx_n += 1
        ans[i] = idx_n
        used[idx_n] = True
        idx_n += 1
    
    print(*ans[1:])

else:
    idx_1 = 1
    idx_2 = 2
    for i,g in enumerate(group):
        if i==0:continue
        if g==1:
            if idx_1>N:continue
            ans[i] = idx_1
            used[idx_1] = True
            idx_1 += 3
        else:
            if idx_2>N:continue
            ans[i] = idx_2
            used[idx_2] = True
            idx_2 += 3

    idx = 3
    for i in range(1,N+1):
        if ans[i]==0:
            while used[idx]:
                idx += 3
            ans[i] = idx
            used[idx] = True

    print(*ans[1:])

Buggy submission (verdict: Runtime Error):
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]

#%%
# 1-indexed
adj_list = [[] for _ in range(N+1)]

for a,b in ab:
    adj_list[a].append(b)
    adj_list[b].append(a)

# DFSで各頂点を1，2に割り当てる．

group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    # 頂点vからpar以外の子へ遷移
    # grpで頂点vのグループを持つ
    
    nxt_grp = grp^3
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    



if min(group_num) <= N//3:
    if min(group_num) == group_num[0]:
        minidx = 1
    else:
        minidx = 2
    
    idx = 3
    idx_n = 1
    for i,g in enumerate(group):
        if i==0:continue
        if g==minidx:
            ans[i] = idx            
            used[idx] = True
            idx += 3

    for i,g in enumerate(group):
        if i==0:continue
        if ans[i]!=0:continue
        while used[idx_n]:
            idx_n += 1
        ans[i] = idx_n
        used[idx_n] = True
        idx_n += 1
    
    print(*ans[1:])

else:
    idx_1 = 1
    idx_2 = 2
    for i,g in enumerate(group):
        if i==0:continue
        if g==1:
            if idx_1>N:continue
            ans[i] = idx_1
            used[idx_1] = True
            idx_1 += 3
        else:
            if idx_2>N:continue
            ans[i] = idx_2
            used[idx_2] = True
            idx_2 += 3

    idx = 3
    for i in range(1,N+1):
        if ans[i]==0:
            while used[idx]:
                idx += 3
            ans[i] = idx
            used[idx] = True

    print(*ans[1:])

Buggy submission (verdict: Runtime Error):
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]

#%%
# 1-indexed
adj_list = [[] for _ in range(N+1)]

for a,b in ab:
    adj_list[a].append(b)
    adj_list[b].append(a)

# DFSで各頂点を1，2に割り当てる．

group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    # 頂点vからpar以外の子へ遷移
    # grpで頂点vのグループを持つ
    
    nxt_grp = grp^3
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    



if min(group_num) <= N//3:
    if min(group_num) == group_num[0]:
        minidx = 1
    else:
        minidx = 2
    
    idx = 3
    idx_n = 1
    for i,g in enumerate(group):
        if i==0:continue
        if g==minidx:
            ans[i] = idx            
            used[idx] = True
            idx += 3

    for i,g in enumerate(group):
        if i==0:continue
        if ans[i]!=0:continue
        while used[idx_n]:
            idx_n += 1
        ans[i] = idx_n
        used[idx_n] = True
        idx_n += 1
    
    print(*ans[1:])

else:
    idx_1 = 1
    idx_2 = 2
    for i,g in enumerate(group):
        if i==0:continue
        if g==1:
            if idx_1>N:continue
            ans[i] = idx_1
            used[idx_1] = True
            idx_1 += 3
        else:
            if idx_2>N:continue
            ans[i] = idx_2
            used[idx_2] = True
            idx_2 += 3

    idx = 3
    for i in range(1,N+1):
        if ans[i]==0:
            while used[idx]:
                idx += 3
            ans[i] = idx

    print(*ans[1:])

Buggy submission (verdict: Runtime Error):
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]

#%%
# 1-indexed
adj_list = [[] for _ in range(N+1)]

for a,b in ab:
    adj_list[a].append(b)
    adj_list[b].append(a)

# DFSで各頂点を1，2に割り当てる．

group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    # 頂点vからpar以外の子へ遷移
    # grpで頂点vのグループを持つ
    
    nxt_grp = grp^3
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    



if min(group_num) <= N//3:
    if min(group_num) == group_num[0]:
        minidx = 1
    else:
        minidx = 2
    
    idx = 3
    idx_n = 1
    for i,g in enumerate(group):
        if i==0:continue
        if g==minidx:
            ans[i] = idx            
            used[idx] = True
            idx += 3

    for i,g in enumerate(group):
        if i==0:continue
        if ans[i]!=0:continue
        while used[idx_n]:
            idx_n += 1
        ans[i] = idx_n
        used[idx_n] = True
        idx_n += 1
    
    print(*ans[1:])

else:
    idx_1 = 1
    idx_2 = 2
    for i,g in enumerate(group):
        if i==0:continue
        if g==1:
            while used[idx_1]:
                idx_1 += 3                
                if idx_1>N:
                    idx_1 = 3
                
            ans[i] = idx_1
            used[idx_1] = True
        else:
            while used[idx_2]:
                idx_2 += 3
                if idx_2>N:
                    idx_2 = 3
            ans[i] = idx_2
            used[idx_2] = True
            
    print(*ans[1:])

Buggy submission (verdict: Runtime Error):
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]

#%%
# 1-indexed
adj_list = [[] for _ in range(N+1)]

for a,b in ab:
    adj_list[a].append(b)
    adj_list[b].append(a)

# DFSで各頂点を1，2に割り当てる．

group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    # 頂点vからpar以外の子へ遷移
    # grpで頂点vのグループを持つ
    
    nxt_grp = grp^3
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    



if min(group_num) <= N//3:
    # if min(group_num) == group_num[0]:
    #     minidx = 1
    # else:
    #     minidx = 2
    
    # idx = 3
    # idx_n = 1
    # for i,g in group:
    #     if i==0:continue
    #     if g==minidx:
    #         ans[i] = idx            
    #         used[idx] = True
    #         idx += 3

    # for i,g in group:
    #     if i==0:continue
    #     if ans[i]!=0:continue
    #     while used[idx_n]:
    #         idx_n += 1
    #     ans[i] = idx_n
    #     used[idx_n] = True
    #     idx_n += 1
    
    print(*ans[1:])

else:
    idx_1 = 1
    idx_2 = 2
    for i,g in enumerate(group):
        if i==0:continue
        if g==1:
            while used[idx_1]:
                idx_1 += 3                
                if idx_1>N:
                    idx_1 = 3
                
            ans[i] = idx_1
            used[idx_1] = True
        else:
            while used[idx_2]:
                idx_2 += 3
                if idx_2>N:
                    idx_2 = 3
            ans[i] = idx_2
            used[idx_2] = True
            
    print(*ans[1:])

Buggy submission (verdict: Runtime Error):
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]

#%%
# 1-indexed
adj_list = [[] for _ in range(N+1)]

for a,b in ab:
    adj_list[a].append(b)
    adj_list[b].append(a)

# DFSで各頂点を1，2に割り当てる．

group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    # 頂点vからpar以外の子へ遷移
    # grpで頂点vの子のグループを持つ
    
    nxt_grp = grp^3
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    



if min(group_num) <= N//3:
    if min(group_num) == group_num[0]:
        minidx = 1
    else:
        minidx = 2
    
    idx = 3
    idx_n = 1
    for i,g in group:
        if i==0:continue
        if g==minidx:
            ans[i] = idx            
            used[idx] = True
            idx += 3

    for i,g in group:
        if i==0:continue
        if ans[i]!=0:continue
        while used[idx_n]:
            idx_n += 1
        ans[i] = idx_n
        used[idx_n] = True
        idx_n += 1
    
    print(*ans[1:])

else:
    # idx_1 = 1
    # idx_2 = 2
    # for i,g in enumerate(group):
    #     if i==0:continue
    #     if g==1:
    #         while used[idx_1]:
    #             idx_1 += 3                
    #             if idx_1>N:
    #                 idx_1 = 3
                
    #         ans[i] = idx_1
    #         used[idx_1] = True
    #     else:
    #         while used[idx_2]:
    #             idx_2 += 3
    #             if idx_2>N:
    #                 idx_2 = 3
    #         ans[i] = idx_2
    #         used[idx_2] = True
            
    print(*ans[1:])

Buggy submission (verdict: Runtime Error):
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]

#%%
# 1-indexed
adj_list = [[] for _ in range(N+1)]

for a,b in ab:
    adj_list[a].append(b)
    adj_list[b].append(a)

# DFSで各頂点を1，2に割り当てる．

group = [1]*(N+1)
group[0] = -1

def dfs(v,par,grp):
    # 頂点vからpar以外の子へ遷移
    # grpで頂点vの子のグループを持つ
    
    nxt_grp = grp^3
    for child in adj_list[v]:
        if child==par:
            continue
        group[child] = nxt_grp
        dfs(child,v,nxt_grp)
    
    return 

dfs(1,-1,1)

ans = [0]*(N+1)
used = [False]*(N+1)


group_num = [0]*2
for g in group[1:]:
    group_num[g-1] += 1
    



if min(group_num) <= N//3:
    if min(group_num) == group_num[0]:
        minidx = 1
    else:
        minidx = 2
    
    idx = 3
    idx_n = 1
    for i,g in group:
        if i==0:continue
        if g==minidx:
            ans[i] = idx            
            used[idx] = True
            idx += 3

    for i,g in group:
        if i==0:continue
        if ans[i]!=0:continue
        while used[idx_n]:
            idx_n += 1
        ans[i] = idx_n
        used[idx_n] = True
        idx_n += 1
    
    print(*ans[1:])

else:
    idx_1 = 1
    idx_2 = 2
    for i,g in enumerate(group):
        if i==0:continue
        if g==1:
            while used[idx_1]:
                idx_1 += 3                
                if idx_1>N:
                    idx_1 = 3
                
            ans[i] = idx_1
            used[idx_1] = True
        else:
            while used[idx_2]:
                idx_2 += 3
                if idx_2>N:
                    idx_2 = 3
            ans[i] = idx_2
            used[idx_2] = True
            
    print(*ans[1:])