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):
from collections import deque

N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
tree = [list() for _ in range(N+1)]
color = [0] * (N-1)

for i, (a, b) in enumerate(ab):
    tree[a].append((b, i))

q = deque([(1, 0)]) 
while q:
    v, pc = q.popleft()
    nc = 1 
    for nv, edge in tree[v]: 
        if nc == pc: 
            nc += 1
        color[edge] = nc 
        q.append((nv, nc))
        nc += 1

print(max(color))
print(*color, sep="\n")

Solution (Python):
from collections import deque

N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
tree = [list() for _ in range(N+1)]
color = [0] * (N-1)

for i, (a, b) in enumerate(ab):
    tree[a].append((b, i))

q = deque([(1, 0)]) 
while q:
    v, pc = q.popleft()
    nc = 0 
    for nv, edge in tree[v]: 
        nc += 1
        if nc == pc: 
            nc += 1
        color[edge] = nc 
        q.append((nv, nc))

print(max(color))
print(*color, sep="\n")

Solution (Python):
def examD():
    N = I()
    AB = [LI() for _ in range(N-1)]
    V = [[] for _ in range(N)]
    for a,b in AB:
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    ans = []
    root = 0
    
    parent = [0] * (N)
    order = []
    stack = [root]
    while stack:
        x = stack.pop()
        order.append(x)
        for y in V[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            stack.append(y)

    
    color = [-1]*(N)

    for i in order:
        NG = color[i]
        cur = 1
        for j in V[i]:
            if j == parent[i]:
                continue
            if cur==NG:
                cur +=1
            color[j] = cur
            cur +=1

    append = ans.append
    for a,b in AB:
        if parent[a-1]==b-1:
            
            append(color[a-1])
        else:
            append(color[b-1])
    print(max(ans))
    for v in ans:
        print(v)

def examE():
    N, K = LI()

    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

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


def main():
    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))
        G[b-1].append((a-1, i))

    V = [[-1, -1] for _ in range(N)]  
    ans = [-1]*(N-1)
    stack = [0]  
    while stack:
        i = stack.pop()
        color = 0
        for c, ei in G[i]:
            if c == V[i][0]:
                continue
            V[c][0] = i
            color += 1
            if color == V[i][1]:
                color += 1
            V[c][1] = ans[ei] = color
            stack.append(c)
    print(max(ans))
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

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


def main():
    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))
        G[b-1].append((a-1, i))

    V = [[-1, -1] for _ in range(N)]  
    ans = [-1]*(N-1)
    import collections
    Q = collections.deque()
    Q.append(0)
    while Q:
        i = Q.popleft()
        color = 0
        for c, ei in G[i]:
            if c == V[i][0]:
                continue
            V[c][0] = i
            color += 1
            if color == V[i][1]:
                color += 1
            V[c][1] = ans[ei] = color
            Q.append(c)
    print(max(ans))
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N = int(input())
edge = [set() for _ in range(N)]
ab = []
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    ab.append((a,b))
    edge[a].add(i)
    edge[b].add(i)

K = 0
ans = [0]*(N-1)
pool = deque([(0,0)])
while pool:
    node, prev = pool.popleft()
    c = 0
    for i in edge[node]:
        c += 1
        if c == prev:
            c += 1
        a, b = ab[i]
        if node == a:
            x = b
        else:
            x = a
        edge[x].remove(i)
        ans[i] = c
        pool.append((x,c))
    if c >= K:
        K = c

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

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N = int(input())
edge = [set() for _ in range(N)]
ab = []
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    ab.append((a,b))
    edge[a].add(i)
    edge[b].add(i)

K = 0
ans = [0]*(N-1)
pool = [(0,0)]
while pool:
    node, prev = pool.pop()
    c = 0
    for i in edge[node]:
        c += 1
        if c == prev:
            c += 1
        a, b = ab[i]
        if node == a:
            x = b
        else:
            x = a
        edge[x].remove(i)
        ans[i] = c
        pool.append((x,c))
    if c >= K:
        K = c

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
ans = {}
queue = deque([])
e = []
for l in range(N-1):
    temp = list(map(int,input().split()))
    temp[0] -= 1
    temp[1] -= 1
    e.append(tuple(temp))
    ans[(temp[0],temp[1])] = 0
    ans[(temp[1],temp[0])] = 0
    G[temp[0]].append(temp[1])
    G[temp[1]].append(temp[0])
    if l == 0:
        queue.append(temp[0])

nuc = [[0] for _ in range(N)]

auc = []

def bfs(x):
    k = 1
    for i in G[x]:
        if ans[(x,i)] ==0:
            queue.append(i)
            flag = 1
            while flag:
                if k not in nuc[x]:         
                    ans[(x,i)] = k
                    ans[(i,x)] = k
                    nuc[x].append(k)
                    nuc[i].append(k)
                    if k not in auc:
                        auc.append(k)
                    flag = 0
                else:
                    k += 1
                
while len(queue) > 0:
    next_ = queue.popleft()
    bfs(next_)
print(len(auc))
for m in e:
    print(ans[m])

Solution (Python):
"""
DFS
"""

import sys
sys.setrecursionlimit(10**7)


class Edge:
    def __init__(self, _to, _id):
        self.to = _to
        self.id = _id


def dfs(vertex, parent_color=-1, parent_vertex=-1):
    color = 1
    for g in graph[vertex]:
        u = g.to
        ei = g.id
        if u == parent_vertex:
            continue
        if color == parent_color:
            color += 1
        ans[ei] = color
        color += 1
        dfs(u, ans[ei], vertex)


N = int(input())
graph = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(Edge(b, i))
    graph[b].append(Edge(a, i))

dfs(0)


mx = max([len(g) for g in graph])
print(mx)

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

Solution (Python):
"""
DFS
"""

import sys
sys.setrecursionlimit(10**7)


class Edge:
    def __init__(self, _to, _id):
        self.to = _to
        self.id = _id


def dfs(vertex, parent_color=-1, parent_vertex=-1):
    color = 1
    for g in graph[vertex]:
        u = g.to
        ei = g.id
        if u == parent_vertex:
            continue
        if color == parent_color:
            color += 1
        ans[ei] = color
        color += 1
        dfs(u, ans[ei], vertex)


N = int(input())
graph = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(Edge(b, i))
    graph[b].append(Edge(a, i))

dfs(0)


mx = max([len(g) for g in graph])
print(mx)

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

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k

parent = [_max_node] * (n)
order = []
stack = [_max_node]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

colors = [-1 for i in range(n)]
for i in order:
    c = 1
    for _next in graph[i]:
        if _next == parent[i]:
            continue
        if c == colors[i]:
            c += 1
        colors[_next] = c
        c += 1
print(_max)
for a, b in ls:
    if parent[a] == b:
        print(colors[a])
    else:
        print(colors[b])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
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: continue 
    if col == p_col: col += 1 
    ans[idx] = col
    dfs(u, v, col)
    col += 1
dfs()
print("\n".join(map(str, ans)))

Solution (Python):





from collections import deque

N=int(input())
d={} 
out=[set() for v in range(N+1)];out[0]=None 
for i in range(1,N): 
    u,v=map(int,input().split())
    out[u].add(v);out[v].add(u)
    u,v=min(u,v),max(u,v);d[(u,v)]=i
K=max([len(out[v]) for v in range(1,N+1)])
    
vcol=[0 for v in range(N+1)];vcol[0]=None
ecol=[0 for e in range(N)];ecol[0]=None

vr=[False for v in range(N+1)];vr[0]=None

q=deque()
q.append(1);vr[1]=True
vcol[1]=1 
while q:
    u=q.popleft() 
    i=1 
    for v in out[u]:
        if not vr[v]:
            col=(vcol[u]+i-1)%K+1
            vcol[v]=ecol[d[(min(u,v),max(u,v))]]=col
            vr[v]=True
            q.append(v)
            i+=1

print(K)
for i in range(1,N):
    print(ecol[i])

Solution (Python):
def solve():
  from collections import deque
  from sys import stdin
  
  f_i = stdin
  N = int(f_i.readline())
  
  e_color = {}
  edge = []
  adj = [[] for i in range(N)]
  for i in range(N - 1):
    a, b = map(int, f_i.readline().split())
    a -= 1
    b -= 1
    e = frozenset((a, b))
    e_color[e] = None
    edge.append(e)
    adj[a].append(b)
    adj[b].append(a)
  
  color_to_parent = [0] * N 
  q = deque([0])
  notVisited = [True] * N
  notVisited[0] = False
  
  
  while q:
    v = q.popleft()
    color = 1
    for child in adj[v]:
      if notVisited[child]:
        if color == color_to_parent[v]:
          color += 1
        color_to_parent[child] = color
        e_color[frozenset((v, child))] = color
        color += 1
        notVisited[child] = False
        q.append(child)
  
  print(len(max(adj, key=len)))
  g = (e_color[e] for e in edge)
  print('\n'.join(map(str, g)))

solve()

Solution (Python):
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    chain_inputs = list(map(string_to_int, inputs))

    CHAIN_N = len(inputs)
    NODE_N = CHAIN_N + 1

    
    node_relation = {i: {} for i in range(NODE_N)}
    
    chain_color = {i: None for i in range(CHAIN_N)}
    
    node_has_color = {i: set() for i in range(NODE_N)}
    passed = set()

    for i, c in enumerate(chain_inputs):
        node = c[0] - 1
        target = c[1] - 1
        node_relation[node][target] = i
        node_relation[target][node] = i

    bfs_queue = collections.deque([0])

    max_branch = 0
    while len(bfs_queue) > 0:
        node = bfs_queue.pop()
        leafs = node_relation[node]
        if max_branch < len(leafs):
            max_branch = len(leafs)

        color = 1
        for leaf, index in leafs.items():
            if leaf in passed:
                continue
            
            
            while color in node_has_color[node]:
                color += 1
            node_has_color[node].add(color)
            node_has_color[leaf].add(color)
            chain_color[index] = color

            bfs_queue.appendleft(leaf)
            passed.add(node)

    ret = [max_branch]
    for i in range(CHAIN_N):
        ret.append(chain_color[i])
    return ret


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(inputs(N-1))
    for r in ret:
        print(r)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m==1:
        mxd=m
        mxi=i
        


v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                if v[c]==col and c!=x:col+=1
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                dc[(i,c)]=col

                col+=1
    return

bfs(mxi)
print(max(v)+1)
for i,j in c:
    print(dc[(i,j)]+1)

Solution (Python):
from collections import deque

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

k = 0
d = dict()
cs = [0] * N
used = [False] * N

que = deque([])
used[0] = 1
que.appendleft(0)
while len(que) > 0:
    v = que.pop()
    k = max(k, len(g[v]))
    cur = 1
    for u in g[v]:
        if used[u]:
            continue
        if cur == cs[v]:
            cur += 1
        cs[u] = d[(u, v)] = d[(v, u)] = cur
        cur += 1
        used[u] = True
        que.appendleft(u)
print(k)
for p in vp:
    print(d[p])

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time

def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m==1:
        mxd=m
        mxi=i
        


v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                if v[c]==col and c!=x:col+=1
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                dc[(i,c)]=col

                col+=1
    return

bfs(mxi)
print(max(v)+1)
for i,j in c:
    print(dc[(i,j)]+1)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = [i, -1]


stack = [(0, -1)]
mx = 0
ans = [0] * (N-1)
while stack:
    u, prev = stack.pop()
    color = 0
    
    for v in nodes[u]:
        if v == prev:
            continue
        stack.append((v, u))
        color += 1
        a, b = min(u, prev), max(u, prev)
        
        if a != -1 and color == edges[(a, b)][1]:
            color += 1
        a, b = min(u, v), max(u, v)
        edges[(a, b)][1] = color
        i = edges[(a, b)][0]
        ans[i] = str(color)
    
    mx = max(mx, color)

print(mx)
print('\n'.join(ans))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = [i, -1]


stack = [(0, -1)]
mx = 0
ans = [0] * (N-1)
while stack:
    u, prev = stack.pop()
    color = 0
    
    for v in nodes[u]:
        if v == prev:
            continue
        stack.append((v, u))
        color += 1
        a, b = min(u, prev), max(u, prev)
        
        if a != -1 and color == edges[(a, b)][1]:
            color += 1
        a, b = min(u, v), max(u, v)
        edges[(a, b)][1] = color
        i = edges[(a, b)][0]
        ans[i] = str(color)
    
    mx = max(mx, color)

print(mx)
print('\n'.join(ans))

Solution (Python):
N = int(input())
num = [[]for _ in range(N)]
for i in (range(N-1)):
  a, b = map(int, input().split())
  num[a-1].append([i, b-1])
answer = [0] * (N-1)
color = [-1] * (N)
max_num = 0
for i in range(len(num)):
  if max_num <= len(num[i]):
    if i == 0:
      max_num = len(num[i])
    else:
      max_num = len(num[i]) + 1
  c = 1
  for j in range(len(num[i])):
    if c == color[i]:
      c += 1
    answer[num[i][j][0]] = c
    color[num[i][j][1]] = c
    c += 1
print(max_num)
for i in answer:
  print(i)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
n = int(input())
t = [[] for _ in range(n)]
e = []
for i in range(n - 1):
    a, b = map(int, input().split())
    t[a - 1].append([i, b - 1])
    t[b - 1].append([i, a - 1])
    e.append([a - 1, b - 1])
colors = [len(t[i]) for i in range(n)]
res1 = max(colors)
print(res1)

res = [0 for _ in range(n - 1)]
f = [False for _ in range(n)]


def dfs2(d, c):
    f[d] = True
    nc = 1
    for g in t[d]:
        if not f[g[1]]:
            if c == nc:
                nc += 1
            res[g[0]] = nc
            dfs2(g[1], nc)
            nc += 1

dfs2(0, res1+10)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
n = int(input())
t = [[] for _ in range(n)]
e = []
for i in range(n - 1):
    a, b = map(int, input().split())
    t[a - 1].append([i, b - 1])
    t[b - 1].append([i, a - 1])
    e.append([a - 1, b - 1])
colors = [len(t[i]) for i in range(n)]
res1 = max(colors)
print(res1)

res = [0 for _ in range(n - 1)]
f = [False for _ in range(n)]


def dfs2(d, c):
    f[d] = True
    nc = 1
    for j in range(len(t[d])):
        if not f[t[d][j][1]]:
            if c == nc:
                nc += 1
            res[t[d][j][0]] = nc
            dfs2(t[d][j][1], nc)
            nc += 1


dfs2(0, 1000000)

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

Solution (Python):

n=int(input())
ab=[]

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



p=[-1 for i in range(n+1)]


edge={}


used=[0 for i in range(n+1)]


max_n=0
for i in range(n+1):
    tmp=len(G[i])
    if tmp>max_n:
        max_n=tmp
        
        top=i


queue=[]
queue.append(top)


while len(queue)>0:
    
    num=queue.pop(0)
    used[num]=1
    color=1
    
    
    for i in range(len(G[num])):
        
        if used[G[num][i]]==0:
            if p[num]==color:
                
                
                color+=1
                
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                
                p[G[num][i]]=color
                
                queue.append(G[num][i])
            else:
                
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            color+=1
            

print(max_n)

for i in range(n-1):
    print(edge["{},{}".format(ab[i][0],ab[i][1])])

Solution (Python):
from collections import deque
n=int(input())
K=0
g=[[] for _ in range(n+1)]
for  i in range(n-1):
    a,b=map(int,input().split())
    g[a].append([b,i])
    g[b].append([a,i])
for i in range(n):
    K=max(len(g[i]),K)
print(K)
ans=[0]*(n-1)
q=deque([(-1,1)])
while q:
    s,p=q.popleft()
    C = (c for c in range(1, K + 1) if c != s)
    for i,j in g[p]:
        g[i].remove([p,j])       
        sa=next(C)
        ans[j]=sa
        q.append((sa,i) )
for i in ans:
    print(i)

Solution (Python):

from collections import deque

N = int(input().split()[0])


node_dict = {i + 1: dict(parent=None, children=[]) for i in range(N)}

a_list = []
b_list = []
edge_dict = {}
edge_list = []


for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    edge_list.append((a, b))
    edge_dict[(a, b)] = dict(a=a, b=b, color=None)
    a_list.append(a)
    b_list.append(b)

    node_dict[a]["children"].append(b)
    node_dict[b]["parent"] = a


root = list(set(a_list) - set(b_list))[0]

max_color_degree = -float("inf")


for k, v in node_dict.items():
    d = len(v["children"])
    
    d = d + 1 if v["parent"] else d
    max_color_degree = max(max_color_degree, d)

COLOR_LIST = list(range(max_color_degree))


def color_edge(parent):
    next_node_list = node_dict[parent]["children"]
    parent_parent = node_dict[parent]["parent"]
    parent_edge_color = edge_dict[(parent_parent, parent)]["color"]
    ng_color = parent_edge_color

    
    color_index = 0
    for child in next_node_list:
        color = COLOR_LIST[color_index]
        if color == ng_color:
            color_index += 1
            color = COLOR_LIST[color_index]

        edge_dict[(parent, child)]["color"] = color
        color_index += 1
    return


parent = root
next_node_list = node_dict[root]["children"]
next_next_node_list = []


color_index = 0
for node in next_node_list:
    color = COLOR_LIST[color_index]
    color_index += 1
    edge_dict[(parent, node)]["color"] = color


while next_node_list:
    next_parent_list = []
    
    for node in next_node_list:
        color_edge(node)
        next_parent_list += node_dict[node]["children"]
    next_node_list = next_parent_list

color_list_str = ""
for edge in edge_list:
    a, b = edge
    color_list_str += str(edge_dict[(a, b)]["color"] + 1) + "\n"

print(max_color_degree)
print(color_list_str)

Solution (Python):
n=int(input())
ab=[]
p=[-1 for i in range(n+1)]
edge={}
G=[[] for i in range(n+1)]
used=[0 for i in range(n+1)]
for i in range(n-1):
    ab.append(list(map(int,input().split())))
    G[ab[i][0]].append(ab[i][1])
    G[ab[i][1]].append(ab[i][0])

max_n=0

for i in range(n+1):
    tmp=len(G[i])
    if tmp>max_n:
        max_n=tmp
        top=i

queue=[]
queue.append(top)

while len(queue)>0:
    num=queue.pop(0)
    used[num]=1
    color=1
    for i in range(len(G[num])):
        if used[G[num][i]]==0:
            if p[num]==color:
                color+=1
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            else:
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            color+=1

print(max_n)
for i in range(n-1):

    print(edge["{},{}".format(ab[i][0],ab[i][1])])

Solution (Python):

from collections import deque

N = int(input().split()[0])


node_dict = {i + 1: dict(parent=None, children=[]) for i in range(N)}

a_list = []
b_list = []
edge_dict = {}
edge_list = []


for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    edge_list.append((a, b))
    edge_dict[(a, b)] = dict(a=a, b=b, color=None)
    a_list.append(a)
    b_list.append(b)

    node_dict[a]["children"].append(b)
    node_dict[b]["parent"] = a


root = list(set(a_list) - set(b_list))[0]

max_color_degree = -float("inf")


for k, v in node_dict.items():
    d = len(v["children"])
    
    d = d + 1 if v["parent"] else d
    max_color_degree = max(max_color_degree, d)

COLOR_LIST = list(range(max_color_degree))


def color_edge(parent):
    next_node_list = node_dict[parent]["children"]
    parent_parent = node_dict[parent]["parent"]
    parent_edge_color = edge_dict[(parent_parent, parent)]["color"]
    ng_color = parent_edge_color

    
    color_index = 0
    for child in next_node_list:
        color = COLOR_LIST[color_index]
        if color == ng_color:
            color_index += 1
            color = COLOR_LIST[color_index]

        edge_dict[(parent, child)]["color"] = color
        color_index += 1
    return


parent = root
next_node_list = node_dict[root]["children"]
next_next_node_list = []


color_index = 0
for node in next_node_list:
    color = COLOR_LIST[color_index]
    color_index += 1
    edge_dict[(parent, node)]["color"] = color


while next_node_list:
    next_parent_list = []
    
    for node in next_node_list:
        color_edge(node)
        next_parent_list += node_dict[node]["children"]
    
    next_node_list = next_parent_list

color_list_str = ""
for edge in edge_list:
    a, b = edge
    color_list_str += str(edge_dict[(a, b)]["color"] + 1) + "\n"

print(max_color_degree)
print(color_list_str)

Solution (Python):
from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.adj = []
        self.pec = 0

n = int(input())
ab = []
nodes = [None] * n
cntMap = {}

def addCount(v1):
    if v1 not in cntMap:
        cntMap[v1] = 1
    else:
        cntMap[v1] += 1

for i in range(n-1):
    v1, v2 = map(int, input().split())
    addCount(v1)
    addCount(v2)
    ab.append([v1, v2])
    nodeAidx = v1-1
    nodeBidx = v2-1
    nodeA = None
    nodeB = None
    if nodes[nodeAidx] is None:
        nodeA = Node(v1)
        nodes[nodeAidx] = nodeA
    else:
        nodeA = nodes[nodeAidx]
    if nodes[nodeBidx] is None:
        nodeB = Node(v2)
        nodes[nodeBidx] = nodeB
    else:
        nodeB = nodes[nodeBidx]
    nodeA.adj.append(nodeB)



root = nodes[0]
nodes[1].pec = 1
q = deque()
q.append(root)

temp = list(cntMap.values())
temp.sort()
maxV = temp[-1]
used = set()
edgeMap = {}

print(maxV)

while q:
    used.clear()
    node = q.popleft()
    pec = node.pec
    used.add(pec)
    prev = 0

    for i in range(len(node.adj)):
        a = node.adj[i]
        for j in range(prev+1, maxV+1):
            if j not in used:
                a.pec = j
                used.add(j)
                prev = j
                break

        edgeMap[(node.val, a.val)] = a.pec
        q.append(a)

for i in range(n-1):
    key = (ab[i][0], ab[i][1])
    print(edgeMap[key])

Solution (Python):
from collections import deque
 
N, *AB = map(int, open(0).read().split())
 
E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))
K = max(len(e) for e in E)
A = [0] * (N - 1)
Q = deque([(-1, 1)])
while Q:
    p, v = Q.popleft()
    C = (c for c in range(1, K + 1) if c != p)
    for u, i in E[v]:
        E[u].remove((v, i))
        c = next(C)
        Q.append((c, u))
        A[i] = c
 
print(K)
for a in A:
    print(a)

Solution (Python):
from collections import defaultdict, deque

n = int(input())

tree = defaultdict(list)

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

I = dict()
que = deque([1])
color = [None]*(n+1)
color[1] = 0
max_val = 0
used = {1, }
while que:
	u= que.popleft()
	max_val = max(max_val, len(tree[u]))
	next_color = 1
	for v in tree[u]:
		if v in used: continue
		if color[u] == next_color:
			next_color += 1
		color[v] = I[(u, v)] = I[(v, u)] = next_color
		next_color += 1
		que.append(v)
		used.add(v)
print(max_val)
for edge in edges:
	print(I[edge])