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:
import sys
sys.setrecursionlimit(200000)

n = int(input())

Adj_dict = {}
All_edges = []
for i in range(n):
    new = {i:[]}
    Adj_dict.update(new)
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a-1].append(b-1)
    Adj_dict[b-1].append(a-1)
    All_edges.append((a-1,b-1))

max_val_count = 0
start_node = 0
for key, val in Adj_dict.items():
    if len(val) >= max_val_count:
        max_val_count = len(val)
        start_node = key


Visited = [False for _ in range(n)]
Colors_use = [False for _ in range(max_val_count)]
Colors_use_raw = [False for _ in range(max_val_count)]

edges_colors = {}

def coloring(Adj_dict, start, Visited, Colors_use):
    
    # 終端処理
    if Visited[start]:
        return
    
    Visited[start] = True

    for node in Adj_dict[start]:
        if Visited[node] == False:
            color = Colors_use.index(False) + 1
            Colors_use[color-1] = True
            
            edge_color = {(min(node, start), max(node, start)): color}
            edges_colors.update(edge_color)
            
            New_Colors_use = Colors_use_raw.copy()
            New_Colors_use[color-1] = True
            
            coloring(Adj_dict, node, Visited, New_Colors_use)
    return

coloring(Adj_dict, start_node, Visited, Colors_use)

print(max_val_count)
for edge in All_edges:
    print(edges_colors[edge])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

n = int(input())

Adj_dict = {}
All_edges = []
for i in range(n):
    new = {i:[]}
    Adj_dict.update(new)
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a-1].append(b-1)
    Adj_dict[b-1].append(a-1)
    All_edges.append((a-1,b-1))

max_val_count = 0
start_node = 0
for key, val in Adj_dict.items():
    if len(val) >= max_val_count:
        max_val_count = len(val)
        start_node = key


Visited = [False for _ in range(n)]
Colors_use = [False for _ in range(max_val_count)]
edges_colors = {}

def coloring(Adj_dict, start, Visited, Colors_use):
    
    # 終端処理
    if Visited[start]:
        return
    
    Visited[start] = True

    for node in Adj_dict[start]:
        if Visited[node] == False:
            color = Colors_use.index(False) + 1
            Colors_use[color-1] = True
            
            edge_color = {(min(node, start), max(node, start)): color}
            edges_colors.update(edge_color)
            
            New_Colors_use = [False for _ in range(max_val_count)]
            New_Colors_use[color-1] = True
            
            coloring(Adj_dict, node, Visited, New_Colors_use)
    return

coloring(Adj_dict, start_node, Visited, Colors_use)

print(max_val_count)
for edge in All_edges:
    print(edges_colors[edge])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
data = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    data[a].append([i,b])  # i本目でbに
    data[b].append([i,a])

k = max(len(data[i]) for i in range(n))
print(k)
ans = [-1 for i in range(n)]


stack = [[0,n,k]]
while stack:
    now,pre,pre_path = stack.pop()
    color = [True for i in range(k + 1)]
    color[ans[pre_path]] = False

    for nex_path, nex in data[now]:
        if nex == pre: continue
        for num, c in enumerate(color):
            if c:
                ans[nex_path] = num
                color[num] = False
                stack.append([nex, now, nex_path])
                break


for x  in ans[:-1]:
    print(x+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
data = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    data[a].append([i,b])  # i本目でbに
    data[b].append([i,a])

k = max(len(data[i]) for i in range(n))
print(k)
ans = [-1 for i in range(n)]

def solve(now,pre,pre_path):
    color = [True for i in range(k+1)]
    color[ans[pre_path]] = False

    for nex_path,nex in data[now]:
        if nex == pre:continue
        for num,c in enumerate(color):
            if c:
                ans[nex_path] = num
                color[num] = False
                solve(nex,now,nex_path)
                break
    return

solve(0,n,k)
for x  in ans[:-1]:
    print(x+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

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


# node: (id, parent_id)
root_node = (1, -1)
open_list = deque([root_node])
n2c = defaultdict(list)
ans = {}
colors = [-1]*(N-1)
while open_list:
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        color = 1
        while True:
            if not color in n2c[cur_id]:
                n2c[cur_id].append(color)
                n2c[child_id].append(color)
                ans[(cur_id, child_id)] = color
                break
            color += 1
        open_list.append((child_id, cur_id))

print(max(list(map(lambda x:len(x), n2c.values()))))
for a, b in inp:
    if (a, b) in ans.keys():
        print(ans[(a, b)])
    else:
        print(ans[(b, a)])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

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


# node: (id, parent_id)
root_node = (1, -1)
open_list = deque([root_node])
n2c = defaultdict(list)
ans = {}
colors = [-1]*(N-1)
while True:
    if len(open_list)==0:
        break
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        color = 1
        while True:
            if not color in n2c[cur_id]:
                n2c[cur_id].append(color)
                n2c[child_id].append(color)
                ans[(cur_id, child_id)] = color
                break
            color += 1
        open_list.append((child_id, cur_id))

print(max(list(map(lambda x:len(x), n2c.values()))))
for a, b in inp:
    if (a, b) in ans.keys():
        print(ans[(a, b)])
    else:
        print(ans[(b, a)])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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


# node: (id, parent_id)
root_node = (1, -1)
open_list = [root_node]
n2c = defaultdict(list)
ans = {}
colors = [-1]*(N-1)
while True:
    if len(open_list)==0:
        break
    cur_node = open_list.pop()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        color = 1
        while True:
            if not color in n2c[cur_id]:
                n2c[cur_id].append(color)
                n2c[child_id].append(color)
                ans[(cur_id, child_id)] = color
                break
            color += 1
        open_list.append((child_id, cur_id))

print(max(list(map(lambda x:len(x), n2c.values()))))
for a, b in inp:
    if (a, b) in ans.keys():
        print(ans[(a, b)])
    else:
        print(ans[(b, a)])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
edges = defaultdict(list)
inp = []
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
    inp.append((a, b))


# node: (id, parent_id)
root_node = (1, -1)
open_list = [root_node]
n2c = defaultdict(list)
ans = {}
while True:
    if len(open_list)==0:
        break
    cur_node = open_list.pop()
    cur_id, parent_id = cur_node
    adj_id_list = edges[cur_id]
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        color = 1
        while True:
            if not color in n2c[cur_id]:
                n2c[cur_id].append(color)
                n2c[child_id].append(color)
                ans[(cur_id, child_id)] = color
                break
            color += 1
        open_list.append((child_id, cur_id))

print(max(list(map(lambda x:len(x), n2c.values()))))
for a, b in inp:
    if (a, b) in ans.keys():
        print(ans[(a, b)])
    else:
        print(ans[(b, a)])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
C = [[i for i in range(1,K+1)] for j in range(N+1)]
import copy 
w = copy.deepcopy(W)
d = [[0 for i in range(N+1)] for j in range(N+1)]
w.sort()
for i in range(N-1):
    a,b = w[i]
    x = C[a].pop(0)
    C[b].remove(x)
    d[a][b] = x
for i in range(N-1):
    a,b = W[i]
    print(d[a][b])

Submission status: Time Limit Exceeded

Solution code:
# input
n = int(input())

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

# process
k = 0
pcolors = [0 for i in range(n)]
for i in range(n):
    color = 0
    for j in range(n-1):
        if edge[j][0] == i+1:
            color += 1
            if color == pcolors[i]: color += 1

            edge[j][2] = color
            pcolors[edge[j][1]-1] = color
            if k < color: k = color
    

# output
print(k)
for e in edge:
    print(e[2])

Submission status: Time Limit Exceeded

Solution code:
# input
n = int(input())

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

# process
def findcolor(p):
    if p == 1: 
        return 0
    else: 
        for e in edge:
            if e[1] == p:
                return e[2]

for i in range(n):
    i += 1
    color = 0
    pcolor = findcolor(i)
    for j in range(n-1):
        if edge[j][0] == i:
            color += 1
            if color == pcolor: color += 1
            edge[j][2] = color

k = 0
for e in edge:
    if e[2] > k: k = e[2]

# output
print(k)
for e in edge:
    print(e[2])

Submission status: Time Limit Exceeded

Solution code:
# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる
def main():
    from collections import deque
    N = int(input())
    graph = {i:[] for i in range(N)}
    A = [0] * (N-1)
    B = [0] * (N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
        A[i] = a
        B[i] = b        
        if i == 0:
            start = a

    K = 0
    for some in graph.values():
        K = max(len(some), K)

    # BFSのためのデータ構造
    que = deque()
    dist = [False] * N

    # 初期条件
    que.append(start)
    color_num = {i:{} for i in range(N)}
    dist[start] = True

    # BFS開始
    while que:
        v = que[0]
        que.popleft()
        tmp = 0
        for new_v in graph[v]:
            if dist[new_v]:
                continue
            # 新たな頂点 new_vについて距離情報を更新してキューを追加する
            dist[new_v] = True
            que.append(new_v)
            # 色を塗る
            for k in range(tmp+1, K+1):
                if k in color_num[v].values():
                    continue
                else:
                    color_num[v][new_v] = k
                    color_num[new_v][v] = k
                    tmp = k
                    break
    # 答えの出力
    print(K)
    for i in range(N-1):
        print(color_num[A[i]][B[i]])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる
def main():
    from collections import deque
    N = int(input())
    graph = {i:[] for i in range(N)}
    AB = [[0] * 2 for _ in range(N-1)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)
        AB[i][0], AB[i][1] = a, b
        if i == 0:
            start = a

    K = 0
    for some in graph.values():
        K = max(len(some), K)

    # BFSのためのデータ構造
    que = deque()
    dist = [False] * N

    # 初期条件
    que.append(start)
    color_num = {i:{} for i in range(N)}
    dist[start] = True

    # BFS開始
    while que:
        v = que[0]
        que.popleft()
        tmp = 0
        for new_v in graph[v]:
            if dist[new_v]:
                continue
            # 新たな頂点 new_vについて距離情報を更新してキューを追加する
            dist[new_v] = True
            que.append(new_v)
            # 色を塗る
            for k in range(tmp+1, K+1):
                if k in color_num[v].values():
                    continue
                else:
                    color_num[v][new_v] = k
                    color_num[new_v][v] = k
                    tmp = k
                    break
    # 答えの出力
    print(K)
    for i in range(N-1):
        print(color_num[AB[i][0]][AB[i][1]])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる

from collections import deque
N = int(input())
graph = {i:[] for i in range(N)}
AB = [[0] * 2 for _ in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    AB[i][0], AB[i][1] = a, b
    if i == 0:
        start = a

K = 0
for some in graph.values():
    K = max(len(some), K)

# BFSのためのデータ構造
que = deque()
dist = [False] * N

# 初期条件
que.append(start)
color_num = {i:{} for i in range(N)}
dist[start] = True

# BFS開始
while que:
    v = que[0]
    que.popleft()
    tmp = 0
    for new_v in graph[v]:
        if dist[new_v]:
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューを追加する
        dist[new_v] = True
        que.append(new_v)
        # 色を塗る
        for k in range(tmp+1, K+1):
            if k in color_num[v].values():
                continue
            else:
                color_num[v][new_v] = k
                color_num[new_v][v] = k
                tmp = k
                break
# 答えの出力
print(K)
for i in range(N-1):
    print(color_num[AB[i][0]][AB[i][1]])

Submission status: Time Limit Exceeded

Solution code:
# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる

from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
AB = [[0] * 2 for _ in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    AB[i][0], AB[i][1] = a, b

K = 0
for i in range(N-1):
    K = max(len(graph[i]), K)

# BFSのためのデータ構造
que = deque()
dist = [False] * N

# 初期条件
que.append(0)
color_num = [[0] * N for _ in range(N)]
dist[0] = True
# BFS開始
while que:
    v = que[0]
    que.popleft()
    tmp = 0
    for new_v in graph[v]:
        if dist[new_v]:
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューを追加する
        dist[new_v] = True
        que.append(new_v)
        # 色を塗る
        for k in range(tmp+1, K+1):
            if k in color_num[v]:
                continue
            else:
                color_num[v][new_v] = k
                color_num[new_v][v] = k
                tmp = k
                break

# 答えの出力
print(K)
for i in range(N-1):
    print(color_num[AB[i][0]][AB[i][1]])

Submission status: Time Limit Exceeded

Solution code:
# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる

from collections import deque
N = int(input())
graph = [[] * N for _ in range(N)]
A = [0] * (N-1)
B = [0] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    A[i] = a
    B[i] = b

K = 0
for i in range(N):
    K = max(len(graph[i]), K)

# BFSのためのデータ構造
que = deque()
dist = [False] * N

# 初期条件
que.append(0)
color_num = [[0] * N for _ in range(N)]
dist[0] = True
# BFS開始
while que:
    v = que[0]
    que.popleft()
    tmp = 0
    for new_v in graph[v]:
        if dist[new_v]:
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューを追加する
        dist[new_v] = True
        que.append(new_v)
        # 色を塗る
        for k in range(tmp+1, K+1):
            if k in color_num[v]:
                continue
            if k in color_num[new_v]:
                continue
            else:
                color_num[v][new_v] = k
                color_num[new_v][v] = k
                tmp = k
                break

# 答えの出力
print(K)
for i in range(N-1):
    print(color_num[A[i]][B[i]])

Submission status: Time Limit Exceeded

Solution code:
# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる

from collections import deque
N = int(input())
graph = [[] * N for _ in range(N)]
A = [0] * (N-1)
B = [0] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    A[i] = a
    B[i] = b
K = 0
for i in range(N):
    K = max(len(graph[i]), K)

ans = [[0] * N for _ in range(N)]

# BFSのためのデータ構造
dist = [False for _ in range(N)]
que = deque()

# 初期条件
dist[0] = True
que.append(0)
color_num = [[] for _ in range(N)]

# BFS開始
while que:
    v = que[0]
    que.popleft()
    for new_v in graph[v]:
        if dist[new_v]:   # すでに探索済みの頂点は探索しない
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューを追加する
        dist[new_v] = True
        que.append(new_v)
        for k in range(1, K+1):
            if k in color_num[v]:
                continue
            if k in color_num[new_v]:
                continue
            else:
                ans[v][new_v] = k
                ans[new_v][v] = k
                color_num[v].append(k)
                color_num[new_v].append(k)
                break
        

# 答えの出力
print(K)
for i in range(N-1):
    print(ans[A[i]][B[i]])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = [[] for _ in range(N)]
color = [[-1]*N for _ in range(N)]
E = []
for i in range(N-1):
	a, b = map(int, input().split())
	G[a-1].append(b-1)
	E.append((a, b))
	
used = [set() for _ in range(N)]

ans = 0
for a,eadges in enumerate(G):
	c = 1
	for b in eadges:
		while c in (used[b] | used[a]):
			c+=1
		color[a][b] = c
		used[a].add(c)
		used[b].add(c)
		if ans < c:
			ans = c

print(ans)
for e in E:
	a,b = map(int, e)
	print(color[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
G = [[] for _ in range(N)]
color = [[-1]*N for _ in range(N)]
E = []
for i in range(N-1):
	a, b = map(int, input().split())
	G[a-1].append(b-1)
	E.append((a, b))
	
used = [set() for _ in range(N)]

ans = 0
for a,eadges in enumerate(G):
	c = 1
	for b in eadges:
		while c in used[b] or c in used[a]:
			c+=1
		color[a][b] = c
		used[a].add(c)
		used[b].add(c)
		if ans < c:
			ans = c

print(ans)
for e in E:
	a,b = map(int, e)
	print(color[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from collections import deque

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]


def main():
	N = INT()
	M = [MAP() for _ in range(N-1)]

	G = [[] for _ in range(N)]
	for m in M:
		a, b = m
		a -= 1
		b -= 1
		G[a].append(b)
		G[b].append(a)

	#print(G)

	dist = [-1] * N
	queue = deque()

	dist[0] = 0
	queue.append(0)

	used = [[0] for _ in range(N)]
	ans = dict()
	max_ans = 0

	insort = bisect.insort
	while queue:
		v = queue.popleft()

		col = 1	
		for nv in G[v]:
			if dist[nv] != -1: continue
			# print(v, nv)
			dist[nv] = 1

			used_col = used[v]
			used_col.sort()
			for c in used_col:
				if col == c: col += 1

			insort(used[v], col)
			insort(used[nv], col)
			ans[tuple([v, nv])] = col
			queue.append(nv)
			max_ans = max(max_ans, col)

	# print(used)

	print(max_ans)
	for m in M:
		print(ans[(m[0]-1, m[1]-1)])

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from collections import deque

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)

#print(G)

dist = [-1] * N
queue = deque()

dist[0] = 0
queue.append(0)

used = [[0] for _ in range(N)]
ans = dict()
max_ans = 0

insort = bisect.insort
while queue:
	v = queue.popleft()

	col = 1	
	for nv in G[v]:
		if dist[nv] != -1: continue
		# print(v, nv)
		dist[nv] = 1

		used_col = used[v]
		used_col.sort()
		for c in used_col:
			if col == c: col += 1

		insort(used[v], col)
		insort(used[nv], col)
		ans[tuple([v, nv])] = col
		queue.append(nv)
		max_ans = max(max_ans, col)

# print(used)

print(max_ans)
for m in M:
	print(ans[(m[0]-1, m[1]-1)])

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from collections import deque, defaultdict

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)

#print(G)

dist = [-1] * N
queue = deque()

dist[0] = 0
queue.append(0)

used = [[0] for _ in range(N)]
ans = dict()
max_ans = 0

insort = bisect.insort
while queue:
	v = queue.popleft()
	
	for nv in G[v]:
		if dist[nv] != -1: continue
		# print(v, nv)
		dist[nv] = 1

		col = 1
		for c in used[v]:
			if col == c: col += 1

		insort(used[v], col)
		insort(used[nv], col)
		ans[tuple([v, nv])] = col
		queue.append(nv)
		max_ans = max(max_ans, col)

# print(used)

print(max_ans)
for m in M:
	print(ans[(m[0]-1, m[1]-1)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)

#print(G)

dist = [-1] * N
queue = deque()

dist[0] = 0
queue.append(0)

used = [[0] for _ in range(N)]
ans = dict()
max_ans = 0

while queue:
	v = queue.popleft()
	
	for nv in G[v]:
		if dist[nv] != -1: continue
		# print(v, nv)
		dist[nv] = 1

		col = 1
		for c in sorted(used[v]):
			if col == c: col += 1

		used[v].append(col)
		used[nv].append(col)
		ans[tuple([v, nv])] = col
		queue.append(nv)
		max_ans = max(max_ans, col)

# print(used)

print(max_ans)
for m in M:
	print(ans[(m[0]-1, m[1]-1)])

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from collections import deque, defaultdict

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	# G[b].append(a)

#print(G)

dist = [-1] * N
queue = deque()

dist[0] = 0
queue.append(0)

used = defaultdict(list)
ans = dict()
max_ans = 0

insort = bisect.insort_left
while queue:
	v = queue.popleft()
	
	for nv in G[v]:
		if dist[nv] != -1: continue
		# print(v, nv)
		dist[nv] = 1

		col = 1
		for c in used[v]:
			if col == c: col += 1

		insort(used[v],col)
		insort(used[nv],col)
		ans[tuple([v, nv])] = col
		queue.append(nv)
		max_ans = max(max_ans, col)

# print(used)

print(max_ans)
for m in M:
	print(ans[(m[0]-1, m[1]-1)])

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from collections import deque, defaultdict

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	# G[b].append(a)

#print(G)

dist = [-1] * N
queue = deque()

dist[0] = 0
queue.append(0)

used = defaultdict(list)
ans = dict()
max_ans = 0

while queue:
	v = queue.popleft()
	
	for nv in G[v]:
		if dist[nv] != -1: continue
		# print(v, nv)
		dist[nv] = 1

		col = 1
		for c in used[v]:
			if col == c: col += 1

		bisect.insort_left(used[v],col)
		bisect.insort_left(used[nv],col)
		ans[tuple([v, nv])] = col
		queue.append(nv)
		max_ans = max(max_ans, col)

# print(used)

print(max_ans)
for m in M:
	print(ans[(m[0]-1, m[1]-1)])

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from collections import deque, defaultdict

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)

#print(G)

dist = [-1] * N
queue = deque()

dist[0] = 0
queue.append(0)

used = defaultdict(list)
ans = dict()
max_ans = 0

while queue:
	v = queue.popleft()
	
	for nv in G[v]:
		if dist[nv] != -1: continue
		# print(v, nv)
		dist[nv] = 1

		col = 1
		for c in used[v]:
			if col == c: col += 1

		bisect.insort_left(used[v],col)
		bisect.insort_left(used[nv],col)
		ans[tuple([v, nv])] = col
		queue.append(nv)
		max_ans = max(max_ans, col)

# print(used)

print(max_ans)
for m in M:
	print(ans[(m[0]-1, m[1]-1)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)

#print(G)

dist = [-1] * N
queue = deque()

dist[0] = 0
queue.append(0)

used = defaultdict(list)
ans = dict()
max_ans = 0

while queue:
	v = queue.popleft()
	
	for nv in G[v]:
		if dist[nv] != -1: continue
		# print(v, nv)
		dist[nv] = 1

		col = 1
		for c in sorted(used[v]):
			if col == c: col += 1

		used[v].append(col)
		used[nv].append(col)
		ans[tuple([v, nv])] = col
		queue.append(nv)
		max_ans = max(max_ans, col)

# print(used)

print(max_ans)
for m in M:
	print(ans[(m[0]-1, m[1]-1)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)

#print(G)

dist = [-1] * N
queue = deque()

dist[0] = 0
queue.append(0)

used = defaultdict(list)
ans = dict()
max_ans = 0

while queue:
	v = queue.popleft()
	
	for nv in G[v]:
		if dist[nv] != -1: continue
		# print(v, nv)
		dist[nv] = 1

		col = 1
		for c in sorted(used[v]):
			if col == c: col += 1
		for c in sorted(used[nv]):
			if col == c: col += 1

		used[v].append(col)
		used[nv].append(col)
		ans[tuple([v, nv])] = col
		queue.append(nv)
		max_ans = max(max_ans, col)

# print(used)

print(max_ans)
for m in M:
	print(ans[(m[0]-1, m[1]-1)])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
M = [MAP() for _ in range(N-1)]

G = [[] for _ in range(N)]
for m in M:
	a, b = m
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)

#print(G)

dist = [-1] * N
queue = deque()

dist[0] = 0
queue.append(0)

used = [[0]*len(g) for g in G]
ans = dict()
max_ans = 0

while queue:
	v = queue.popleft()
	
	for nv in G[v]:
		if dist[nv] != -1: continue
		# print(v, nv)
		dist[nv] = 1

		col = 1
		for c in used[v]+used[nv]:
			if col == c: col += 1
		for c in used[v]+used[nv]:
			if col == c: col += 1

		used[v].append(col)
		used[nv].append(col)
		ans[tuple([v, nv])] = col
		queue.append(nv)
		max_ans = max(max_ans, col)

# print(used)

print(max_ans)
for m in M:
	print(ans[(m[0]-1, m[1]-1)])