Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import copy

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(node)

Visited = [False for _ in range(n+1)]
Visited[node] = True
Visited_to = [[] for _ in range(n+1)]

Colors = [x for x in range(1, max_edges+1)]
Colors_list = [[x for x in range(1, max_edges+1)] for x in range(n+1)]
Edge_colors = [[-1 for _ in range(n+1)] for _ in range(n+1)]

# print(Colors_list)

while dq:
    # Colors_copy = copy.deepcopy(Colors)    
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    # for v in Visited_from:
    #     Colors_copy.remove(Edge_colors[node][v])

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited_to[next_node].append(node)
        Visited[next_node] = True

        use_color = Colors_list[node][0]
        Colors_list[node].remove(use_color)
        Colors_list[next_node].remove(use_color)

        Edge_colors[node][next_node] = use_color
        Edge_colors[next_node][node] = use_color

 #       del Colors_copy[0]

print(max_edges)
for ab in AB:
    print(Edge_colors[ab[0]][ab[1]])

Fixed submission:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import copy

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(node)

Visited = [False for _ in range(n+1)]
Visited[node] = True
Visited_to = [[] for _ in range(n+1)]

Colors = [x for x in range(1, max_edges+1)]
Colors_list = [[x for x in range(1, max_edges+1)] for x in range(n+1)]
Edge_colors = [[-1 for _ in range(n+1)] for _ in range(n+1)]

# print(Colors_list)

while dq:
    # Colors_copy = copy.deepcopy(Colors)    
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    # for v in Visited_from:
    #     Colors_copy.remove(Edge_colors[node][v])

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited_to[next_node].append(node)
        Visited[next_node] = True

        use_color = Colors_list[node][0]
        Colors_list[node].remove(use_color)
        Colors_list[next_node].remove(use_color)

        Edge_colors[node][next_node] = use_color
        Edge_colors[next_node][node] = use_color

 #       del Colors_copy[0]

print(max_edges)
for ab in AB:
    print(Edge_colors[ab[0]][ab[1]])

Fixed submission:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import copy

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(node)

Visited = [False for _ in range(n+1)]
Visited[node] = True
Visited_to = [[] for _ in range(n+1)]

Colors = [x for x in range(1, max_edges+1)]
Edge_colors = [[-1 for _ in range(n+1)] for _ in range(n+1)]


while dq:
    Colors_copy = copy.deepcopy(Colors)    
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    Visited_from = Visited_to[node]
    for v in Visited_from:
        Colors_copy.remove(Edge_colors[node][v])

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited_to[next_node].append(node)
        Visited[next_node] = True
        Edge_colors[node][next_node] = Colors_copy[0]
        Edge_colors[next_node][node] = Colors_copy[0]
        del Colors_copy[0]

print(max_edges)
for ab in AB:
    print(Edge_colors[ab[0]][ab[1]])

Fixed submission:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(200000)

n = int(input())

#Adj_dict = {}
All_edges = []
# for i in range(n):
#     new = {i:[]}
#     Adj_dict.update(new)
Adj_dict= {i:[] for i in range(n)}

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

Fixed submission:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)

Buggy python submission (verdict: Time Limit Exceeded):
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])

Fixed submission:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)

Buggy python submission (verdict: Runtime Error):
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])

Fixed submission:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)

Buggy python submission (verdict: Time Limit Exceeded):
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])

Fixed submission:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)

Buggy python submission (verdict: Time Limit Exceeded):
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])

Fixed submission:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)

Buggy python submission (verdict: Runtime Error):
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])

Fixed submission:
from collections import deque

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB_dict = {}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])
    AB_dict.update({str(a)+'_'+str(b):0})

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(1)

Visited = [False for _ in range(n+1)]
Visited[1] = True
Colors = [0 for _ in range(n+1)]

while dq:
    c = 1
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited[next_node] = True

        if c == Colors[node]:
            c += 1
        Colors[next_node] = c
        c += 1
        if node < next_node:
            AB_dict[str(node)+'_'+str(next_node)] = Colors[next_node]
        else:
            AB_dict[str(next_node)+'_'+str(node)] = Colors[next_node]

print(max_edges)
for ab in AB:
    a = ab[0]
    b = ab[1]
    print(AB_dict[str(a)+'_'+str(b)])
# print(AB_dict)