Problem:


Score : 400 points

Problem Statement

Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.

Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.

Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

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

Print N lines.

The first line should contain K, the number of colors used.

The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.

If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

8
1 2
2 3
2 4
2 5
4 7
5 6
6 8

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
 
N = int(input())
 
edge =  [[] for i in range(N-1)]
to = [[] for i in range(N)]
color = {}
edge_list = []
 
for i in range(N-1):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
    edge[i] = [a-1, b-1]
    edge_list.append(a-1)
    edge_list.append(b-1)
 
K = Counter(edge_list).most_common()[0][1]
 
q = deque([])
q.append([0,-1])
 
is_visited = [False] * N
 
while(len(q) != 0):
    cur_node, pre_col = q.popleft()
    col_list = [False] * K
    if not pre_col == -1:
        col_list[pre_col] = True
 
    is_visited[cur_node] = True
 
    for next_node in to[cur_node]:
        if not is_visited[next_node]:
            for i in range(K):
                if not col_list[i]:
                    col_list[i] = True
                    color[(cur_node,next_node)] = i
                    q.append([next_node, i])
                    break
 
print(K)
 
for i in range(N-1):
    print(color[tuple(edge[i])] + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter

N = int(input())

edge =  [[] for i in range(N-1)]
to = [[] for i in range(N)]
color = {}
edge_list = []

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

K = Counter(edge_list).most_common()[0][1]

q = deque([])
q.append([0,-1])

is_visited = [False] * N

while(len(q) != 0):
    cur_node, pre_col = q.popleft()
    col_list = [False] * K
    if not pre_col == -1:
        col_list[pre_col] = True

    is_visited[cur_node] = True

    for next_node in to[cur_node]:
        if not is_visited[next_node]:
            for i in range(K):
                if not col_list[i]:
                    col_list[i] = True
                    color[(cur_node,next_node)] = i
                    q.append([next_node, i])
                    break

print(K)

for i in range(N-1):
    print(color[tuple(edge[i])] + 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
G = dict([(i,[]) for i in range(1,N+1)])
ansl = []
for i in range(N-1):
  a,b = map(int,input().split())
  ansl.append([a,b])
  G[a].append(b)
  G[b].append(a)

K = -1
hen = [[0]*(N+1) for i in range(N+1)]
seen = [False for i in range(N+1)]
seen[1] = True 
#[頂点、来たときの辺の色]
l = deque([[1,0]])
while len(l)!=0:
  [v,oyac] = l.popleft()
  nuri = 1
  for i in G[v]:
    if seen[i] == False:
      seen[i] = True
      while True:
        if nuri != oyac:
          hen[min(v,i)][max(v,i)] = nuri
          l.append([i,nuri])
          K = max(K,nuri)
          nuri += 1
          break
        else:
          nuri += 1  
###
print(K)
for i in range(N-1):
  a,b = ansl[i]
  print(hen[a][b])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    import sys
    readline = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N = int(readline())
    R = [[int(i) for i in r.split()] for r in read().rstrip().split(b'\n')]
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for a, b in R:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def bfs(s, max_g):
        dist = [-1 for _ in range(N)]
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        que = deque()
        que.append(s)
        dist[s] = 0
        par = [-1]*N
        while que:
            u = que.popleft()
            if par[u] != -1:
                if par[u] < u:
                    color[u].discard(edge[(par[u], u)])
                else:
                    color[u].discard(edge[(par[u], u)])
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)
                c = color[u].pop()
                par[v] = u
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c
            if all(i != -1 for i in edge.values()):
                return
    bfs(0, max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def bfs(s, max_g):
        dist = [-1 for _ in range(N)]
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        que = deque()
        que.append(s)
        dist[s] = 0
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)
                c = color[u].pop()
                color[v].discard(c)
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c
            if all(i != -1 for i in edge.values()):
                return
    bfs(0, max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def dfs(max_g):
        todo = [0]
        seen = [False]*N
        seen[0] = True
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        par = [-1]*N
        while todo:
            u = todo.pop()
            if par[u] != -1:
                if par[u] < u:
                    color[u].discard(edge[(par[u], u)])
                else:
                    color[u].discard(edge[(u, par[u])])
            for v in G[u]:
                if seen[v]:
                    continue
                seen[v] = True
                todo.append(v)
                c = color[u].pop()
                par[v] = u
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c

    dfs(max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def dfs(max_g):
        todo = [0]
        seen = [False]*N
        seen[0] = True
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        while todo:
            u = todo.pop()
            for v in G[u]:
                if seen[v]:
                    continue
                seen[v] = True
                todo.append(v)
                c = color[u].pop()
                color[v].discard(c)
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c

    dfs(max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def bfs(s, max_g):
        dist = [-1 for _ in range(N)]
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        que = deque()
        que.append(s)
        dist[s] = 0
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)
                c = color[u].pop()
                color[v].discard(c)
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c

    bfs(0, max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)

color = [0] * N

def dfs(v, c):
    color[v] = c
    now = 0
    for nv in edge[v]:
        if v == nv: continue
        now += 1
        if now == c:
            now += 1
        dfs(nv, now)

dfs(0, 0)
color[0] = max(color)
print(*color, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import deque

n = int(input())

connect_list = [[] for _ in range(n)]

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

for i in range(n-1):
    a, b = ab[i]
    connect_list[a-1].append(b-1)
    connect_list[b-1].append(a-1)


color_list = [[-1]*(n) for _ in range(n)]
check_list = [0]*n

color_max = 1

d = deque([0])
while(len(d) > 0):
    # print(d)
    index = d.pop()
    check_list[index] = 1

    index_list = connect_list[index]
    color_max = max(color_max, len(index_list))

    color_list_rest = set(range(1, len(index_list)+1))-set(color_list[index])

    for i in index_list:
        if check_list[i] == 1:
            continue
        else:
            check_list[i] == 0
            check_list[i] = 1
            d.append(i)

        if color_list[index][i] == -1:
            num = color_list_rest.pop()
            color_list[index][i] = num
            color_list[i][index] = num


print(color_max)
for a, b in ab:
    print(color_list[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import deque

n = int(input())

connect_list = [[] for _ in range(n)]

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

for i in range(n-1):
    a, b = ab[i]
    connect_list[a-1].append(b-1)
    connect_list[b-1].append(a-1)


color_list = [[-1]*(n) for _ in range(n)]
check_list = [0]*n

color_max = 1

d = deque([0])
while(len(d) > 0):
    # print(d)
    index = d.pop()
    check_list[index] = 1

    index_list = connect_list[index]
    color_max = max(color_max, len(index_list))

    color_list_rest = set(range(1, len(index_list)+1))-set(color_list[index])

    for i in index_list:
        if color_list[index][i] == -1:
            num = color_list_rest.pop()
            color_list[index][i] = num
            color_list[i][index] = num

        if check_list[i] == 0:
            check_list[i] = 1
            d.append(i)


print(color_max)
for a, b in ab:
    print(color_list[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
n = int(input())
 
connect_list = [[] for _ in range(n)]
 
ab = [list(map(int, input().split())) for i in range(n-1)]
 
for i in range(n-1):
    a, b = ab[i]
    connect_list[a-1].append(b-1)
    connect_list[b-1].append(a-1)
 
 
color_list = [[-1]*(n) for _ in range(n)]
check_list = [0]*n
 
color_max = 1
 
d = deque([0])
while(len(d) > 0):
    # print(d)
    index = d.pop()
    check_list[index] = 1
 
    index_list = connect_list[index]
    color_max = max(color_max, len(index_list))
 
    color_list_rest = set(range(1, len(index_list)+1))-set(color_list[index])
    # print("clr:", color_list_rest)
 
    for i in index_list:
        if color_list[index][i] == -1:
            num = color_list_rest.pop()
            color_list[index][i] = num
            color_list[i][index] = num
 
    for i in index_list:
        if check_list[i] == 0:
            check_list[i] = 1
            d.append(i)
 
print(color_max)
for a, b in ab:
    print(color_list[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import deque

n = int(input())

connect_list = [[] for _ in range(n)]

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

for i in range(n-1):
    a, b = ab[i]
    connect_list[a-1].append(b-1)
    connect_list[b-1].append(a-1)


color_list = [[-1]*(n) for _ in range(n)]
check_list = [0]*n

color_max = 1

d = deque([0])
while(len(d) > 0):
    # print(d)
    index = d.pop()
    check_list[index] = 1

    index_list = connect_list[index]
    color_max = max(color_max, len(index_list))

    color_list_rest = set(range(1, len(index_list)+1))-set(color_list[index])
    # print("clr:", color_list_rest)

    for i in index_list:
        if color_list[index][i] == -1:
            num = color_list_rest.pop()
            color_list[index][i] = num
            color_list[i][index] = num

    for i in index_list:
        if check_list[i] == 0:
            check_list[i] = 1
            d.append(i)

print(color_max)
for a, b in ab:
    print(color_list[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
ab = []
deg = [0 for i in range(N)]
child = [[] for _ in range(N)]
edge = {}
color = [0 for _ in range(N-1)]
for i in range(N-1):
  tmp = list(map(int, input().split()))
  deg[tmp[0]-1] += 1
  deg[tmp[1]-1] += 1
 
  child[tmp[0]-1].append(tmp[1]-1)
  child[tmp[1]-1].append(tmp[0]-1)
  tmp = [tmp[0]-1, tmp[1]-1]
  edge[tuple(tmp)] = i
  
q = queue.Queue()
q.put([None, 0, None])
used = [0]
# parent, self, color
while not q.empty():
  current = q.get()
  if current[0] is not None:
    cnt = 1
    for c in child[current[1]]:
      if c in used:
        continue
      used.append(c)
      if cnt == current[2]:
        cnt += 1
      q.put([current[1], c, cnt])
      ind = [current[1], c] if current[1] < c else [c, current[1]]
      
      color[edge[tuple(ind)]] = cnt
      
      cnt += 1
  else:
    for i, c in enumerate(child[current[1]]):
      used.append(c)
      q.put([current[1], c, i+1])
      ind = [current[1], c] if current[1] < c else [c, current[1]]
      #print(edge[tuple(ind)], i+1)
      color[edge[tuple(ind)]] = i+1
print(max(deg))
for c in color:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peer_nodes = [[] for _ in range(N)]
edge_colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peer_nodes[a].append(b)
    if not a in peer_nodes[b]:
        peer_nodes[b].append(a)
    edge_colors[a][b] = 0

#print(peer_nodes,edge_colors)

def draw_color_return_max_colors(node):
    max_colors = 0
    peers = peer_nodes[node]
    if len(peers) == 0:
        return 0
    used_colors = []
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        c = edge_colors[i][j]
        if c != 0:
            used_colors.append(c)
    #print('----', node, peers,used_colors)
    if len(used_colors) == len(peers):
        return 0
    color = 1
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        if edge_colors[i][j] > 0:
            continue
        else:
            while(color in used_colors):
                used_colors.remove(color)
                color += 1
            used_colors.append(color)
            edge_colors[i][j] = color
    max_colors = max([color] + used_colors)
    for p in peers:
        max_colors = max(max_colors, draw_color_return_max_colors(p))

    return max_colors


print(draw_color_return_max_colors(pairs[0][0]))

for a,b in pairs:
    print(edge_colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peer_nodes = [[] for _ in range(N)]
edge_colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peer_nodes[a].append(b)
    if not a in peer_nodes[b]:
        peer_nodes[b].append(a)
    edge_colors[a][b] = 0

#print(peer_nodes,edge_colors)

def draw_color_return_max_colors(node):
    max_colors = 0
    peers = peer_nodes[node]
    if len(peers) == 0:
        return 0
    used_colors = []
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        c = edge_colors[i][j]
        if c != 0:
            used_colors.append(c)
    #print('----', node, peers,used_colors)
    if len(used_colors) == len(peers):
        return 0
    color = 1
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        if edge_colors[i][j] > 0:
            continue
        else:
            while(color in used_colors):
                used_colors.remove(color)
                color += 1
            if edge_colors[i][j] == 0:
                used_colors.append(color)
                edge_colors[i][j] = color
    max_colors = max([0] + used_colors)
    for p in peers:
        max_colors = max(max_colors, draw_color_return_max_colors(p))

    return max_colors


print(draw_color_return_max_colors(pairs[0][0]))

for a,b in pairs:
    print(edge_colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peer_nodes = [[] for _ in range(N)]
edge_colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peer_nodes[a].append(b)
    if not a in peer_nodes[b]:
        peer_nodes[b].append(a)
    edge_colors[a][b] = 0

#print(peer_nodes,edge_colors)

def draw_color_return_max_colors(node):
    max_colors = 0
    peers = peer_nodes[node]
    if len(peers) == 0:
        return 0
    used_colors = []
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        c = edge_colors[i][j]
        if c != 0:
            used_colors.append(c)
    #print('----', node, peers,used_colors)
    if len(used_colors) == len(peers):
        return 0
    color = 1
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        if edge_colors[i][j] > 0:
            continue
        else:
            while(color in used_colors):
                color += 1
            if edge_colors[i][j] == 0:
                used_colors.append(color)
                edge_colors[i][j] = color
    max_colors = max(used_colors)
    for p in peers:
        max_colors = max(max_colors, draw_color_return_max_colors(p))

    return max_colors


print(draw_color_return_max_colors(pairs[0][0]))

for a,b in pairs:
    print(edge_colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peer_nodes = [[] for _ in range(N)]
edge_colors = [[0]*(N) for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peer_nodes[a].append(b)
    if not a in peer_nodes[b]:
        peer_nodes[b].append(a)
    edge_colors[a][b] = 0

#print(peer_nodes,edge_colors)

def draw_color_return_max_colors(node):
    max_colors = 0
    peers = peer_nodes[node]
    if len(peers) == 0:
        return 0
    used_colors = []
    for p in peers:
        c = edge_colors[node][p]
        if c != 0:
            used_colors.append(c)
    #print('----', node, peers,used_colors)
    if len(used_colors) == len(peers):
        return 0
    color = 1
    for p in peers:
        if edge_colors[node][p] > 0:
            continue
        else:
            while(color in used_colors):
                color += 1
            if edge_colors[node][p] == 0:
                used_colors.append(color)
                edge_colors[node][p] = color
                edge_colors[p][node] = color
    max_colors = max(used_colors)
    for p in peers:
        max_colors = max(max_colors, draw_color_return_max_colors(p))

    return max_colors


print(draw_color_return_max_colors(pairs[0][0]))

for a,b in pairs:
    print(edge_colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peer_nodes = [[] for _ in range(N)]
edge_colors = [[0]*(N) for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peer_nodes[a].append(b)
    if not a in peer_nodes[b]:
        peer_nodes[b].append(a)
    edge_colors[a][b] = 0

#print(peer_nodes,edge_colors)

def draw_color_return_max_colors(node):
    max_colors = 0
    peers = peer_nodes[node]
    if len(peers) == 0:
        return 0
    used_colors = []
    for p in peers:
        c = edge_colors[node][p]
        if c != 0:
            used_colors.append(c)
    #print('----', node, peers,used_colors)
    if len(used_colors) == len(peers):
        return 0
    color = 1
    for p in peers:
        #print(node, p, edge_colors[node][p])
        while(color in used_colors):
            color += 1
        if edge_colors[node][p] == 0:
            used_colors.append(color)
            edge_colors[node][p] = color
            edge_colors[p][node] = color
    max_colors = max(used_colors)
    for p in peers:
        max_colors = max(max_colors, draw_color_return_max_colors(p))

    return max_colors


print(draw_color_return_max_colors(pairs[0][0]))

for a,b in pairs:
    print(edge_colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
G = dict([(i,[]) for i in range(1,N+1)])
ansl = []
for i in range(N-1):
  a,b = map(int,input().split())
  ansl.append([a,b])
  G[a].append(b)
  G[b].append(a)

K = -1
hen = [[0 for i in range(N+1)] for i in range(N+1)]
seen = [False for i in range(N+1)]
seen[1] = True 
#[頂点、来たときの辺の色]
l = deque([[1,0]])
while len(l)!=0:
  [v,oyac] = l.popleft()
  nuri = 1
  for i in G[v]:
    if seen[i] == False:
      seen[i] = True
      while True:
        if nuri != oyac:
          hen[v][i] = nuri
          hen[i][v] = nuri
          l.append([i,nuri])
          K = max(K,nuri)
          nuri += 1
          break
        else:
          nuri += 1  
###
print(K)
for i in range(N-1):
  a,b = ansl[i]
  print(hen[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
G = dict([(i,[]) for i in range(1,N+1)])
ansl = []
for i in range(N-1):
  a,b = map(int,input().split())
  ansl.append([a,b])
  G[a].append(b)
  G[b].append(a)

K = -1
hen = [[0 for i in range(N+1)] for i in range(N+1)]
seen = [False for i in range(N+1)]
seen[1] = True 
#[頂点、来たときの辺の色]
l = deque([[1,0]])
while len(l)!=0:
  [v,oyac] = l.popleft()
  nuri = 1
  for i in G[v]:
    if seen[i] == False:
      seen[i] = True
      while True:
        if nuri != oyac:
          hen[v][i] = nuri
          hen[i][v] = nuri
          l.append([i,nuri])
          K = max(K,nuri)
          nuri += 1
          break
        else:
          nuri += 1  
###
print(K)
for i in range(N-1):
  a,b = ansl[i]
  print(hen[a][b])

Submission status: Time Limit Exceeded

Solution code:

#初期入力
import sys
input = sys.stdin.readline
import heapq
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            =[i for i in range(N-1)]
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i] =a,b            #色を出力するため

#色の数(各頂点の最大値)
color_max =0
root =0
for i,v in connection.items():
    if color_max < len(v) :
        color_max =len(v)
        root =i         #枝が一番多い所を根 ⇒スタート

#各頂点に色を準備⇒辺の色決定
aa=[]
color =0                                 #辺に塗る色の候補
node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理
edge ={}
for a,b in A:
    edge[(a,b)] =-1                   #辺の色 -1で初期化
now_set =set() #=start
now_set.add(root) #=start
next =set()
next_next =set()
passed ={i:False for i in range(1,N+1)}
count =0
while -1 in edge.values(): #全て辺の色が-1以外＝塗り終わった
    for now in now_set: #幅優先探索
        next =connection[now]
        for nex_2 in next:
            count =0
            if node[now] !=[]:
                color =node[now][-1] +1
            while count < color_max:
                q,color =divmod(color,color_max)
                if color not in node[now] and color not in node[nex_2]:
                    n1,n2=0,0
                    if now > nex_2:
                        n1,n2 =nex_2,now
                    else:
                        n1,n2 =now,nex_2
                    edge[(n1,n2)] =color +1  #辺の色決定
                    node[now]   .append(color)
                    node[nex_2] .append(color)
                    passed[now] =True
                    #colored     =connection[nex_2] - passed
                    if passed[nex_2] ==False:
                        next_next.add(nex_2)  #つながっている頂点（次に探索する）
                    passed[nex_2] =nex_2
                    color   +=1
                    count   +=1
                    break
                else:
                    color +=1
                    count +=1
    now_set     .clear()
    now_set     |=next_next
    next_next   .clear()
    
#出力
print(color_max)
for i in A:
    print(edge[i])

Submission status: Time Limit Exceeded

Solution code:
#nord_aで使っている色の＋１
#初期入力
import sys
input = sys.stdin.readline
import heapq
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            =[i for i in range(N-1)]
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i] =a,b            #色を出力するため

#色の数(各頂点の最大値)
color_max =0
root =0
for i,v in connection.items():
    if color_max < len(v) :
        color_max =len(v)
        root =i         #枝が一番多い所を根 ⇒スタート

#各頂点に色を準備⇒辺の色決定
aa=[]
color =0                                 #辺に塗る色の候補
color_node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理
color_edge ={}
for a,b in A:
    color_edge[(a,b)] =-1                   #辺の色 -1で初期化
now_set =set() #=start
now_set.add(root) #=start
next =set()
next_next =set()
passed =set()
count =0
while -1 in color_edge.values(): #全て辺の色が-1以外＝塗り終わった
    for now in now_set: #幅優先探索
        next =connection[now]
        for nex_2 in next:
            count =0
            while count < color_max:
                q,color =divmod(color,color_max)
                if color not in color_node[now] and color not in color_node[nex_2]:
                    n1,n2=0,0
                    if now > nex_2:
                        n1,n2 =nex_2,now
                    else:
                        n1,n2 =now,nex_2
                    color_edge[(n1,n2)] =color +1  #辺の色決定
                    color_node[now]     .append(color)
                    color_node[nex_2]   .append(color)
                    passed              .add(now)
                    colored =connection[nex_2] - passed
                    if colored !=set():
                        next_next       .add(nex_2)  #つながっている頂点（次に探索する）
                    passed      .add(nex_2)
                    color       +=1
                    count       +=1
                    break
                else:
                    color +=1
                    count +=1
    now_set     .clear()
    now_set     |=next_next
    next_next   .clear()
    
#出力
print(color_max)
for i in A:
    print(color_edge[i])