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())
routings = [[] for _ in range(N+1)]
colors = [0 for _ in range(N+1)]
vertexes = [tuple(map(int, input().split())) for _ in range(N-1)]

for a, b in vertexes:
  routings[a].append(b)
  routings[b].append(a)
  
edges = deque([1])
colors[1] = 0
answer = 0
while len(edges) > 0:
  edge = edges.pop()
  color = colors[edge]
  nc = 1
  answer = max(answer, len(routings[edge]))
  for ne in routings[edge]:
    if colors[ne] == 0 and ne != 1:
      if nc == color:
        nc += 1
      colors[ne] = nc
      edges.append(ne)
      nc += 1
print(answer)
for a, b in vertexes:
  print(colors[b])

Solution (Python):

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def dfs(u, p, c, color, tree):
    color[(u, p)] = c
    color[(p, u)] = c

    now = 0
    for v in tree[u]:
        if v == p:
            continue
        if now == c:
            now += 1

        dfs(v, u, now, color, tree)
        now += 1


def solve():
    N = int(input())

    tree = [[] for _ in range(N)]
    edges = []
    for _ in range(N - 1):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        tree[A].append(B)
        tree[B].append(A)
        edges.append((A, B))

    color = dict()
    dfs(0, -1, -1, color, tree)

    print(max(color.values()) + 1)
    for e in edges:
        print(color[e] + 1)


def main():
    solve()


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())

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

key_order = [0] * (N-1)
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    key_order[i] = (in1, in2)




def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))

    edge_colors = dict()
    node_colors = [0] * len(tree)
    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True

        parent_color = node_colors[q]

        cnt = 1
        for v in tree[q]:
            if not seen[v]:
                if cnt == parent_color:
                    cnt += 1

                edge_colors[(q, v)] = cnt
                node_colors[v] = cnt
                queue.append(v)
                cnt += 1



    """
    node_colors = [set() for _ in tree]
    edge_colors = dict()
    all_colors = set()
    color = 0

    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True

        for v in tree[q]:
            if not seen[v]:
                residual = all_colors - node_colors[q]
                if len(residual) > 0:
                    this_color = residual.pop()
                else:
                    color += 1
                    this_color = color
                edge_colors[(q, v)] = this_color
                node_colors[q].add(this_color)
                node_colors[v].add(this_color)
                all_colors.add(this_color)

                queue.append(v)
    """

    return edge_colors


edge_colors = bfs(tree, 0)

print(max([c for key, c in edge_colors.items()]))
[print(edge_colors[t]) for t in key_order]

Solution (Python):
from sys import setrecursionlimit


setrecursionlimit(10**6)



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



hands = [0 for _ in range(n+1)]
for a, b in t:
    hands[a] += 1
    hands[b] += 1

number_of_colors = max(*hands)

def next_color(i):
    return i+1 if i < number_of_colors else 1



class edge():
    def __init__(self, en):
        self.ends = en
        self.color = 0

    def set_color(self, co):
        self.color = co

class nord():
    def __init__(self, tr):
        self.parent = tr
        self.edges = []

    def add(self, ed):
        self.edges.append(ed)

    def set_color(self, previous_color):
        co = next_color(previous_color)
        for ed in self.edges:
            if ed.color == 0:
                ed.set_color(co)
                for i in ed.ends:
                    no = self.parent.nords[i-1]
                    if self is not no:
                        no.set_color(co)
                co = next_color(co)

class tree():
    def __init__(self):
        self.nords = []

    def add_nord(self, no):
        self.nords.append(no)

    def add_edge(self, ed):
        for i in ed.ends:
            self.nords[i-1].add(ed)

    def set_color(self):
        self.nords[0].set_color(0)


tr = tree()
for _ in range(n):
    no = nord(tr)
    tr.add_nord(no)

e_tree = []
for en in t:
    ed = edge(en)
    e_tree.append(ed)
    tr.add_edge(ed)

tr.set_color()

print(number_of_colors)
for e in e_tree:
    print(e.color)

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

col = [0 for i in range(n)]
visited = [False for i in range(n)]
visited[0] = True
v = [0]

while v:
  d = v.pop(0)
  k = 1
  for i in a[d]:
    if visited[i] == False:
      if col[d] == k:
        k += 1
      col[i] = k
      visited[i] = True
      v.append(i)
      k += 1

print (max(col))
for i in e:
  print (col[i])

Solution (Python):
from collections import deque
n = int(input())
a = [[] for i in range(n)]
e = []
for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  a[b].append(c)
  e.append(c)
col = [0 for i in range(n)]
v = deque([0])

while v:
  d = v.popleft()
  k = 1
  for i in a[d]:
    if col[d] == k:
      k += 1
    col[i] = k
    v.append(i)
    k += 1
print (max(col))
for i in e:
  print(col[i])

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

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

color_max = 0
color_list = [0]*(N-1)
visit = [False]*(N+1)
visit[1] = True
def dfs(node, color, used_path):
    global visit
    nxt_color = 0
    for nxt in path[node]:
        nxt_node = nxt[0]
        use_path = nxt[1]
        if visit[nxt_node] == False:
            visit[nxt_node] = True
            nxt_color += 1
            if nxt_color == color:
                nxt_color += 1
            dfs(nxt_node, nxt_color, use_path)
    
    global color_list
    if used_path != -1:
        color_list[used_path] = color

dfs(1, 0, -1)


for c in color_list:
    color_max = max(c, color_max)
print(color_max)
print("\n".join(map(str, color_list)))

Solution (Python):
N=int(input())
l=[[] for i in range(N)]
color=[0]*N
mem=[]
for i in range(N-1):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   mem.append(b)
from collections import deque
que=deque([0])
while que:
   node=que.popleft()
   c=1
   for i in l[node]:
      if color[node]==c:
         c+=1
      color[i]=c
      c+=1
      que.append(i)
print(max(color))
for i in mem:
   print(color[i])

Solution (Python):
from collections import deque
n=int(input())
e=[]
edge=[[] for _ in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
    e.append(str(x-1)+" "+str(y-1))
par=[0]*n 
visited=[0]*n
visited[0]=1
que=deque([0])
ans=dict()
K=0
while que:
    now=que.popleft()
    color=1
    for x in edge[now]:
        if visited[x]:
            continue
        visited[x]=1
        que.append(x)
        if color==par[now]:
            color+=1
        par[x]=color
        ans[str(min(x,now))+" "+str(max(x,now))]=color
        color+=1
print(max(ans.values()))
for i in e:
    print(ans[i])

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    N=int(readline())
    g=[[] for _ in range(N)]
    AB=[]
    for _ in range(N-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        g[a].append(b)
        g[b].append(a)
        AB.append(str(a)+" "+str(b))

    link=[0]*N
    que=deque([0])
    is_searched=[False]*N
    is_searched[0]=True
    K=0
    ans=dict()
    
    while len(que)>=1:
        now=que.popleft()
        color=1
        for x in g[now]:
            if is_searched[x]:
                continue
            else:
                is_searched[x]=True
                que.append(x)
                if color==link[now]:
                    color+=1
                link[x]=color
                ans[str(min(now,x))+" "+str(max(now,x))]=color
                color+=1
        color-=1
        K=max(K,color)

    
    print(K)
    for key in AB:
        print(ans[key])
        
if __name__=="__main__":
    main()

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    N=int(readline())
    g=[[] for _ in range(N)]
    AB=[]
    for _ in range(N-1):
        a,b=map(lambda x:int(x)-1,readline().split())
        g[a].append(b)
        g[b].append(a)
        AB.append(str(a)+" "+str(b))

    link=[0]*N
    que=deque([0])
    is_searched=[False]*N
    is_searched[0]=True
    K=0
    ans=dict()
    
    while len(que)>=1:
        now=que.popleft()
        color=1
        for x in g[now]:
            if is_searched[x]:
                continue
            else:
                is_searched[x]=True
                que.append(x)
                if color==link[now]:
                    color+=1
                link[x]=color
                ans[str(min(now,x))+" "+str(max(now,x))]=color
                color+=1
        color-=1
        K=max(K,color)

    
    print(K)
    for key in AB:
        print(ans[key])
        
if __name__=="__main__":
    main()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math








INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def dfs(c, to, cols, max_counts, pre_col = 0):
    colors = set()
    colors.add(pre_col)
    num = 1
    for idx, n in to[c]:
        if cols[idx]:continue
        for i in range(num, max_counts+1):
            if not i in colors:
                num = i
                cols[idx] = i
                colors.add(i)
                dfs(n, to, cols, max_counts, i)
                break


def run():
    N = int(sysread())
    to = [[] for _ in range(N+1)]
    cols = [0] * (N-1)
    counts = [0 for i in range(N+1)]
    for i in range(N-1):
        a,b = mapline()
        to[a].append((i, b))
        to[b].append((i, a))
        counts[a] += 1
        counts[b] += 1

    max_counts = max(counts)
    print(max_counts)
    dfs(1, to, cols, max_counts)

    for c in cols:
        print(c)

    
if __name__ == "__main__":
    run()

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



N=intput()
node=[list() for _ in range(N+1)]
done=[False]*(N+1)
color=[0]*(N+1)
ans=[0]*(N-1)
S=dict()
for i in range(N-1):
    u,v=mint()
    node[u].append(v)
    node[v].append(u)
    S[(u,v)]=i
    S[(v,u)]=i
q=deque([1])
done[1]=True
while q:
    u=q.popleft()
    c=1
    for v in node[u]:
        if not done[v]:
            if c==color[u]:
                c+=1
            color[v]=c
            ans[S[(u,v)]]=c
            done[v]=True
            q.append(v)
            c+=1
print(max(ans))
lprint(ans)

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

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

for i in range(n-1):
    a, b = map(int,input().split())
    t[a].append((b,i))
    t[b].append((a,i))
num = max([len(tmp) for tmp in t])
print(num)

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

def dfs(n, before, bcol):
    col = 1
    for i, j in t[n]:
        if i == before:
            continue
        if col == bcol:
            col += 1
        ans[j] = col
        dfs(i, n, col)
        col += 1

dfs(1, 0, -1)
for i in range(n-1):
    print(ans[i])

Solution (Python):
from queue import Queue
N = int(input())
G = [[] for _ in range(N)]
Q = [{} for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    Q[a-1][b-1] = i

K = max(list(map(len, G)))
print(K)
ans = [0] * (N-1)
q = Queue()
q.put(0)
while not q.empty():
    v = q.get()
    c = set()
    for u in G[v]:
        if u < v:
            c.add(ans[Q[u][v]])
    
    i = 1
    for u in G[v]:
        if u > v:
            while i in c: i += 1
            ans[Q[v][u]] = i
            i += 1
            q.put(u)

for a in ans:
    print(a)

Solution (Python):
from collections import deque

N=int(input())
G=[[] for _ in [0]*(N+1)]
for i in range(1,N):
    a,b=map(int,input().split())
    G[a].append((b,i))
    G[b].append((a,i))

root,res=0,0
for i in range(1,N+1):
    tmp=len(G[i])
    if tmp>res:
        res=tmp
        root=i
        
q=deque()
q.append((root,0))
color=[0]*N
D=[N+10]*(N+1)
D[root]=0
while q:
    p,c=q.popleft()
    nc=1
    while G[p]:
        np,ni=G[p].pop()
        if D[np]>D[p]:
            D[np]=D[p]+1
            if nc==c:
                nc+=1
            color[ni]=nc
            q.append((np,nc))
            nc+=1
print(res,*color[1:],sep='\n')

Solution (Python):









import os
import sys


from collections import deque


class BFS():
    def __init__(self, path, N):
        self.N = N
        self.color_path = [-1]*self.N
        self.path = path
        self.init = 1
        self.Q = deque([[0, self.init]])

    def forward(self):
        while self.Q:
            prev_path, u = self.Q.popleft()
            p_cnt = 1
            for cp, v in self.path[u]:
                if self.color_path[cp] == -1:
                    if prev_path == p_cnt:
                        p_cnt += 1
                    self.Q.append([p_cnt, v])
                    self.color_path[cp] = p_cnt
                    p_cnt += 1


    def print_ans(self):
        self.color_path.pop(0)
        print(max(self.color_path))
        for cp in self.color_path:
            print(cp)


def main():
    N = int(input())
    path = [[] for _ in range(N+1)]
    for i in range(1, N):
        a, b = map(int, input().split())
        path[a].append([i, b])
        path[b].append([i, a])
    bfs = BFS(path, N)
    bfs.forward()
    bfs.print_ans()



if __name__ == "__main__":
    main()

Solution (Python):
import collections
N = int(input())
graph = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append([b-1,i])
    graph[b-1].append([a-1,i])

q = collections.deque()
ans = [-1]*(N-1)
q.append([0,-1])
while len(q) != 0:
    tmp = 1
    v, v2 = q.popleft()
    for w, i in graph[v]:
        if ans[i] != -1:
            continue
        if ans[v2] == tmp:
            tmp += 1
        ans[i] = tmp
        tmp += 1
        q.append([w,i])

print(len(set(ans)))
for i in ans:
    print(i)

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

N = int(readline())

G = [[] for i in range(N)]
from collections import defaultdict
E = defaultdict(int)

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

from collections import deque
q = deque([])
ans = [None] * (N - 1)

q.append([0, -1, 0])
maxcol = 0
while q:
  v, parent, color = q.popleft()
  if color > maxcol:
    maxcol = color
  if (v, parent) in E:
    ans[E[(v, parent)]] = color
  elif (parent, v) in E:
    ans[E[(parent, v)]] = color
  next_col = 0
  for child in G[v]:
    if child == parent:
      continue
    next_col += 1
    if next_col == color:
      next_col += 1
    q.append([child, v, next_col])
    
print(maxcol)
for a in ans:
  print(a)

Solution (Python):
N = int(input())
G = [[] for n in range(N)]
vc = N*[0]
ec = (N-1)*[0]
h = 1

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

for v,g in enumerate(G):
  t = 1
  for b,i in g:
    if vc[v]==t:
      t+=1
    vc[b] = t
    ec[i] = t
    h = max(h,t)
    t+=1

print(h)
for n in range(N-1):
  print(ec[n])

Solution (Python):
def main():
	N = int(input())
	vertex = [[] for i in range(N)]

	ini_v = 0
	for i in range(N - 1):
		a, b = [int(x) for x in input().split(" ")]
		if i == 0:
			ini_v = a - 1
		vertex[a - 1].append({"v": b - 1, "e": i})
		vertex[b - 1].append({"v": a - 1, "e": i})

	checked_v = [0] * N
	checked_e = [0] * (N - 1)
	to_visit = [ini_v]
	checked_v[ini_v] = 1
	color_e = [-1] * (N - 1)

	while len(to_visit):
		visiting = to_visit.pop(0)
		vs = vertex[visiting]
		used_cs = []
		cless_e = []
		for d in vs:
			if checked_v[d["v"]] == 0:
				checked_v[d["v"]] = 1
				to_visit.append(d["v"])
			if color_e[d["e"]] == -1:
				cless_e.append(d["e"])
			else:
				used_cs.append(color_e[d["e"]])
		s = 0
		for j in range(len(vs)):
			if s >= len(cless_e) or len(cless_e) == 0:
				break
			elif j in used_cs:
				continue
			else:
				color_e[cless_e[s]] = j
				s += 1

	print(max(color_e) + 1)
	for i in range(len(color_e)):
		print(color_e[i] + 1)

main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N = getN()

dist = [[] for i in range(N)]
edges = {}
for i in range(N - 1):
    a, b = getNM()
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)
    edges[(a - 1, b - 1)] = i
    edges[(b - 1, a - 1)] = i

color = [-1] * N
color[0] = 0
ans = [0] * (N - 1)
pos = deque([0])

while pos:
    u = pos.popleft()
    j = 1
    for i in dist[u]:
        if color[i] != -1:
            continue
        if j == color[u]:
            j += 1
        color[i] = j
        ans[edges[(i, u)]] = j
        pos.append(i)
        j += 1

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

Solution (Python):
from sys import stdin

def getval():
    n = int(input())
    e = [[i] + list(map(int,stdin.readline().split())) for i in range(n-1)]
    return n,e

def main(n,e):
    tree = [[] for i in range(n)]
    ans = [0 for i in range(n-1)]
    for i in e:
        tree[i[1]-1].append([i[2]-1,i[0]])
    tree[0].append(0)
    k = 1
    q = [0]
    while q:
        n = 0
        idx = q.pop(0)
        for i in range(len(tree[idx])-1):
            n += 1
            if n==tree[idx][-1]:
                n += 1
            ans[tree[idx][i][-1]] = n
            tree[tree[idx][i][0]].append(n)
            q.append(tree[idx][i][0])
        k = max(k,n)

    print(k)
    for i in ans:
        print(i)
            
            
if __name__=="__main__":
    n,e = getval()
    main(n,e)

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


N = int(input())
to = [[] for _ in range(N)]
order = []

for _ in range(N - 1):
    a, b = list(map(lambda x:int(x) - 1, input().split()))
    to[a].append(b)
    to[b].append(a)
    order.append(b)


def solve():
    dist = [-1] * N
    
    color = [0] * N
    dist[0] = 0
    color[0] = 0
    que = deque([0])

    while que:
        v = que.popleft()
        used_color = [color[v]]
        next_color = 1
        for nv in to[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                while next_color in used_color:
                    next_color += 1
                color[nv] = next_color
                used_color.append(next_color)
                que.append(nv)

    print(len(set(color[1:])))
    for i in range(N - 1):
        print(color[order[i]])


if __name__ == "__main__":
    solve()

Solution (Python):
N =int(input())

edge = [[] for i in range(N)]
adj = [[] for i in range(N)]

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

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

from collections import deque
color = [-1] * (N - 1)
qu = deque([0])
done = [False] * N
done[0] = True
vc = [-1] * N
while(len(qu) > 0):
    v = qu.popleft()
    for nv, e in adj[v]:
        if not done[nv]:
            vc[v] = (vc[v] + 1) % K
            color[e] = vc[v]
            qu.append(nv)
            vc[nv] = vc[v]
            done[nv] = True

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

Solution (Python):
from collections import deque

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

l = [[] for _ in range(n+1)]
for a, b in ab:
    l[a].append(b)
    l[b].append(a)

parents = [-1] * (n+1)
order = []
q = deque()
q.append(1)
while q:
    c = q.pop()
    order.append(c)
    for i in l[c]:
        if i == parents[c]:
            continue
        parents[i] = c
        q.append(i)

color = [-1] * (n+1)
for i in order:
    ng = color[i]
    c = 1
    for j in l[i]:
        if j == parents[i]:
            continue
        if c == ng:
            c += 1
        color[j] = c
        c += 1

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

print(max(ans))
print('\n'.join(list(map(str, ans))))

Solution (Python):
from collections import defaultdict
N = int(input())
edge = []
relation = defaultdict(set)
for i in range(N - 1):
    a, b = map(lambda x: x - 1, map(int, input().split()))
    edge.append((a,b))
    relation[a].add(b)
    relation[b].add(a)

print(max(map(lambda x: len(relation[x]), relation)))
answer = {}
queue = []
queue.append((0, 0)) 
already = set()
counter = 0
already.add(0)
while counter < len(queue):
    node, color = queue[counter]
    c = 1 if color != 1 else 2
    for n in relation[node]:
        if n not in already:
            queue.append((n, c))
            already.add(n)
            answer[(node, n)] = c
            c += 1
            if c == color:
                c += 1
    counter += 1
for e in edge:
    print(answer[e])

Solution (Python):
def main():
    import sys
    readline = sys.stdin.buffer.readline

    from collections import deque

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

    l = [[] for _ in range(n+1)]
    for a, b in ab:
        l[a].append(b)
        l[b].append(a)

    parents = [-1] * (n+1)
    order = []
    q = deque()
    q.append(1)
    while q:
        c = q.pop()
        order.append(c)
        for i in l[c]:
            if i == parents[c]:
                continue
            parents[i] = c
            q.append(i)
    
    color = [-1] * (n+1)
    for i in order:
        ng = color[i]
        c = 1
        for j in l[i]:
            if j == parents[i]:
                continue
            if c == ng:
                c += 1
            color[j] = c
            c += 1
    
    ans = []
    for a, b in ab:
        if a == parents[b]:
            ans.append(color[b])
        else:
            ans.append(color[a])

    print(max(ans))
    print('\n'.join(list(map(str, ans))))

if __name__ == '__main__':
    main()

Solution (Python):
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
from collections import deque

class Graph():
    def __init__(self, v):
        from heapq import heappop, heappush
        self.v = v
        self.graph = [[] for _ in range(v)]
        self.INF = 10 ** 9
    
    def addEdge(self, start, end, edge):
        self.graph[start].append((end, edge))
        self.graph[end].append((start, edge))

def do():
    n=INT()
    g=Graph(n)
    for i in range(n-1):
        a,b=INTM()
        a-=1
        b-=1
        g.addEdge(a,b,i)

    
    que=deque()
    check=[True]*n
    clrs=[0]*(n-1)
    que.append([0,0])
    check[0]=False
    while que:
        clr=1
        now,clr_f=que.popleft()
        if clr_f==1:
            clr=2
        for next,i in g.graph[now]:
            if check[next]:
                check[next]=False
                que.append([next,clr])
                clrs[i]=clr
                clr+=1
                if clr==clr_f:
                    clr+=1
    
    print(max(clrs))
    for i in range(n-1):
        print(clrs[i])








if __name__=='__main__':
    do()

Solution (Python):
from collections import defaultdict,deque
n = int(input())
d = defaultdict(list)
l = []
for i in range(n-1):
    a,b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    l.append((a,b))



que = deque([a])
visited = [-1] + [False]*n
visited[a] = True

preans = defaultdict(list)
ans = defaultdict(int)
maxi = 1

while que:
    v = que.popleft()
    cnt = 1
    for x in d[v]:
        if not visited[x]:
            while cnt in preans[v]:
                cnt += 1
            maxi = max(maxi,cnt)
            preans[x].append(cnt)
            ans[(v,x)] = cnt
            ans[(x,v)] = cnt
            que.append(x)
            visited[x] = True
            cnt += 1
    
    
print(maxi)

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

Solution (Python):
N=int(input())
ans=[-1]*(N-1)
rootLine=[0]*N
numLine=[0]*N
l=[]
for i in range(N-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  l.append([a,b,i])
l.sort()

for a,b,i in l:
  numLine[a]+=1
  if numLine[a]==rootLine[a]:
    numLine[a]+=1
  ans[i]=numLine[a]
  rootLine[b]=numLine[a]

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

Solution (Python):
N=int(input())
l=[[] for i in range(N)]
color=[0]*N
mem=[]
for i in range(N-1):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   mem.append(b)
from collections import deque
que=deque([0])
while que:
   node=que.popleft()
   c=1
   for i in l[node]:
      if color[node]==c:
         c+=1
      color[i]=c
      c+=1
      que.append(i)
print(max(color))
for i in mem:
   print(color[i])