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
import sys
input = sys.stdin.readline
    
def bfs(v, N, G, E):
    visited = [0]*N
    queue = deque()
    K = -1
    node2color = [-1 for _ in range(N)]
    queue.append(v)
    visited[v] = 1
    while queue:
        q = queue.popleft()
        color = 0
        for nex in G[q]:
            if visited[nex]:
                continue
            visited[nex] = 1
            color += 1
            if color == node2color[q]:
                color += 1
            
            node2color[nex] = color
            E[(min(q, nex), max(q, nex))] = color
            queue.append(nex)
        K = max(K, color)
    return K

def main():
    N = int(input())
    G = [deque() for _ in range(N)]
    E = dict() 
    for i in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        G[a].append(b)
        G[b].append(a)
        E[(a, b)] = 0
    K = bfs(0, N, G, E)
    
    print(K)
    for value in E.values():
        print(value)
main()

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

k = max([len(i) for i in g])
print(k)

reach = [False]*n
c = dict()
from collections import deque
q = deque([[0,-1]])

while q:
    cur,col = q.popleft()
    reach[cur] = True
    for next_i in g[cur]:
        if not reach[next_i]:
            col = (col+1)%k
            a,b = sorted([cur,next_i])
            c[(a,b)] = col
            q.append([next_i,col])

for a,b in ab:
    print(c[(a,b)]+1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for i,(a,b) in enumerate(AB):
    a,b = a-1,b-1
    es[a].append((b,i))
    es[b].append((a,i))

ans = [None] * (N-1)

def dfs(v,p=-1,c=-1):
    nc = 1
    for to,e in es[v]:
        if to==p: continue
        if nc==c: nc += 1
        ans[e] = nc
        dfs(to,v,nc)
        nc += 1
dfs(0)

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

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



def main():
    n = int(input().strip())
    edges = [[int(i) for i in input().strip().split()] for _ in range(n - 1)]
    g = defaultdict(list)
    for a, b in edges:
        g[a].append(b)

    
    que = deque([1])
    
    
    colors = [0] * (n + 1)

    
    while que:
        parent = que.popleft()
        color = 0
        for child in g[parent]:
            color += 1
            if color == colors[parent]:
                color += 1
            colors[child] = color
            que.append(child)

    print(max(colors))

    for a, b in edges:
        print(colors[b])
    return


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

N = int(input())
G = [[] for _ in range(N + 1)]

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


dq = deque([1])


edge_color = {}

used_color = [0 for _ in range(N + 1)]

visited = [False for _ in range(N + 1)]
visited[1] = True


while dq:
    
    prt = dq.popleft()
    color = 0

    
    for cld in G[prt]:
        if visited[cld] == False:
            
            visited[cld] = True
            
            color += 1
            
            if color == used_color[prt]:
                color += 1

            

            
            used_color[cld] = color
            
            n1 = min(cld, prt)
            n2 = max(cld, prt)
            edge_color[(n1, n2)] = color
            
            dq.append(cld)


print(max(edge_color.values()))

for edge in edge_order:
    print(edge_color[edge])

Solution (Python):
from collections import deque

N = int(input())

G = [[] for _ in range(N + 1)]

G_order = []

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


que = deque([0])



colors = [0] * N

while que:
    
    
    prt = que.popleft()
    color = 0

    
    for cld in G[prt]:
        color += 1
        
        if color == colors[prt]:
            color += 1
        colors[cld] = color
        que.append(cld)





print(max(colors))


for i in G_order:
    print(colors[i])

Solution (Python):
from collections import deque

n = int(input())
tree = [[] for _ in range(n)]
color = dict()
edge = [(0, 0)] * (n-1)
for i in range(n-1):
    a, b = map(lambda x : int(x) - 1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    edge[i] = (a, b)
color_n = max(map(len, tree))

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

visited = set()
while q:
    i, prev_c = q.popleft()
    visited.add(i)
    c = prev_c
    for x in tree[i]:
        if not x in visited:
            c = (c + 1) % color_n
            p = (i, x) if i < x else (x, i)
            color[p] = c
            q.append((x, c))
print(color_n)
for e in edge:
    print(color[e] + 1)

Solution (Python):
from collections import deque

n = int(input())
tree = [[] for _ in range(n)]
color = dict()
edge = [(0, 0)] * (n-1)
for i in range(n-1):
    a, b = map(lambda x : int(x) - 1, input().split())
    tree[a].append(b)
    tree[b].append(a)
    edge[i] = (a, b)
color_n = max(map(len, tree))

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

visited = set()
while q:
    i, prev_c = q.popleft()
    visited.add(i)
    c = 0
    for x in tree[i]:
        if not x in visited:
            if c == prev_c:
                c = (c + 1) % color_n
            p = (i, x) if i < x else (x, i)
            color[p] = c
            q.append((x, c))
            c = (c + 1) % color_n

print(color_n)
for e in edge:
    print(color[e] + 1)

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    n = INT()
    Q = [tuple(MAP1()) for _ in range(n-1)]

    deg = [0]*n
    adj = [[] for _ in range(n)]
    color = dict()

    for a, b in Q:
        deg[a] += 1
        deg[b] += 1
        adj[a].append(b)
        adj[b].append(a)

    def dfs(s, p):
        nouse = -1
        if p > -1:
            nouse = color[(min(s,p),max(s,p))]
        c = 1
        for t in adj[s]:
            if t == p:
                continue
            if c == nouse:
                c += 1
            color[(min(s,t),max(s,t))] = c
            dfs(t,s)
            c += 1
    
    dfs(1,-1)
    
    print(max(deg))
    for a, b in Q:
        print(color[(a, b)])

if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
n = int(input())
edges_ls = [[0,0] for _ in range(n-1)]
edges_d = {}
ver_ls = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges_d[(a,b)] = i
    edges_d[(b,a)] = i
    edges_ls[i] = [a,b]
    ver_ls[a].append(b)
    ver_ls[b].append(a)
n_color = 0
for ver in ver_ls:
    n_color = max(n_color,len(ver))
def next_color(color):
    return (color+1)%n_color

edge_color = [0] * (n-1)
q = deque()
color_now = 0
for ver in ver_ls[0]:
    q.append([0,ver,color_now])
    edge_color[edges_d[(0,ver)]] = color_now
    color_now = next_color(color_now)
done_ls = [0] * n
done_ls[0] = 1

while q:
    From, to, color_now = q.popleft()
    
    for ver in ver_ls[to]:
        if not done_ls[ver]:
            q.append([to,ver,next_color(color_now)])
            edge_color[edges_d[(to,ver)]] = next_color(color_now)
            color_now = next_color(color_now)
    done_ls[to] = 1

print(n_color)
for color in edge_color:
    print(color+1)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
edges = [[] for _ in range(n)]
ab = [[i] + LI() for i in range(n-1)]
cnt = [0] * n
for i, a, b in ab:
    edges[a-1].append((i, b-1))
    edges[b-1].append((i, a-1))
    cnt[a-1] += 1
    cnt[b-1] += 1

k = max(cnt)
print(k)
que = deque([(0, -1, 0)])
edges_color = [None] * (n-1)
while que:
    v, p, col = que.popleft()
    cnt = 1
    for i, u in edges[v]:
        if edges_color[i] != None:
            continue
        if u == p:
            continue
        if cnt != col:
            edges_color[i] = cnt
        else:
            edges_color[i] = cnt + 1
            cnt += 1
        que.append((u, v, cnt))
        cnt += 1
for c in edges_color:
    print(c)

Solution (Python):
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


n=int(input())
edge=[[] for i in range(n+1)]
par=[0]*(n+1)
par[1]=-1
col=[0]*(n-1)
for i in range(n-1):
    a,b=mp()
    edge[a].append([a,b,i])
    edge[b].append([b,a,i])


que=deque([edge[1]])
while len(que):
    k=1
    q=que.popleft()
    for x,y,i in q:
        if col[i]==0:
            if k==par[x]:
                k+=1
            col[i]=k
            par[y]=k
            k+=1
            que.append(edge[y])
print(max(col))
for i in range(n-1):
    print(col[i])

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

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

Col = 0
for n in range(N):
    Col = max(Col, len(graph[n]))

Color = dict()
checked = [-1]*N
q = [0]
checked[0] = Col+1
while q:
    qq = []
    for p in q:
        c = checked[p]
        t = 0
        for np in graph[p]:
            if checked[np] == -1:
                if t == c:
                    t += 1
                checked[np] = t
                Color[(p, np)] = t
                Color[(np, p)] = t
                t += 1
                qq.append(np)
    q = qq

print(Col)
for a, b in Edges:
    print(Color[(a, b)]+1)

Solution (Python):
from collections import deque

n=int(input())
g=[[] for i in range(n)]
b=[0]*(n-1)
for i in range(n-1):
    ai,bi=map(int,input().split())
    g[ai-1].append(bi-1)
    g[bi-1].append(ai-1)
    b[i]=bi-1
    






q=deque([0])

stack=[0]
parent=[-1]*n
pc=[-1]*n
parent[0]=0
dist=[-1]*n
dist[0]=0
while q:
    state = q.popleft()
    ic=0
    for v in g[state]:
        if parent[v] !=-1:
            continue
        else:
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
            ic+=1
            if ic==pc[state]:
                ic+=1
            pc[v]=ic

k=max(pc)
print(k)
for i in range(n-1):
    print(pc[b[i]])

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    ans = [0]*(n-1)
    for i in range(n-1):
        u, v = mi()
        u -= 1
        v -= 1
        edge[u].append((v, i))
        edge[v].append((u, i))
    k = 0
    q = deque([0])
    visited = [False]*n
    visited[0] = True
    c = [0]*n
    while q:
        v = q.popleft()
        cur = 1
        k = max(k, len(edge[v]))
        for nv, idx in edge[v]:
            if visited[nv]:
                continue
            if cur == c[v]:
                cur += 1
            visited[nv] = True
            c[nv] = cur
            ans[idx] = cur
            cur += 1
            q.append(nv)
    print(k)
    print(*ans, sep='\n')





if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
deg = [0 for _ in range(N)]
edges = [[] for _ in range(N - 1)]
a = []
for i in range(N - 1):
    in1, in2 = map(int, input().split())
    a.append([in1, in2, i])
a = sorted(a, key = lambda x: x[0])
for i in range(N - 1):
    edges[i] = [a[i][0] - 1, a[i][1] - 1, a[i][2]]
    deg[a[i][0] - 1] += 1
    deg[a[i][1] - 1] += 1
deg_max = max(deg)
print(deg_max)

co = [0 for _ in range(N)]
ans = [0 for _ in range(N - 1)]
for i in range(N - 1):
    a = edges[i][0]
    b = edges[i][1]
    temp = 1 + (co[a] % deg_max)
    co[a] = temp
    co[b] = temp
    ans[edges[i][2]] = temp
for i in range(N - 1):  print(ans[i])

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
n = int(input())
ab = [list(map(int,input().split()))for _ in range(n-1)]

graph = [[] for _ in range(n+1)]
ans = [0]*(n-1)
for i in range(n-1):
    graph[ab[i][0]].append((ab[i][1],i))
    graph[ab[i][1]].append((ab[i][0],i))

visit = [False]*(n+1)
def dfs(p,c):
    color = 1
    visit[p] = True
    for n,i in graph[p]:
        if visit[n] == False:
            if color == c:
                color += 1
            ans[i] = color
            dfs(n,color)
            color += 1

dfs(1,0)
print(max(ans))
for t in ans:
    print(t)

Solution (Python):
from collections import deque
n=int(input())
tree=[[] for _ in range(n+1)]
for i in range(1,n):
  a,b=map(int,input().split())
  tree[a].append([b,i])
  tree[b].append([a,i])
queue=deque([[1,0]])
ans=[0]*(n+1)
ans[1]=1
visited=[0]*(n+1)

while queue:
  v,c=queue.popleft()
  color=1
  for nv,i in tree[v]:
    if c==color:
      color+=1
    if visited[i]==1:
      continue
    visited[i]=1
    queue.append([nv,color])
    ans[i]=color
    color+=1
print(max(ans))
for i in range(1,n):
  print(ans[i])

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

n = int(input())
edge = [[] for _ in [0]*n]
for i in range(~-n):
    a, b = map(int, input().split())
    a -= 1;b -= 1
    edge[a] += [[b, i]]
ans = [0] * ~-n

def dfs(now, color):
    count = 1
    for to, i in edge[now]:
        
        if count == color:
            count += 1
        ans[i] = count
        dfs(to, count)
        count += 1


dfs(0, 0)

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

Solution (Python):
import sys
from collections import deque
N = int(input())
E = [tuple(map(lambda x: int(x) - 1, sys.stdin.readline().split())) for _ in range(N - 1)]
G = [[] for _ in range(N)]
for a, b in E:
    G[a].append(b)

colornum = len(G[0])
colors = [{} for _ in range(N)]
todo = deque()
for i, p in enumerate(G[0]):
    colors[0][p] = i
    todo.append((0, p))

while todo:
    pp, p = todo.popleft()
    colornum = max(colornum, len(G[p]) + 1)
    c = colors[pp][p]
    for np in G[p]:
        c = (c + 1) % colornum
        colors[p][np] = c
        todo.append((p, np))

print(colornum)
for a, b in E:
    print(colors[a][b] + 1)

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    G = [[] for _ in range(N)]
    E = []
    _E = set()
    for i in range(N-1):
        a,b=mi()
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        E.append((a-1,b-1))
        _E.add((a-1,b-1))
    
    leaf = 0
    for i in range(N):
        g = G[i]
        if len(g) == 1:
            leaf = i

    stack = deque([(leaf,1,None)])
    seen = set()
    path = {x:0 for x in E}
    K = 0

    def save(edge,color):
        if edge == None: return

        a,b = edge
        if (a,b) in _E:
            path[(a,b)] = color
        else:
            path[(b,a)] = color


    while stack:
        current,color,edge = stack.popleft()
        seen.add(current)
        save(edge,color)
        K = max(K,color)
        

        i = 1
        for next in G[current]:
            if next in seen: continue
            if color == i:
                i += 1
            
            stack.append((next,i,(current,next)))
            i += 1
    
    if N == 2:
        print(1)
        print(1)
        exit()


    print(K)
    for i in range(N-1):
        a,b = E[i]
        print(path[(a,b)],sep="")







if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n = int(input())
k = 0
data = [[] for _ in range(n)]
ans_index = []

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

q = deque([0])
color = [0] * n
while q:
    cur = q.popleft()
    c = 1
    for x in data[cur]:
        if c == color[cur]:
            c += 1
    
        color[x] = c
        c += 1
        q.append(x)

print(max(color))
for i in ans_index:
    print(color[i])

Solution (Python):
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)


input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  
    fac = [0] * SIZE  
    finv = [0] * SIZE  
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    
    
    
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    
    return X.flatten().tolist()[0]

class TwoDimGrid:
    
    def __init__(self, h, w, wall="
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        
        
        
        
        


def soinsu(n):
    ret = defaultdict(int)
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while True:
                if n % i == 0:
                    ret[i] += 1
                    n //= i
                else:
                    break

    if not ret:
        return {n: 1}
    return ret


def solve():
    n = getN()
    graph = [[] for i in range(n)]
    ji = [0 for i in range(n)]
    hen = [0 for i in range(n-1)]
    used = [dict() for i in range(n)]
    for i in range(n - 1):
        a, b = getZList()
        graph[a].append([b, i])
        graph[b].append([a, i])
        ji[a] += 1
        ji[b] += 1
    mji = max(ji)
    mid = ji.index(mji)
    
    d = deque()
    d.append(mid)
    while(d):
        
        
        cur = d.pop()
        iro = 1
        for nc, np in graph[cur]:
            if hen[np] != 0:
                continue
            
            while True:
                if iro not in used[cur]:
                    hen[np] = iro
                    d.append(nc)
                    used[nc][iro] = 1
                    iro += 1
                    break
                iro += 1


    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    print(mji)
    print(*hen, sep="\n")



def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = LI_()
        G[a].append((b, i))
        G[b].append((a, i))

    ans = [0] * (N - 1)
    visited = [False] * N

    def dfs(c, color_p):
        visited[c] = True
        color = 0
        for n, i in G[c]:
            if not visited[n]:
                if color == color_p:
                    color += 1
                ans[i] = color
                dfs(n, color)
                color += 1

    dfs(0, -1)

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

if __name__ == '__main__':
    resolve()

Solution (Python):
from collections import deque
n=int(input())
ab=[[] for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    ab[a].append([b,i])
que=deque()
que.append(1)
visited=[0]*(n)
ans=[0]*(n-1)
while que:
    x=que.popleft()
    k=1
    for j in ab[x]:
        if visited[x-1]!=k:
            ans[j[1]]+=k
            visited[j[0]-1]+=k
            k+=1
            que.append(j[0])
        else:
            ans[j[1]]+=(k+1)
            visited[j[0]-1]+=(k+1)
            k+=2
            que.append(j[0])
print(max(ans))
for l in ans:
    print(l)

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

n = int(input())

ab = []
adj = [[] * (n+1) for _ in range(n+1)]

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

m = [0] * (n+1)
for a, b in ab:
    m[a] += 1
    m[b] += 1

k = max(m)
print(k)

visited = [False] * (n+1)
label = [(0, 0)] * (n+1)

j = m.index(k)

q = deque([j])
visited[j] = True
while len(q) > 0:
    v = q.popleft()
    l = 0
    for w in adj[v]:
        if not visited[w]:
            l += 1
            if label[v][1] == l:
                l += 1
            label[w] = (v, l)
            visited[w] = True
            q.append(w)



for a, b in ab:
    if label[a][0] == b:
        print(label[a][1])
    else:
        print(label[b][1])

Solution (Python):
import collections

n = int(input())
graph = [[] for i in range(n + 1)]
edge = []
for i in range(n - 1):
    a, b = map(int, input().split())
    edge.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
color = {}
queue = collections.deque([(1, 0)])
while queue:
    temp = queue.popleft()
    num = temp[0]
    prev = temp[1]
    if prev:
        col = color[(prev, num)]
    else:
        col = 0
    count = 1
    for i in graph[num]:
        a, b = min(i, num), max(i, num)
        if (a, b) in color.keys():
            continue
        else:
            if count == col:
                color[(a, b)] = count + 1
                count += 2
            else:
                color[(a, b)] = count
                count += 1
            queue.append((i, num))
print(max([len(graph[i]) for i in range(n + 1)]))
for i, j in edge:
    print(color[(i, j)])

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

N = int(input())
ad = [[] for i in range(N+1)]

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

ans_max = 0
for i in range(1,N+1):
    ans_max = max(ans_max, len(ad[i]))

print(ans_max)

visited = [0 for i in range(N+1)]
seen = [0 for i in range(N+1)]
edge_color = defaultdict(int)
node_color = [0 for i in range(N+1)]

def bfs(u):
    stack = deque([u])
    seen[u] = 1
    node_color[u] = 0

    while len(stack) > 0:
        v = stack.popleft()

        c = 1
        for w in ad[v]:
            if seen[w] == 0:
                stack.append(w)
                if c != node_color[v]:
                    edge_color[(v, w)] = c
                    node_color[w] = c
                else:
                    c += 1
                    edge_color[(v, w)] = c
                    node_color[w] = c
                c += 1
                seen[w] = 1

        if stack == []: break

bfs(1)

for edge in edges:
    if edge_color[edge] != 0:
        print(edge_color[edge])
    else:
        print(edge_color[edge.reverse()])

Solution (Python):
N = int(input())
ad = {}
status = {}
edge=[]

for n in range(N):
    ad[n+1]=set([])
    status[n+1] = -1
    
for n in range(N-1):
    a,b = list(map(int,input().split()))
    edge.append((a,b))
    ad[a].add(b)
    ad[b].add(a)
    
color = set([])
parent = [0] * (N+1) 
ans={}


from collections import deque

start = 1
status[start] = 0
que = deque([start])

while len(que) > 0:
    start = que[0]

    c = 1
    for v in ad[start]:
        if status[v] == -1:
            que.append(v)
            status[v]=0
            if parent[start] == c:
                c += 1
            parent[v] = c
            color.add(c)
            
            s = min(start,v)
            e = max(start,v)
            
            ans[s,e]=c
            
            c+=1
            

    que.popleft()

print(len(color))
for e in edge:
    print(ans[e])

Solution (Python):
from collections import deque
n = int(input())
tree = [[] for i in range(n+1)]
edge = []
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
  edge.append((a,b))
m = len(max(tree,key=len))
col = [0]*(n+1)
col[1]='a'
Q = deque([1])

ans = {}
while Q:
  temp = Q.popleft()
  now = 1
  for n in tree[temp]:
    if col[n]:
      continue
    if now == col[temp]:
      now += 1
    col[n] = now
    ans[min(temp,n),max(temp,n)] = now
    now += 1
    Q.append(n)
    
print(m)
for a,b in edge:
  print(ans[(a,b)])

Solution (Python):



from collections import deque






def solve(N, ABs):
    tree_top = [[] for _ in range(N + 1)]
    for i in range(N - 1):
        tree_top[ABs[i][0]].append(i)
        tree_top[ABs[i][1]].append(i)

    max_color = 0
    for tt in tree_top:
        max_color = max(max_color, len(tt))

    ans = [0 for _ in range(N - 1)]
    for tt in tree_top:
        colored = []
        for i in tt:
            if ans[i] != 0:
                colored.append(ans[i])
        colored.sort()
        now_color = 1
        colored_point = 0
        for i in tt:
            if ans[i] != 0:
                continue
            if colored_point < len(colored) \
                    and now_color == colored[colored_point]:
                now_color += 1
                colored_point += 1
            ans[i] = now_color
            now_color += 1

    print(max_color)
    for a in ans:
        print(a)


if __name__ == '__main__':
    
    N = int(input())
    
    
    
    ABs = [[int(i) for i in input().split()] for _ in range(N - 1)]
    solve(N, ABs)

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    tree = [[] for  _ in range(N)]
    abs = []
    for _ in range(N-1):
        a, b = read_ints()
        a -= 1
        b -= 1
        abs.append((a, b))
        tree[a].append(b)
    Q = [(0, -1)]
    colors = {}
    color_count = 0
    while Q:
        node, color = Q.pop()
        c = 1
        for child in tree[node]:
            if color == c:
                c += 1
            colors[(node, child)] = c
            Q.append((child, c))
            color_count = max(color_count, c)
            c += 1
    print(color_count)
    for ab in abs:
        print(colors[ab])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import deque

n = int(input())
G = [[] for _ in range(n + 1)]
G_order = []

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


que = deque([0])



colors = [0] * n

while que:
    
    
    prt = que.popleft()
    color = 0

    
    for cld in G[prt]:
        color += 1
        
        if color == colors[prt]:
            color += 1
        colors[cld] = color
        que.append(cld)





print(max(colors))


for i in G_order:
    print(colors[i])