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 queue import deque

n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]
li = [[0 for i in range(n)]for j in range(n)]

for i,j in l:
    i,j = i-1,j-1
    li[i][j] = 1
    li[j][i] = 1

ans = [[0 for i in range(n)]for j in range(n)]
before_color = {}
before_color[0] = 0
visited_node = [False]*n
visited_node[0] = True

max_color = 1

# 幅優先探索（BFS）
def breadth_first_search(start, W):
    global max_color
    # リストをキューにする
    work_queue = deque([])
    visited = set()
    # 初期化
    work_queue.append(start)
    visited.add(start)

    while work_queue:
        # 今いる頂点
        here = work_queue.popleft()
        # 今いる頂点に隣接する頂点すべてを処理する
        for i, node in enumerate(W[here]):
            # 隣接しなければ何もしない
            if node == 0: continue
            if i not in visited:
                work_queue.append(i)
                visited.add(i)
        color = 1
        for j in work_queue:
            if visited_node[j]:
                continue
            else:
                visited_node[j] = True
            if color == before_color[here]:
                color += 1
            before_color[j] = color
            ans[here][j] = color
            ans[j][here] = color
            max_color = max(max_color,color)
            color += 1
    return visited

breadth_first_search(0,li)
print(max_color)
for i,j in l:
    i,j = i-1,j-1
    print(ans[i][j])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
edge=list(set(map(int,input().split())) for _ in range(n-1))
color=[0]*(n-1)
d=deque()


s=1
d.append(s)
while d:
  c=1
  s=d.popleft()
  check=set()
  seen=set()
  for i in range(n-1):
    if s in edge[i] :
      for k in edge[i]:
        if k!=s:
          e=k
      if color[i]==0:
        d.append(e)
        check.add(i)
      else:
        seen.add(color[i])
  for j in check:
    if c not in seen:
      color[j]=c
      c+=1
    else:
      while c in seen:
        c+=1
      color[j]=c
      c+=1
print(int(max(color)))
print(" ".join(list(map(lambda x: str(int(x)), color))))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
edge=list(list(map(int,input().split())) for _ in range(n-1))
color=[0]*(n-1)
d=deque()


s=1
d.append(s)
while d:
  c=1
  s=d.popleft()
  check=[]
  seen=[]
  for i in range(n-1):
    if s in edge[i]:
      for k in edge[i]:
        if k!=s:
          e=k
      if color[i]==0:
        d.append(k)
        check.append(i)
      else:
        seen.append(color[i])
  for j in check:
    if c not in seen:
      color[j]=c
      c+=1
    else:
      while c in seen:
        c+=1
      color[j]=c
      c+=1
print(int(max(color)))
print(" ".join(list(map(lambda x: str(int(x)), color))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
n=int(input())
edge=np.array(list(list(map(int,input().split())) for _ in range(n-1)))
color=np.zeros(n-1)
d=deque()


s=1
d.append(s)
while d:
  c=1
  s=d.popleft()
  check=[]
  seen=[]
  for i in range(n-1):
    if s in edge[i]:
      e=edge[i][edge[i]!=s]
      if color[i]==0:
        d.append(e[0])
        check.append(i)
      else:
        seen.append(color[i])
  for j in check:
    if c not in seen:
      color[j]=c
      c+=1
    else:
      while c in seen:
        c+=1
      color[j]=c
      c+=1
print(int(max(color)))
print(" ".join(list(map(lambda x: str(int(x)), color))))

Submission status: Time Limit Exceeded

Solution code:
# D - Coloring Edges on Tree

n = int(input())
A = []
B = []

# 2次元配列で辺（頂点,遷移先の頂点）を管理する
D = [[] for _ in range(n)]

# 2次元配列で塗る色（頂点,遷移先の頂点）を管理する
C = [[0]*n for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a].append(b)
    D[b].append(a)
    A.append(a)
    B.append(b)

print(max([len(d) for d in D]))

def dfs(node, par, col):
    cid = 1
    for chi in D[node]:
        if chi==par:
            continue
        else:
            if cid==col:
                cid += 1
            C[node][chi] = cid
            dfs(chi, node, cid)
            cid += 1

dfs(0,0,0)

for a, b in zip(A, B):
    print(C[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
path = [[] for _ in range(n)]
ab = []
color = [0]*(n-1)
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  ab.append([a,b])
  path[a].append(b)
  path[b].append(a)
  
que = deque()
que.append((0,0))
reached = [False]*n
reached[0] = True
while que:
  p,pc = que.popleft()
  c = 0
  for i in path[p]:
    if reached[i] == False:
      while True:
        c += 1
        if c == pc:continue
        color[ab.index(sorted([p,i]))] = c
        break
      reached[i] = True
      que.append((i,c))
print(max(color))
for i in color:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
#%%
e = [[] for i in range(N)]
for a, b in ab:
    e[a-1].append(b-1)
    e[b-1].append(a-1)
#%%
ans = [e.copy() for i in range(N)]
max_e = 0
for e_ in e:
    max_e = max(max_e, len(e_))
print(max_e)

def dfs(s=0,p=-1,pe=-1):
    ts = e[s]
    e_num=1
    for t in ts:
        if t==p:
            continue
        if e_num==pe:
            e_num+=1
        ans[s][t] = e_num
        ans[t][s] = e_num
        dfs(s=t, p=s, pe=e_num)
        e_num +=1

dfs()
for a, b in ab:
    print(ans[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
N = int(input())
AB = [list(map(int, input().split())) for i in range(N-1)]

#　頂点をキー、つながり先をVALUEの辞書
tunagari ={}
for ab in AB:
    tunagari.setdefault(ab[0], []).append(ab[1])
    tunagari.setdefault(ab[1], []).append(ab[0])

# 　最小の色数（根の辺の数）
color_count = [len(i) for i in tunagari.values() ]
color_max =max(color_count)     
print(color_max) #答え

#
color_set =set("")
#頂点とつながり先をキー、色をValueの辞書
color_ten_ten = {}
from collections import defaultdict
col_sumi= {i:set() for i in tunagari.keys()} # 使った色を覚えておく辞書

for k,v in tunagari.items():
    color_set =set([i for i in range(1,color_max+1) ])
    for ii in v:
        if k<ii:
            if col_sumi[k] & color_set:
                color_set = color_set - col_sumi[k] # 今の頂点に対して覚えていた色を消す
            if col_sumi[ii] & color_set:    
                color_set =color_set - col_sumi[ii] # 先の頂点に対して覚えていた色を消す
        
            xx = color_set.pop() # ポップだから速度のため末尾から消す  
            color_ten_ten.setdefault((k,ii) ,xx)  
            col_sumi[k].add(xx) # 元の頂点に対して使った色を覚えておく
            col_sumi[ii].add(xx) # 後の頂点に対して使った色を覚えておく

#AB＝color_ten_tenのキーが同じなら、値の色をprint
for i in AB:
    ab = tuple(i)
    if ab in color_ten_ten.keys() :
        print(color_ten_ten[ab])

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
N = int(input())
AB = [list(map(int, input().split())) for i in range(N-1)]

#　頂点をキー、つながり先をVALUEの辞書
tunagari ={}
for ab in AB:
    tunagari.setdefault(ab[0], []).append(ab[1])
    tunagari.setdefault(ab[1], []).append(ab[0])

# 　最小の色数（根の辺の数）
color_count = [len(i) for i in tunagari.values() ]
color_max =max(color_count)     
print(color_max) #答え

#
color_set =set("")
#頂点とつながり先をキー、色をValueの辞書
color_ten_ten = {}
from collections import defaultdict
col_sumi= {i:set() for i in tunagari.keys()} # 使った色を覚えておく辞書

for k,v in tunagari.items():
    color_set =set([i for i in range(1,color_max+1) ])
    for ii in v:
        if (col_sumi[k] & color_set) and (k<ii) :
            color_set = color_set - col_sumi[k] # 今の頂点に対して覚えていた色を消す
        if (col_sumi[ii] & color_set) and (k<ii):    
            color_set =color_set - col_sumi[ii] # 先の頂点に対して覚えていた色を消す
        if k<ii:
            xx = color_set.pop() # ポップだから速度のため末尾から消す  
            color_ten_ten.setdefault((k,ii) ,xx)  
            col_sumi[k].add(xx) # 元の頂点に対して使った色を覚えておく
            col_sumi[ii].add(xx) # 後の頂点に対して使った色を覚えておく

#AB＝color_ten_tenのキーが同じなら、値の色をprint
for i in AB:
    ab = tuple(i)
    if ab in color_ten_ten.keys() :
        print(color_ten_ten[ab])

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
N = int(input())
AB = [list(map(int, input().split())) for i in range(N-1)]

#　頂点をキー、つながり先をVALUEの辞書
tunagari = {}
for ab in AB:
    tunagari.setdefault(ab[0], []).append(ab[1])
    tunagari.setdefault(ab[1], []).append(ab[0])
color_count = [len(i) for i in tunagari.values() ]
color_max =max(color_count)     
color_list =[i for i in range(1,color_max+1)]
#頂点とつながり先をキー、色をValueの辞書
color_hen = {}

"""
for i in AB:
    color_hen[AB[0]] =1
"""
from collections import defaultdict

color_moto ={i:color_list for i in tunagari.keys()} 
color_ten_ten = {}
col =[] #　色の一時的な変数
for k,v in tunagari.items():
    color =[]
    color.extend(color_moto[k])
    for ii in v:
        #print(color,end=" ")
        if (k,ii) not in color_ten_ten.keys():
            xx = color.pop() # ポップだから速度のため末尾から消す  
            #print(xx,end="  ")
            color_ten_ten.setdefault((k,ii) ,xx)  
            color_ten_ten.setdefault((ii,k) ,xx)
        # 辞書から取り出す→消す→辞書に戻す(後の検索先)        
            col.extend(color_moto[ii]) 
            col.remove(xx)
            #print(col)
            color_moto[ii] = col
            col=[]
     
print(color_max) #答え　最小の色数（根の辺の数）
#AB＝color_ten_tenのキーが同じなら、値の色をprint
for i in AB:
    ab = tuple(i)
    if ab in color_ten_ten.keys():
        print(color_ten_ten[ab])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
edges = np.array([input().split() for _ in range(N - 1)], dtype=int)
edges -= 1#ゼロ始まりに

# エッジ辞書を作成
from collections import defaultdict
edict = defaultdict(list)
for i, (a, b) in enumerate(edges):
    edict[a] += [i]
    edict[b] += [i]

def get_maxdeg():
    """次数最大の頂点を選ぶ"""
    mvtx, mlen = 0, 0
    for vtx, lis in edict.items():
        if len(lis) > mlen:
            mlen = len(lis)
            mvtx = vtx
    return mvtx, mlen

svtx, slen = get_maxdeg()#探索開始頂点、最大使用色数
etable = np.zeros((N, slen), dtype=bool)#使用済み色を記録するテーブル
colors = np.zeros(N-1, dtype=int) - 1#色塗り結果を保存するところ

import queue
q = queue.Queue()
visit = np.zeros(N, dtype=bool)

def min_used(used_array):
    """未使用の色でID最小のものを選ぶ"""
    for i, v in enumerate(used_array):
        if v == False:
            return i
    return None

def paint(eidx):
    """エッジ番号eidx番のエッジに色を塗る"""
    if colors[eidx] >= 0:
        return#すでに塗られているなら終了
    # 色を選ぶ
    va, vb = edges[eidx]
    used = etable[va] + etable[vb]
    cidx = min_used(used)
    if cidx == None:
        return#塗れる色がない場合
    # 色を塗る
    colors[eidx] = cidx
    etable[va, cidx] = True
    etable[vb, cidx] = True

def push_neighbor(svtx):
    """隣接マスをキューにpush"""
    eids = edict[svtx]
    for eidx in eids:
        va, vb = edges[eidx]
        paint(eidx)
        v = va if va != svtx else vb#２点のうち、開始点svtxと違う方が探索対象
        if not visit[v]:
            q.put(v)
            visit[v] = True
            
visit[svtx] = True#初期位置は探索済み
# 計算
q.put(svtx)

while not q.empty():
    v = q.get()
    push_neighbor(v)
    
print(slen)
for c in colors:
    print(c + 1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
adj = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  adj[a-1].append((b-1, i))
  adj[b-1].append((a-1, i))
max_degree = 0
for i in range(n):
  degree = len(adj[i])
  if degree > max_degree:
    root = i
    max_degree = degree
color = [[] for _ in range(n)]
edge = [0] * (n - 1)
queue = [root]
parent = [root] * n
while queue:
  vertex = queue.pop()
  c = 1
  for v, i in adj[vertex]:
    if parent[vertex] == v:
      continue
    while c in color[v] or c in color[vertex]:
      c += 1
    color[v].append(c)
    color[vertex].append(c)
    edge[i] = c
    queue.append(v)
    parent[v] = vertex
    c += 1
print(max_degree)
for c in edge:
  print(c)

Submission status: Time Limit Exceeded

Solution code:
import queue

n = int(input())
edge = [list(map(int, input().split())) for i in range(n-1)]
vertex = [[] for i in range(n)]
visited = [0 for i in range(n)]

for i in range(n-1):
    vertex[edge[i][0]-1].append(i)
    vertex[edge[i][1]-1].append(i)

reqcolor = max([len(vertex[i]) for i in range(n)])
print(reqcolor)

vq = queue.Queue()
eq = queue.Queue()

vq.put(1)

while not vq.empty():
    v = vq.get()
    visited[v-1] = 1
    for e in vertex[v-1]:
        for w in edge[e]:
            if visited[w-1] == 0:
                vq.put(w)
                eq.put(e)

usedcolor = [[0 for i in range(reqcolor)] for i in range(n)]
edgecolor = [0 for i in range(n-1)]

while not eq.empty():
    e = eq.get()
    for i in range(reqcolor):
        if usedcolor[edge[e][0]-1][i] == 0 and usedcolor[edge[e][1]-1][i] == 0:
            edgecolor[e] = i
            usedcolor[edge[e][0]-1][i] = 1
            usedcolor[edge[e][1]-1][i] = 1
            break

for e in range(n-1):
    print(edgecolor[e]+1)

Submission status: Time Limit Exceeded

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

vc=[[] for _ in range(n)]
ec=[-1]*(n-1)
for p,ci in enumerate(g):
    for c, i in ci:
        color = 1
        while True:
            if color not in vc[p]:
                vc[p].append(color)
                vc[c].append(color)
                ec[i] = color
                break
            else:
                color += 1
        

print(max(ec))
for i in range(n-1):
    print(ec[i])

Submission status: Time Limit Exceeded

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

vc=[[] for _ in range(n)]
ec=[-1]*(n-1)
for p,ci in enumerate(g):
    color = 1
    for c, i in ci:
        while True:
            if color not in vc[p]:
                vc[p].append(color)
                vc[c].append(color)
                ec[i] = color
                break
            else:
                color += 1
        

print(max(ec))
for i in range(n-1):
    print(ec[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
    a, b = map(int, input().split())
    edges[a].append([edge_idx, b])
    edges[b].append([edge_idx, a])

used_edges = []
colors = [1 for _ in range(1, N + 1)]
used_colors = [[] for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1

while stack:
    edge_info, parent_node_idx = stack.popleft()
    cur_color = 1
    for edge_idx, node_idx in edge_info:
        if edge_idx in used_edges: continue
        while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
            cur_color += 1
        used_colors[node_idx].append(cur_color)
        colors[edge_idx] = cur_color
        stack.append([edges[node_idx], node_idx])
        used_edges.append(edge_idx)
        max_col = max(max_col, cur_color)
        cur_color += 1
        
print(max_col)
for c in colors[1:]:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
    a, b = map(int, input().split())
    edges[a].append([edge_idx, b])
    edges[b].append([edge_idx, a])

used_edges = []
colors = [1 for _ in range(1, N + 1)]
used_colors = [[] for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1

while stack:
    edge_info, parent_node_idx = stack.pop()
    cur_color = 1
    for edge_idx, node_idx in edge_info:
        if edge_idx in used_edges: continue
        while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
            cur_color += 1
        used_colors[node_idx].append(cur_color)
        colors[edge_idx] = cur_color
        stack.append([edges[node_idx], node_idx])
        used_edges.append(edge_idx)
        max_col = max(max_col, cur_color)
        cur_color += 1
        
print(max_col)
for c in colors[1:]:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
 
import sys
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()


def main():
    input = sys.stdin.readline      # 改行文字が残ることに注意
    def ii():  return int(input())
            

    def bfs_tree_traverse(root):
        ' root から BFS し条件を満たすように彩色していく。各辺の色情報を color に記載。最後に使用した色の数を返す。'
        paths = deque([root])
        max_branch = 0
        while len(paths) != 0:
            edge_color = 0
            current = paths.popleft()
            if current == root:
                parent = -1
                parent_color = -1
            else:
                parent = adj[current][0]
                parent_color = color[parent][current]
            for v in adj[current]:
                if v != parent:
                    paths.append(v)
                    edge_color += 1
                    if edge_color == parent_color:
                        edge_color += 1
                    color[current][v] = edge_color
                max_branch = max(max_branch, edge_color)
        return max_branch
        
 
    n = ii()
    # 各辺の両端の頂点 index を保存したペア (tuple) の list
    L = [tuple(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]
    # 隣接リスト
    adj = [[] for _ in range(n)]
    for pair in L:
        a, b = pair
        adj[a].append(b)
        adj[b].append(a)
    # 色情報 (int) が記載される隣接行列
    color = [[None] * n for _ in range(n)]
    
    print(bfs_tree_traverse(0))
    for pair in L:
        a, b = pair
        print(color[a][b])
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
 
import sys
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()

 
def main():
    input = sys.stdin.readline      # 改行文字が残ることに注意
    def ii():  return int(input())
            

    def bfs_tree_traverse(start):
        paths = deque([[start]])
        max_branch = 0
        pp = paths.popleft    # 定数倍高速化への道のり
        pa = paths.append    # 定数倍高速化への道のり
        while paths:
            # current_path = paths.popleft()
            current_path = pp()    # 定数倍高速化への道のり
            u = current_path[-1]
            previous = current_path[-2] if len(current_path)>=2 else -1
            previous_color = color[current_path[-2]][u] if len(current_path)>=2 else 0
            count = 0    # 現在の頂点 u から伸びるリンクの数を数える
            current_color = 0
            for v in adj[u]:
                count += 1    # 親へのリンクも含めて数えている
                if v != previous:
                    # tmp = current_path[:]
                    tmp = current_path[-1:]    # 定数倍高速化への道のり
                    tmp.append(v)
                    pa(tmp)    # 定数倍高速化への道のり
                    current_color += 1
                    if current_color == previous_color:
                        current_color += 1
                    color[u][v] = current_color
                    # color[v][u] = current_color    # 定数倍高速化への道のり
            max_branch = max(max_branch, count)
        return max_branch
 
 
    n = ii()
    adj = [[] for _ in range(n)]
 
    # L = [tuple(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]    # 定数倍高速化への道のり
    L = [None] * (n-1)   # 定数倍高速化への道のり
    for i in range(n-1):
        L[i] = tuple(map(lambda x: int(x)-1, input().rstrip().split()))
 
    for pair in L:
        a, b = pair
        adj[a].append(b)
        adj[b].append(a)
    
    color = [[None] * n for _ in range(n)]
    
    print(bfs_tree_traverse(0))
    for pair in L:
        a, b = pair
        print(color[a][b])
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    
    
    def bfs_tree_traverse(start):
        paths = deque([[start]])
        max_branch = 0
        pp = paths.popleft    # 定数倍高速化への道のり
        pa = paths.append    # 定数倍高速化への道のり
        while paths:
            # print(paths)
            # current_path = paths.popleft()
            current_path = pp()    # 定数倍高速化への道のり
            u = current_path[-1]
            previous = current_path[-2] if len(current_path)>=2 else -1
            previous_color = color[current_path[-2]][u] if len(current_path)>=2 else 0
            count = 0    # 現在の頂点 u から伸びるリンクの数を数える
            current_color = 0
            for v in adj[u]:
                count += 1    # 親へのリンクも含めて数えている
                if v != previous:
                    # tmp = current_path[:]
                    tmp = current_path[-1:]    # 定数倍高速化への道のり
                    tmp.append(v)
                    pa(tmp)    # 定数倍高速化への道のり
                    current_color += 1
                    if current_color == previous_color:
                        current_color += 1
                    color[u][v] = current_color
                    # color[v][u] = current_color    # 定数倍高速化への道のり
            max_branch = max(max_branch, count)
        return max_branch


    n = ii()
    adj = [[] for _ in range(n)]

    # L = [tuple(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]    # 定数倍高速化への道のり
    L = [None] * (n-1)   # 定数倍高速化への道のり
    for i in range(n-1):
        L[i] = tuple(map(lambda x: int(x)-1, input().rstrip().split()))

    for pair in L:
        a, b = pair
        adj[a].append(b)
        adj[b].append(a)
    
    color = [[None] * n for _ in range(n)]
    
    print(bfs_tree_traverse(0))
    for pair in L:
        a, b = pair
        print(color[a][b])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    
    
    def bfs_tree_traverse(start):
        paths = deque([[start]])
        max_branch = 0
        while paths:
            # print(paths)
            current_path = paths.popleft()
            u = current_path[-1]
            previous = current_path[-2] if len(current_path)>=2 else -1
            previous_color = color[current_path[-2]][u] if len(current_path)>=2 else 0
            count = 0    # 現在の頂点 u から伸びるリンクの数を数える
            current_color = 0
            for v in adj[u]:
                count += 1    # 親へのリンクも含めて数えている
                if v != previous:
                    # tmp = current_path[:]
                    tmp = current_path[-1:]    # 定数倍高速化への道のり
                    tmp.append(v)
                    paths.append(tmp)
                    current_color += 1
                    if current_color == previous_color:
                        current_color += 1
                    color[u][v] = current_color
                    # color[v][u] = current_color    # 定数倍高速化への道のり
            max_branch = max(max_branch, count)
        return max_branch

    n = ii()
    adj = [[] for _ in range(n)]
    L = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]
    for pair in L:
        a, b = pair
        adj[a].append(b)
        adj[b].append(a)
    color = [[None] * n for _ in range(n)]
    
    print(bfs_tree_traverse(0))
    for pair in L:
        a, b = pair
        print(color[a][b])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    
    
    def bfs_tree_traverse(start):
        paths = deque([[start]])
        max_branch = 0
        while paths:
            # print(paths)
            current_path = paths.popleft()
            u = current_path[-1]
            previous = current_path[-2] if len(current_path)>=2 else -1
            previous_color = color[current_path[-2]][u] if len(current_path)>=2 else 0
            count = 0    # 現在の頂点 u から伸びるリンクの数を数える
            current_color = 0
            for v in adj[u]:
                count += 1    # 親へのリンクも含めて数えている
                if v != previous:
                    tmp = current_path[:]
                    tmp.append(v)
                    paths.append(tmp)
                    current_color += 1
                    if current_color == previous_color:
                        current_color += 1
                    color[u][v] = current_color
                    color[v][u] = current_color
            max_branch = max(max_branch, count)
        return max_branch

    n = ii()
    adj = [[] for _ in range(n)]
    L = [list(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]
    for pair in L:
        a, b = pair
        adj[a].append(b)
        adj[b].append(a)
    color = [[None] * n for _ in range(n)]
    
    print(bfs_tree_traverse(0))
    for pair in L:
        a, b = pair
        print(color[a][b])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
g1 = [[-1] * n for _ in range(n)]
g2= [[] for _ in range(n)]
deg = [0] * n

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

k = max(deg)
print(k)

s = deg.index(k)

q = deque([s])
novisit = [True] * n
novisit[s] = False

color = [[] for _ in range(n)]
ans = [0] * (n - 1)

while q:
    v = q.popleft()
    for i in range(len(g2[v])):
        if novisit[g2[v][i]]:
            u = g2[v][i]
            q.append(u)
            novisit[u] = False
            for j in range(1, k + 1):
                if (not j in color[v]) and (not j in color[u]):
                    color[v].append(j)
                    color[u].append(j)
                    ans[g1[v][u]] = j
                    break

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