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

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


class Edge():
    def __init__(self, to_, id_):
        self._to = to_
        self._id = id_


G = [[Edge]]
ans = []

sys.setrecursionlimit(1000000)


def dfs(v, color, parent=-1):
    global G
    global ans
    c = 1
    if c == color:
        c += 1
    for g in G[v]:
        if g._to == parent:
            continue
        if ans[g._id] != -1:
            continue
        ans[g._id] = c
        dfs(g._to, c, v)
        c += 1
        if c == color:
            c += 1
    return


def main():
    
    global G
    global ans
    N = Scanner.int()
    G = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append(Edge(b, i))
        G[b].append(Edge(a, i))
    ans = [-1 for _ in range(N-1)]
    dfs(0, 0)
    print(max(ans))
    print(*ans, sep="\n")
    return


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
links = [[] for _ in range(n)]
colors = [0] * (n - 1)

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

def dfs(a, color):
    c = 1
    for b, i in links[a]:
        if c == color:
            c += 1
        colors[i] = c
        dfs(b, c)
        c += 1


dfs(0, 0)
print(max(colors))
for color in colors:
    print(color)

Solution (Python):
from collections import deque
n = int(input())
e = [[] for _ in range(n)]
AB = [list(map(int, input().split())) for _ in range(n - 1)]
AB = [(a -1, b - 1) for a, b in AB]

for itr, (a, b) in enumerate(AB):
  e[a].append((b, itr))
  e[b].append((a, itr))
  
cidx = max([len(i) for i in e])

ans = [-1] * (n - 1)

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

while q:
  v, p, pcol = q.popleft()
  col = 1
  for u, i in e[v]:
    if u != p:
      
      if col == pcol:
        col += 1
      if ans[i] == -1: 
        ans[i] = col
      q.append((u, v, col))
      col += 1 

print(cidx)
for i in ans:
  print(i)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**6)
n = int(input())
edge = [tuple(int(i) for i in input().split()) for i in range(n-1)]
to = [[] for _ in range(n+1)]
for e in edge:
    a,b = e
    to[a].append(b)
    to[b].append(a)
color = {}

def f(cn,pn,pc):
    c = 1
    for nn in to[cn]:
        if nn == pn: continue
        if c == pc: c += 1
        tmp = (cn,nn)
        color[(min(tmp),max(tmp))] = c
        f(nn,cn,c)
        c += 1

f(1,0,0)
print(max(color.values()))
for key in edge: print(color[key])

Solution (Python):
import sys,math

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	ans = {}
	order = []
	for i in range(N-1):
		a,b = MI()
		a -= 1;b -= 1
		ans[str(a)+"-"+str(b)] = 0
		order.append(str(a)+"-"+str(b))
		to[a].append(b);to[b].append(a)
	
	def bfs():
		from collections import deque
		hist = [True]*N
		que = deque()
		que.append(0)
		e_colors = [0]*N
		max_c = 0
		while len(que) > 0:
			n = que.popleft()
			hist[n]=False
			for i in to[n]:
				if(hist[i]):
					ch = e_colors[n] | e_colors[i]
					index = int(math.log2(~ch & -~ch))
					e_colors[n] += 1 << index
					e_colors[i] += 1 << index
					ans[str(min(n,i))+"-"+str(max(n,i))] = index+1
					if(max_c < index+1): max_c = index+1
					que.append(i)
		print(max_c)
		for i in order:
			print(ans[i])

	bfs()


main()

Solution (Python):
from collections import defaultdict, deque

d = defaultdict(list)
N = int(input())
l = []

for _ in range(N-1):
    a, b = map(int, input().split())
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
    l.append((a,b))

parent = [0]*(N)
used = [False]*(N)
used[0]=True

q = deque()
q.append(0)
res = {}

max_n = 0
while q:
    p = q.popleft()
    color_num = 0
    for i in d[p]:
        if used[i]:continue

        used[i] = True
        
        color_num += 1
        
        if color_num == parent[p]:
            color_num+=1 
        parent[i] = color_num
        res[(p,i)] = color_num
        q.append(i)
    max_n = max(max_n, color_num)

print(max_n)
for i in l:
    print(res[i])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
AB = [list(map(int,readline().split())) for i in range(N-1)]

graph = [[] for _ in range(N+1)] 
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)


stack = [1]
parent = [0]*(N+1)
order = []
while stack:
    x = stack.pop()
    order.append(x)
    for i in graph[x]:
        if i == parent[x]:
            continue
        parent[i] = x
        stack.append(i)


color = [-1]*(N+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if parent[x] == y:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1

ans = []
for a,b in AB:
    if parent[a] == b: 
        ans.append(color[a])
    else:
        ans.append(color[b])

print(max(ans))
for i in ans:
    print(i)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    tree = {i:[] for i in range(N)}
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges.append((a, b))
        tree[a].append(b)

    ans = {}
    frontier = deque([(1,0)])
    while frontier:
        u, prev_color = frontier.pop()
        if tree.get(u) is None:
            continue

        over_color = len(tree[u])+1
        for i, v in enumerate(tree[u], 1):
            color = i if i != prev_color else over_color
            ans[u, v] = color
            frontier.appendleft((v, color))

    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])


    
main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    tree = {i:[] for i in range(N)}
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges.append((a, b))
        tree[a].append(b)

    ans = {}
    frontier = deque([(1,0)])
    while frontier:
        u, prev_color = frontier.pop()
        if tree.get(u) is None:
            continue
        for i, v in enumerate(tree[u], 1):
            color = i if i != prev_color else len(tree[u])+1
            ans[u, v] = color
            frontier.appendleft((v, color))

    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])


    
main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def main():
    N = int(input())
    edges = list(readlines(N-1))
    tree = {i:[] for i in range(N)}
    for a, b in edges:
        tree[a].append(b)

    ans = {}
    frontier = deque([(1,0)])
    while frontier:
        u, prev_color = frontier.pop()
        if tree.get(u) is None:
            continue
        for i, v in enumerate(tree[u], 1):
            color = i if i != prev_color else len(tree[u])+1
            ans[u, v] = color
            frontier.appendleft((v, color))

    print(max(ans.values()))
    for u,v in edges:
        print(ans[u,v])


    
main()

Solution (Python):
from collections import namedtuple, deque


def bfs():
    while queue:
        u = queue.popleft()
        i = 1
        for e in adj[u]:
            if e.t == u:
                continue
            if parent[u] == i:
                i += 1
            parent[e.t] = i
            ans[e.id] = i
            queue.append(e.t)
            i += 1


Edge = namedtuple('Edge', ('t', 'id'))

n = int(input())

adj = [[] for _ in range(n)]
for i in range(n - 1):
    s, t = (int(v) - 1 for v in input().split())
    edge = Edge(t, i)
    adj[s].append(edge)
    adj[t].append(edge)

k = len(max(adj, key=lambda x: len(x)))

queue = deque([0])
parent = [-1] * n
ans = [0] * (n - 1)
bfs()

print(k)
print(*ans, sep='\n')

Solution (Python):
import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append((b,i))
    E[b].append((a,i))

K = max(len(e) for e in E)

print(K)
ans = [-1] * (N-1)





def dfs(v=1,p=0,p_col=-1):
    
    col = 1
    
    
    for u, idx in E[v]:
        
        if u != p:
            
            
            
            if col == p_col:
                col += 1
            ans[idx] = col
            
            
            
            
            dfs(u,v,col)
            
            col += 1

dfs()

print("\n".join(map(str,ans)))

Solution (Python):
import sys
sys.setrecursionlimit(500000)
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append((b,i))
    E[b].append((a,i))

K = max(len(e) for e in E)
print(K)
ans = [-1] * (N-1)
def dfs(v=1,p=0,p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u != p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(u,v,col)
            col += 1
dfs()
print("\n".join(map(str,ans)))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
 
n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append([b, i])
  g[b].append([a, i])
  
ans = [0]*(n-1)
  
def dfs(v, c=-1, p=-1):
  k = 1
  for u, ei in g[v]:
    if u == p:
      continue
    if k == c:
      k += 1
    ans[ei] = k
    k += 1
    dfs(u, ans[ei], v)
 
dfs(0)
print(max(ans))
for i in range(n-1):
  print(ans[i])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append([b, i])
  g[b].append([a, i])
  
ans = [0]*(n-1)
  
def dfs(v, c=-1, p=-1):
  k = 1
  for u, ei in g[v]:
    if u == p:
      continue
    if k == c:
      k += 1
    ans[ei] = k
    k += 1
    dfs(u, ans[ei], v)
 
dfs(0)
print(max(ans))
for i in range(n-1):
  print(ans[i])

Solution (Python):


import sys
input=sys.stdin.readline

N=int(input())

q=[]

l=[[] for i in range(N)]

ans=[1]*N
ans[0]=0


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

mx=0
for index,item in enumerate(l):
    color=1
    while item:
        temp=item.pop(-1)
        if color==ans[index]:
            color+=1
        ans[temp]=color
        color+=1
    mx=max(color-1,mx)

print(mx)
for _,item in q:
    print(ans[item])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

tree = {}
N = 0

def assign(assignment, u, prev_color):
    color = 1
    for v in tree[u]:
        if color == prev_color:
            color += 1
        assignment[u,v] = color
        assign(assignment, v, color)
        color += 1

def main():
    global tree, N
    N = int(input())
    tree = {i: [] for i in range(1,N+1)}
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        edges.append((a, b))
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(200000)

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

def dfs(v, c=-1, p=-1):
  k=1
  for i in range(len(to[v])):
    u, id=to[v][i]
    if u==p:
      continue
    if k==c:
      k+=1
    ans[id]=k
    k+=1
    dfs(u, ans[id], v)

to=[[] for _ in range(N)]
for i in range(N-1):
  a, b=ab[i][0]-1, ab[i][1]-1
  to[a].append([b, i])
  to[b].append([a, i])

dfs(0)
print(max(ans))
for a in ans:
  print(a)

Solution (Python):
from collections import deque

N = int(input())

es = [[] for _ in range(N)]

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


ans = [0] * (N-1)
c = 1
prev_c = -1
"""
現在ノード、そこに至るための直前の辺の色を知っておく必要がある
q : (current_node, prev_color)
今見てるノードと、そこに来る直前のへんが何色かを示す
"""
q = deque()
q.append((0, prev_c))
while q:
    curr_node, pc = q.popleft()
    c = 1
    for edge_num, node in es[curr_node]:
        if c == pc:
            c += 1
        ans[edge_num] = c
        
        q.append((node, c))
        
        c += 1

print(len(set(ans)))
print(*ans, sep="\n")

Solution (Python):

from sys import setrecursionlimit


def genid(a, b):
    if b < a:
        a, b = b, a
    return a * 100000 + b


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

edges = [[] for _ in range(N)]
for a, b in ab:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

colors = {}
q = [(0, -1, -1)]
while q:
    currentNode, usedColor, parentNode = q.pop()
    color = 1
    for childNode in edges[currentNode]:
        if childNode == parentNode:
            continue
        if color == usedColor:
            color += 1
        colors[genid(currentNode, childNode)] = color
        q.append((childNode, color, currentNode))
        color += 1

print(max(len(e) for e in edges))
for a, b in ab:
    print(colors[genid(a - 1, b - 1)])

Solution (Python):
import sys
sys.setrecursionlimit(500000)

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

ans = [-1] * (N-1)
def dfs(v=1, p=0, p_col=-1):
    col = 1
    for u, idx in E[v]:
        if u!=p:
            if col == p_col:
                col += 1
            ans[idx] = col
            dfs(u, v, col)
            col += 1
dfs()
print("\n".join(map(str, ans)))

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N=int(input())
S = [list(map(int, input().split()))+[i] for i in range(N-1)]
A=[None]*(N-1)
l=[[] for i in range(N+1)]
t=[0]*N
t[0]=1
for i in S:
    l[i[0]].append((i[1],i[2]))
    l[i[1]].append((i[0],i[2]))
def haba(o,c):
    p=1
    for i in l[o]:
        if t[i[0]-1]==0:
            if c==p:
                p+=1
            A[i[1]]=p
            t[i[0]-1]=1
            haba(i[0],p)
            p+=1
haba(1,0)
print(max(A))
print(*A,sep="\n")

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(200000)
N=int(input())
S = [list(map(int, input().split()))+[i] for i in range(N-1)]
A=[None]*(N-1)
l=[[] for i in range(N+1)]
t=[0]*N
t[0]=1
for i in S:
    l[i[0]].append((i[1],i[2]))
    l[i[1]].append((i[0],i[2]))
def haba(o,c):
    p=1
    for i in l[o]:
        if t[i[0]-1]==0:
            if c==p:
                p+=1
            A[i[1]]=p
            t[i[0]-1]=1
            haba(i[0],p)
            p+=1
haba(1,0)
print(max(A))
print(*A,sep="\n")

Solution (Python):
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    e = [[] for _ in range(n + 1)]
    
    q = [1]
    c = [0] * (n + 1)
    for a, b in zip(*[iter(ab)] * 2):
        e[a].append(b)
    while q:
        s = q.pop(0)
        d = 0
        for t in e[s]:
            d += 1 + (d + 1 == c[s])
            c[t] = d
            q.append(t)
    return str("{}\n{}".format(max(c), "\n".join(str(c[b]) for _, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
import sys
n = int(input())
sys.setrecursionlimit(2*n)
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    graph[a].append((b, i))
    graph[b].append((a, i))

def DFS(node, p_node=-1, p_color=-1):
    color = 1
    for c_node, edge in graph[node]:
        if c_node==p_node:
            continue
        if color==p_color:
            color += 1
        ans[edge] = color
        DFS(c_node, node, color)
        color += 1
ans = [0]*(n-1)
DFS(0)
k = max(len(i) for i in graph)
print(k)
[print(i) for i in ans]

Solution (Python):
from collections import deque

N = int(input())
edge = [set() for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a].add((b, i))
    edge[b].add((a, i))
    
r = [0] * (N-1)
q = deque([(0, 1)])

while q:
    preC, fromv = q.popleft()
    c = 0
    for tov, i in edge[fromv]:
        edge[tov].remove((fromv, i))
        c += 1 + (c + 1 == preC)
        q.append((c, tov))
        r[i] = c

print(max(r))
for x in r:
    print(x)

Solution (Python):


N = int(input())
edges = [[] for i in range(N+1)]
A = [-1 for i in range(N-1)]

for i in range(N-1):
  a, b = map(int, input().split())
  if i == 0:
    root = a
  edges[a].append((b, i))
  edges[b].append((a, i))

def dfs(u):
  visited = ["white"] * (N + 1)
  stack = [(u, -1, -1)]
  mcolor = -1

  while stack:
    u, p, c = stack.pop()
    visited[u] = "black"

    next = 1
    for (v, i) in edges[u]:
      if v != p and visited[v] != "black":
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[i] = next
        stack.append((v, u, next))
        next += 1
  
  return mcolor

print(dfs(root))

for a in A:
  print(a)

Solution (Python):
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)
d = {}
D = {}
D[1] = 1
k = 1
H = []
list = [1]
sumi = []
while list:
    x = list.pop(0)
    sumi.append(x)
    Y = G[x]
    k = D[x] + 1
    while Y:
        y = Y.pop(0)
        if x in G[y]:
            G[y].remove(x)
        if k > K:
            k -= K
        list.append(y)
        d[(x,y)] = k
        D[y] = k 
        k += 1
        if k > K:
            k -= K
                
for i in range(N-1):
    a,b = W[i]
    print(d[(a,b)])

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)


n = int(input())

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

def dfs(now, prev = 0):
    a, b = min(now, prev), max(now, prev)
    used = COLORS[(a, b)]
    color = 1
    for v in GRAPH[now]:
        if v == prev:
            continue
        next = v
        a, b = min(now, next), max(now, next)
        if color == used:
            color += 1
            COLORS[(a, b)] = color
            color += 1
        else:
            COLORS[(a, b)] = color
            color += 1
    
    for v in GRAPH[now]:
        if v == prev:
            continue
        next = v
        dfs(next, now)

COLORS = {(0, 1):0}
dfs(1)

print(max(COLORS.values()))
for edge in EDGES:
    print(COLORS[edge])

Solution (Python):
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools



readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []

COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    '''
    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l
    '''

q = deque([(1, -1)])
while(q):
    a, ng = q.popleft()
    bs = PT[a]

    c = 1
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        cab = COLOR[(na, nb)]

        if cab == ng:
            continue

        if cab == 0:
            if c == ng:
                c += 1
            clr = c
            COLOR[(na, nb)] = clr
            q.append((b, clr))
            c += 1

print(max(COLOR.values()))

clr = []
for a, b in PATH:
    clr.append(COLOR[(a, b)])

print("\n".join(map(str, clr)))

Solution (Python):
import sys
input = sys.stdin.readline


n = int(input())

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

PREV = {1:0}
Q = [1]
while Q:
    now = Q.pop(0)
    for vertex in GRAPH[now]:
        if vertex == PREV[now]:
            continue
        next = vertex
        PREV[next] = now
        Q.append(next)

COLORS = {(0, 1):0}
Q = [1]
while Q:
    now = Q.pop(0)
    prev = PREV[now]
    a, b = min(now, prev), max(now, prev)
    used = COLORS[(a, b)]
    
    color = 1
    for vertex in GRAPH[now]:
        if vertex == prev:
            continue
        next = vertex
        a, b = min(now, next), max(now, next)
        if color == used:
            color += 1
            COLORS[(a, b)] = color
            color += 1
        else:
            COLORS[(a, b)] = color
            color += 1
        Q.append(next)

print(max(COLORS.values()))
for edge in EDGES:
    print(COLORS[edge])

Solution (Python):
import sys
input = sys.stdin.readline


n = int(input())

GRAPH = {i:[] for i in range(1, n + 1)}
EDGES = []
COLORS = {(0, 1):0}
for _ in range(n - 1):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)
    EDGES.append((a, b))
    COLORS[(a, b)] = 0

PREV = {1:0}
Q = [1]
while Q:
    now = Q.pop(0)
    for vertex in GRAPH[now]:
        if vertex == PREV[now]:
            continue
        next = vertex
        PREV[next] = now
        Q.append(next)

Q = [1]
while Q:
    now = Q.pop(0)
    prev = PREV[now]
    a, b = min(now, prev), max(now, prev)
    used = COLORS[(a, b)]
    
    color = 1
    for vertex in GRAPH[now]:
        if vertex == prev:
            continue
        next = vertex
        a, b = min(now, next), max(now, next)
        if color == used:
            color += 1
            COLORS[(a, b)] = color
            color += 1
        else:
            COLORS[(a, b)] = color
            color += 1
        Q.append(next)

print(max(COLORS.values()))
for edge in EDGES:
    print(COLORS[edge])

Solution (Python):

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    N = INT()
    uv = [LIST() for i in range(N - 1)]

    
    graph = defaultdict(list)

    
    edge = defaultdict(int)

    for u, v in uv:
        graph[u-1].append(v-1)
        graph[v-1].append(u-1)
    
    K = 0
    for v in graph.values():
        
        K = max(K, len(v))
    color = list(range(1, K + 1))
    
    
    
    
    que = deque()
    que.append((0, None))

    
    
    while que:
        i, color_from = que.popleft()
        tmp = -1
        for node in graph[i]:
            str_ = "{},{}".format(i, node)
            if not edge[str_]:
                
                use_color = color[tmp]
                if use_color == color_from:
                    
                    use_color = color[tmp - 1]
                    tmp -= 1
                tmp -= 1

                edge[str_] = use_color
                
                edge["{},{}".format(node, i)] = use_color
                que.append((node, use_color))
    print(K)
    for u, v in uv:
        print(edge["{},{}".format(u-1, v-1)])


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
 
N = int(input())
edge = [[] for i in range(N)]
count = [0] * N
color = {}
egs = []
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    count[a] += 1
    count[b] += 1
    edge[a].append(b)
    edge[b].append(a)
    egs.append(tuple(sorted([a, b])))
 
 
ans = max(count)
c = 1
 
 
 
def dfs(idx, pr):
    c = 1
    col = color[pr]
    for i in edge[idx]:
        if i in pr:
            continue
        if c == col:
            c+=1
        x, y = sorted([i, idx])
        color[(x, y)] = c
        dfs(i, (x, y))
        c+=1
 
color[(-1, -1)] = 0
dfs(0, (-1, -1))
print(ans)
for tpl in egs:
    print(color[tpl])

Solution (Python):
from collections import deque

N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)




dict = {}
'''

def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val
'''
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            key = tuple(sorted([now_node, next_node]))
            if not dict.get(key) is None:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            dict[key] = now_color
            
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val

ans = bfs(0)
print(ans)
for a, b in input_list:
    
    print(dict[tuple(sorted([a,b]))])

Solution (Python):
from collections import*
import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline

n=int(input())
d={}

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    if a not in d:
        d[a]=[]
    if b not in d:
        d[b]=[]
    d[b].append(a)
    d[a].append(b)        
    q.append(tuple(sorted([a,b])))

m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            c+=1
            if c==m+1:
                c=1
            dcolars[tuple(sorted([point,i]))]=c
            BFS(d,i,c)
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])

Solution (Python):
N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(a,b)] = i
    
ans = [-1]*(N-1)

que = [[1,-1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    
    now,parent,parentcolor = que.pop()
    visited[now]=True
    nowcolor = 1
    for i in G[now]:
        
        if i != parent:
            if nowcolor == parentcolor:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            if len(G[i])!=1:
                que.append([i,now, nowcolor-1])
    

print(K)
for i in ans:
    print(i)