Problem:
 Score : 400 points    Problem Statement  Given is a tree G with N vertices.
The vertices are numbered 1 through N , and the i -th edge connects Vertex a_i and Vertex b_i .  Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.  Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.      Constraints   2 \le N \le 10^5  1 \le a_i \lt b_i \le N  All values in input are integers.  The given graph is a tree.         Input  Input is given from Standard Input in the following format:  N  a_1  b_1  a_2  b_2  \vdots  a_{N-1}  b_{N-1}       Output  Print N lines.  The first line should contain K , the number of colors used.  The (i+1) -th line (1 \le i \le N-1) should contain c_i , the integer representing the color of the i -th edge, where 1 \le c_i \le K must hold.  If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.        Sample Input 1 3
1 2
2 3      Sample Output 1 2
1
2       Sample Input 2 8
1 2
2 3
2 4
2 5
4 7
5 6
6 8      Sample Output 2 4
1
2
3
4
1
1
2       Sample Input 3 6
1 2
1 3
1 4
1 5
1 6      Sample Output 3 5
1
2
3
4
5

Solution (Python):
import sys

sys.setrecursionlimit(100000)

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

def dfs(i, p, pcol):
    col = 1
    ret = 0
    for c, e in edges[i]:
        if c != p:
            if col == pcol:
                col += 1
            color[e] = col
            ret = max(ret, dfs(c, i, col))
            col += 1
    return max(ret, col - 1)

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

Solution (Python):
n=int(input())
l=[[]for i in range(n)]
ans=set()
ll=[set() for i in range(n)]
c=1
ab=[]
from collections import Counter
ans2=Counter()
for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    ab.append((a,b))
    l[a].append(b)
    

for i in range(n):
    c=1
    for j in l[i]:
        while True:
            if (c not in ll[j]) and (c not in ll[i]):
                ll[j].add(c)
                ll[i].add(c)
                ans.add(c)
                ans2[(i,j)]=c
                break
            else:
                c+=1
print(len(ans))


for i,j in ab:
    print(ans2[(i,j)])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def solve():
    n = II()
    ed = [[] for i in range(n)]
    edg = defaultdict(int)
    ans = [None] * (n - 1)
    for i in range(n - 1):
        a, b = LI_()
        ed[a].append((b, i))
        ed[b].append((a, i))
        edg[a] += 1
        edg[b] += 1
    ma = max(edg.values())
    print(ma)
    for num, a in enumerate(ed):
        if len(a) == ma:
            break
    q = deque([num])
    while q:
        a = q.pop()
        o = 1
        li = defaultdict(int)
        for b, i in ed[a]:
            if ans[i] != None:
                li[ans[i]] = 1
        for b, i in ed[a]:
            if ans[i] == None:
                q.appendleft(b)
                while li[o]:
                    o += 1
                ans[i] = o
                o += 1
    for i in ans:
        print(i)
    return



if __name__ == '__main__':
    solve()

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

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

colors = dict()
def dfs(vNow, vPar, color):
    c = 1
    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        if c == color:
            c += 1
        A, B = vNow, v2
        if A > B:
            A, B = B, A
        colors[(A, B)] = c
        dfs(v2, vNow, c)
        c += 1

dfs(0, -1, 0)


anss = []
for A, B in edges:
    anss.append(colors[(A, B)])

print(max(colors.values()))
print('\n'.join(map(str, anss)))

Solution (Python):
N = int(input())
ABs = []
E = [set() for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  ABs.append((a, b))
  E[a].add(b)
  E[b].add(a)
K = max([len(s) for s in E])
print(K)
Is = sorted(range(N-1), key=lambda i: ABs[i])





cs = [-1]*(N-1)
V = [-1]*N
for i in range(N-1):
  j = Is[i]
  a, b = ABs[j]
  c = V[a]
  c = (c+1)%K
  V[a] = c
  V[b] = c
  cs[j] = c

for c in cs:
  print(c+1)

Solution (Python):
from queue import  Queue
n = int(input())


class uf_tree():

  def __init__(self, n):
    self.n = n
    self.par = [i for i in range(n)]
    self.rank = [0 for i in range(n)]

  def indep(self):
    dep = 0
    for i in range(self.n):
      if i == self.par[i]:
        dep += 1

    return dep

  def unite(self, x, y):
    if self.root(x) == self.root(y):
      return
    else:
      rootx = self.root(x)
      rooty = self.root(y)
      if self.rank[rootx] < self.rank[rooty]:
        self.par[rootx] = rooty
      else:
        self.par[rooty] = rootx
        if self.rank[rootx] == self.rank[rooty]:
          self.rank[rootx] += 1

  def root(self, i):
    if self.par[i] == i:
      return i
    else:
      self.par[i] = self.root(self.par[i])
      return self.par[i]

  def same(self, x, y):
    return self.root(x) == self.root(y)

tree = uf_tree(n)

edges = {}
arr = [0 for i in range(n-1)]
dic = {}

for i in range(n-1):
  a,b = map(int,input().split())
  dic[str(a-1)+","+str(b-1)] = i
  dic[str(b - 1) + "," + str(a - 1)] = i
  if a-1 in edges:
    edges[a-1].append(b-1)
  else:
    edges[a-1] = [b-1]
  if b-1 in edges:
    edges[b - 1].append(a - 1)
  else:
    edges[b - 1] = [a - 1]
  tree.unite(a-1,b-1)

root = tree.root(0)
que = []
que.append([root,0])
visited = set()
visited.add(root)


while not len(que)==0:
  top = que[-1]
  que.pop()
  v = top[0]
  col = top[1]
  color = 1
  if v in edges:
    nex = edges[v]
  else:
    continue
  nc = []
  
  
  for i in range(len(nex)):
    if nex[i] in visited:
      continue
    else:
      visited.add(nex[i])
    if col != color:
      
      que.append([nex[i],color])
      arr[dic[str(v)+","+str(nex[i])]] = color
      color += 1
    else:
      
      arr[dic[str(v)+","+str(nex[i])]] = color+1
      que.append([nex[i],color+1])
      color += 2

print(max(arr))
for a in arr:
  print(a)

Solution (Python):

import sys
from collections import deque
input = sys.stdin.readline
INF = 10**9

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

colors = 0
for i, line in enumerate(edge):
    colors = max(colors, len(line))
    if len(line) == 1:
        start = i
print(colors)

dq = deque()
dq.append((i, -1, -1))

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

while dq:
    v, prev, prev_c = dq.popleft()
    c = 0
    for dest, index in edge[v]:
        if dest == prev:
            continue
        if c == prev_c:
            c += 1
        color[index] = c 
        dq.append((dest, v, c))
        c += 1
for item in color:
    print(item + 1)

Solution (Python):
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n = ri()
ls = rils(n - 1)
temp = []
for a, b in ls:
    if a > b:
        a, b = b, a
    temp.append((a - 1, b - 1))
ls = temp

edges = collections.defaultdict(list)
for i, (a, b) in enumerate(ls):
    edges[a].append((b, i))

colors = [-1] * n
colors[0] = (0, 0)

q = collections.deque()
q.append((0, 0))
while q:
    node, i0 = q.popleft()
    c = 1
    for next_, i in edges[node]:
        if colors[next_] != -1:
            continue
        if colors[node][0] == c:
            c += 1
            colors[next_] = (c, i)
        else:
            colors[next_] = (c, i)
        c += 1
        q.append((next_, i))
colors = [c for c, i in sorted(colors, key=lambda x: x[1])]
print(max(colors))
for c in colors[1:]:
    print(c)

Solution (Python):
from collections import deque


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add((b-1, i))
    ans = [0] * (N-1)
    q = deque([])
    q.append((0, -1))
    while len(q):
        cur, used = q.popleft()
        idx = 0
        for nxt, edge in adj[cur]:
            idx += 1
            if idx == used:
                idx += 1
            if ans[edge] != 0:
                continue
            ans[edge] = idx
            q.append((nxt, idx))
    mx = max(ans)
    print(mx)
    for i in range(N-1):
        print(ans[i])


if __name__ == "__main__":
    main()

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

v_color = [0] * N
e_color = [0] * (N-1)
K = 1
for a, children in enumerate(G):
    c = 1
    for b, i in children:
        if c == v_color[a]:
            c += 1
        v_color[b] = c
        e_color[i] = c
        K = max(K, c)
        c += 1

print(K)
print('\n'.join(map(str, e_color)))

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed==False:
            pt[t[i]-1].append(s[i]-1)
    return pt

N = I()
a,b = Line(N-1,2)
d = defaultdict(int)

pt = edges_to_pt(a,b,N)
for i in range(N-1):
    x = min(a[i],b[i])
    y = max(a[i],b[i])
    d[(x-1)*N+(y-1)] = i

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

color = [0]*N
q = [0]
c = 1
while q:
    q1 = []
    for i in q:
        c = 1
        for j in pt[i]:
            if used[j]==False:
                if c==color[i]:
                    c += 1
                color[j] = c
                used[j] = True
                ans[d[min(i,j)*N+max(i,j)]] = c
                c += 1
                q1.append(j)
    q = q1

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

Solution (Python):

import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count = 0

n=int(input())
edgecolor=[0]*(n-1)
nodecolorset=[set() for i in range(n)]
G=[[]*n 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,i))
    G[b].append((a,i))

def dfs(node,color):
    i=1
    for gi,edgenum in G[node]:
        if edgecolor[edgenum]:continue
        if i!=color:
            edgecolor[edgenum]=i
        else:
            i+=1
            edgecolor[edgenum]=i
        dfs(gi,i)
        i+=1


dfs(0,0)
print(max(edgecolor))
for ci in edgecolor:
    print(ci)

Solution (Python):
from collections import deque
N = int(input())
P = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    P[a-1].append((b-1, i))
    P[b-1].append((a-1, i))
ans = [0] * N
q = deque()
q.append((0, 0))
colmax = 0
while q:
    u, pcol = q.popleft()
    icol = 1
    for v, i in P[u]:
        if ans[i] != 0:
            continue
        if icol == pcol:
            icol += 1
        ans[i] = icol
        q.append((v, icol))
        colmax = max(colmax, icol)
        icol += 1

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

Solution (Python):

from collections import defaultdict
import queue


def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.color = defaultdict(int)
		self.precolor = [None] * N
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			self.c = 0
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.c += 1
					if self.c == self.precolor[v]:
						self.c += 1
					x, y = sorted([i, v])
					self.color[100000 * x + y] = self.c
					self.precolor[i] = self.c
					self.Q.put(i)
					self.visit[i] = "Yes"



def main():
	N = int(input())
	G = Graph()
	S = []
	for i in range(N - 1):
		a, b = getlist()
		a, b = sorted([a, b])
		G.add_edge(a - 1, b - 1)
		G.add_edge(b - 1, a - 1)
		S.append([a - 1, b - 1])
	BF = BFS(G, 0, N)
	D = BF.color
	
	ans = []
	d = defaultdict(int)
	for i in range(N - 1):
		a = S[i][0]
		b = S[i][1]
		ans.append(D[100000 * a + b])
		d[D[100000 * a + b]] += 1
	print(len(d))
	for i in range(N - 1):
		print(ans[i])

if __name__ == '__main__':
	main()

Solution (Python):
from collections import deque

N = int(input())

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

ans = 1
ans_l = [-1]*(N-1)
que = deque([(1, -1, -1)])

while que:
    ci, pi, ec = que.popleft()
    c = 0

    for ni, n in G[ci]:
        if ni != pi:
            c += 1
            if c == ec:
                c += 1
            ans = max(ans, c)
            que.append((ni, ci, c))
            ans_l[n] = c

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

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())

g = [[] for _ in range(n)]
d = {}
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    d[(a-1,b-1)] = i
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 

def dfs(v,p,j): 
    """
    vでの操作をここに
    """
    num = -1
    for c in g[v]:
        if c == p: continue
        num += 1
        col = (j+num)%m+1
        if c > v: ans[d[(v,c)]] = col
        else: ans[d[(c,v)]] = col
        dfs(c,v,col)

m = max(len(i) for i in g)
ans = [0]*(n-1)

dfs(0,-1,0)


print(m)
print(*ans,sep = "\n")

Solution (Python):

import sys
from collections import defaultdict, deque
from operator import itemgetter
from heapq import heappop, heappush
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N = int(input())
M = []
D = {}

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

for i in range(N-1):
    a, b = inpl()
    D[(a, b)] = i
    D[(b, a)] = i
    G[a].append(b)
    G[b].append(a)

K = max(map(len, G))

used = [set() for _ in range(N+1)]
ans = [0]*(N-1)
Q = deque([1])
searched = [0]*(N+1)
searched[1] = True

while Q:
    p = Q.popleft()
    i = 0
    for q in G[p]:
        if ans[D[(p, q)]]:
            continue
        while True:
            i += 1
            if (i in used[p]) or (i in used[q]):
                continue
            ans[D[(p, q)]] = i
            used[p].add(i)
            used[q].add(i)
            if not searched[q]:
                searched[q] = True
                Q.append(q)
            break

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

Solution (Python):


import collections


class Node(object):

  def __init__(self):
    self.edges = []


class Edge(object):

  def __init__(self):
    self.color = -1


def main():
  nodes = [Node() for _ in range(int(input()))]
  edges = [Edge() for _ in range(len(nodes) - 1)]

  for i in range(len(nodes) - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    nodes[a].edges.append((edges[i], nodes[b]))
    nodes[b].edges.append((edges[i], nodes[a]))

  queue = collections.deque()
  node = nodes[0]

  for i in range(len(node.edges)):
    node.edges[i][0].color = i
    queue.append(node.edges[i][1])

  max_color = len(node.edges) - 1

  while len(queue) != 0:
    node = queue.popleft()
    exist = -1
    index = 0

    for i in range(len(node.edges)):
      if node.edges[i][0].color != -1:
        exist = node.edges[i][0].color
        break

    for i in range(len(node.edges)):
      if index == exist:
        index += 1

      if node.edges[i][0].color != -1:
        continue

      node.edges[i][0].color = index
      index += 1
      queue.append(node.edges[i][1])

    max_color = max(len(node.edges) - 1, max_color)

  print(max_color + 1)
  for e in edges:
    print(e.color + 1)


if __name__ == '__main__':
  main()

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

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

K = max(len(S) for S in ad)
d = dict()

def dfs(v=0, pv=-1, memo=-1):
    color = 0
    for nv in ad[v]:
        if nv == pv:
            continue
        if color == memo:
            color += 1
        d[(v, nv)] = color
        d[(nv, v)] = color
        dfs(nv, v, color)
        color += 1

dfs()

print(K)
for e in edge:
    print(d[e]+1)

Solution (Python):


import os
import sys


def main():
    N = read_int()
    E = []
    G = [dict() for _ in range(N)]

    for _ in range(N - 1):
        a, b = read_ints()
        a -= 1
        b -= 1
        E.append((a, b))
        G[a][b] = -1
        G[b][a] = -a

    K, C = solve(N, E, G)
    print(K)
    for c in C:
        print(c + 1)


def solve(N, E, G):
    K = max([len(d) for d in G])

    q = [(-1, 0)]
    while q:
        p, i = q.pop()

        used = -1
        if p != -1:
            used = G[p][i]

        c = 0
        for j in G[i]:
            if j == p:
                continue
            if c == used:
                c += 1
            G[i][j] = c
            G[j][i] = c
            q.append((i, j))
            c += 1

    C = [-1] * len(E)
    for i, (a, b) in enumerate(E):
        C[i] = G[a][b]
    return K, C




DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
l = []
edge = [[] for i in range(N)]
idx = {}
for i in range(N-1):
	a,b = map(int,input().split())
	a -= 1
	b -= 1
	edge[a].append([b,None])
	edge[b].append([a,None])
	l.append((a,b))
	idx[(a,b)] = len(edge[a]) - 1

search = [(0,0)]
searched = [False for i in range(N)]
col_max = 1
while len(search) > 0:
	s = search.pop()
	n = s[0]
	c = s[1]
	searched[n] = True
	color = 1
	for e in edge[n]:
		if not searched[e[0]]:
			if color == c:
				color += 1
			e[1] = color
			col_max = max(col_max, color)
			search.append((e[0], color))
			color += 1
print(col_max)
for e in l:
	a,b = e[0], e[1]
	print(edge[a][idx[(a,b)]][1])

Solution (Python):
from sys import setrecursionlimit

setrecursionlimit(100000)

N = int(input())

adj = [list() for _ in range(N)]

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


res = [None]*(N-1)

C = max(len(l) for l in adj)

def rec(v, used):
    global res
    c = 0
    for u,i in adj[v]:
        if c == used:
            c += 1
        if res[i] is None:
            res[i] = c
            rec(u, c)
            c += 1
rec(0, -1)
print(C)
for c in res:
    print(c+1)

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

N = int(input())
graph = [[] for _ in range(N)]
Ed = {}
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    Ed[(a-1)*N+b-1] = i
    Ed[(b-1)*N+a-1] = i

q = [0]
checked = [False]*N
checked[0] = True

V_color = [None]*N
V_color[0] = 0

ans = [None]*(N-1)
while q:
    qq = []
    for p in q:
        c = V_color[p]
        t = 1
        for np in graph[p]:
            if not checked[np]:
                checked[np] = True
                qq.append(np)
                ind = Ed[p*N+np]
                if t == c:
                    t += 1
                ans[ind] = t
                V_color[np] = t
                t += 1
    q = qq

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

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


N = int(input())
AB = [0] * (N + 1) 
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))

check = [[0, 0] for _ in range(N + 1)] 
check[1][0] = 1
ans = 0
stack = [1]
while len(stack) != 0:
    tmp = stack.pop()
    color = 1
    for g, i in G[tmp]:
        if check[g][0] == 1: 
            continue
        if color == check[tmp][1]:
            color += 1
        AB[i] = color
        check[g][0] = 1
        check[g][1] = color
        color += 1
        stack.append(g)

K = max(AB)
print (K)
print (*AB[:N - 1], sep = '\n')

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n = I()
G = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = LI()
    G[a - 1] += [(i, b - 1)]
    G[b - 1] += [(i, a - 1)]


k = 0
for i in G:
    k = max(k, len(i))


col_set = set(range(1, k + 1))
ans = [0] * (n - 1)
visited = [0] * n
visited[0] = 1
dq = deque([(0, 0)])
while dq:
    u, pre_col = dq.popleft()
    col = 1
    for i, v in G[u]:
        if not visited[v]:
            visited[v] = 1
            if pre_col == col:
                col += 1
            ans[i] = col
            dq += [(v, col)]
            col += 1


print(k)
for j in ans:
    print(j)

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

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

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

ret = [0] * (N - 1)

def dfs(pre, cur, color) :
    i = 1
    for nex, j in v[cur] :
        if nex != pre :
            if i == color :
                i += 1
            ret[j] = i
            dfs(cur, nex, i)
            i += 1

dfs(-1, 0, 0)

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

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

R = {}
for a, b in ab:
  a -= 1
  b -= 1
  if a not in R:
    R[a] = [b]
  else:
    R[a].append(b)
  if b not in R:
    R[b] = [a]
  else:
    R[b].append(a)

D = [0] * N
S = [[0, 0]] 
D[0] = 1
C = {}
m = 0
while S != []:
  t, c = S.pop()
  n = 1
  if c == n:
    n += 1
  m = max(m, len(R[t]))
  for i in R[t]:
    if D[i] == 0:
      D[i] = D[t] + 1
      S.append([i, n])
      if t not in C:
        C[t] = {}
        C[t][i] = n
      else:
        C[t][i] = n
      if i not in C:
        C[i] = {}
        C[i][t] = n
      else:
        C[i][t] = n
      n += 1
      if c == n:
        n += 1

print(m)
for a, b in ab:
  a -= 1
  b -= 1
  print(C[a][b])

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**5+1)
readline = sys.stdin.readline
N, = map(int, readline().split())
G = [[] for _ in range(N+1)]
ees = dict()
for v in range(N-1):
    a, b = map(int, readline().split())
    G[a].append(b)
    G[b].append(a)
    ees[v+1] = tuple([min(a,b), max(a,b)])
cd = dict()
cd[1] = 0
ed = dict()

def itree(v, p):
    cdd = 1
    for c in G[v]:
        if c == p:
            continue
        if cdd == cd[v]:
            cdd += 1
        cd[c] = cdd
        ed[tuple([min(c,v), max(c,v)])] = cdd
        cdd += 1
        itree(c, v)


def process():
    itree(1,0)
process()
xs = []
for i in range(N-1):
    xs.append(ed[ees[i+1]])
print(max(xs))
print("\n".join(map(str,xs)))

Solution (Python):
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
ei = {}
for i,(a,b) in enumerate(AB):
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
    ei[(a,b)] = ei[(b,a)] = i

max_e = root = 0
for i in range(N):
    if len(es[i]) > max_e:
        max_e = len(es[i])
        root = i

ans = [None]*(N-1)
visited = [0]*N
visited[root] = 1
stack = []
for i,to in enumerate(es[root]):
    ans[ei[(root,to)]] = i+1
    visited[to] = 1
    stack.append((to,i+1))

while stack:
    v,pc = stack.pop()
    c = 0
    for to in es[v]:
        if visited[to]: continue
        visited[to] = 1
        c += 1
        if c == pc:
            c += 1
        pi = ei[(v,to)]
        ans[pi] = c
        stack.append((to,c))

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

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

n = int(input())
edge = [[] for i in range(n)]
a = [0] * n
b = [0] * n

color_dict = {}
k = 0

def dfs(x, last = -1, ban_color = -1):
    global k
    color = 1
    for to in edge[x]:
        if to == last:continue
        if color == ban_color:color += 1
        color_dict[(x, to)] = color
        dfs(to, x, color)
        color += 1
    k = max(k, color-1)

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


dfs(0)
print(k)

for i in range(n-1):
    if (a[i], b[i]) in color_dict:
        print(color_dict[(a[i], b[i])])
    else:
        print(color_dict[(b[i], a[i])])

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

n = int(input())
g = [list() for _ in range(n)]
edge = list()
d = dict()
for _ in range(n-1):
    a,b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)
    if a > b:
        a,b = b,a
    edge.append((a,b))
k = max(len(g[i]) for i in range(n))

q = [(0,-1,-1)]
while q:
    v,p,c = q.pop()
    cc = 1
    for x in g[v]:
        if x == p:
            continue
        if cc == c:
            cc += 1
        if v < x:
            d[(v,x)] = cc
        else:
            d[(x,v)] = cc
        q.append((x,v,cc))
        cc += 1
print(k)
for x in edge:
    print(d[x])

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    edge = [[] for i in range(N)]
    e_index = []
    for i in range(N-1):
        a,b = MI_()
        edge[a].append(b)
        edge[b].append(a)
        e_index.append((a,b))
    queue = deque()
    queue.append((0,0))
    ans_col = {}
    visited = set()
    K=1
    while queue:
        from_,col = queue.popleft()
        if from_ in visited:
            continue
        visited.add(from_)
        now = 1
        for to in edge[from_]:
            if to in visited:
                continue
            if now == col:
                now += 1
            ans_col[from_,to] = now
            ans_col[to,from_] = now
            queue.append((to,now))
            K = max(now,K)
            now += 1
    print(K)
    for a,b in e_index:
        print(ans_col[a,b])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())

dic = {}
color = 0

for i in range(N-1):

    a,b = map(int,input().split())

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append([b,i])
    dic[b].append([a,i])

    color = max(color,len(dic[a]),len(dic[b]))

print (color)

q = deque([[1,float("inf")]])
clis = [0] * (N-1)

while len(q) > 0:

    
    now = q.popleft()
    np = now[0]
    ducolor = now[1]
    

    ncolor = 1
    for i in range(len(dic[np])):

        j = i
        if ncolor == ducolor:
            ncolor += 1

        nexp = dic[np][j][0]
        hen = dic[np][j][1]
        if clis[hen] == 0:
            clis[hen] = ncolor
            q.append([nexp,ncolor])
            ncolor += 1

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

Solution (Python):
def solve():
    from collections import deque
    import sys

    input = sys.stdin.readline

    n = int(input())

    g = tuple(set() for _ in range(n))
    for idx in range(n - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add((b, idx))
        g[b].add((a, idx))

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

    e = [-1] * n  
    used = [False] * n
    used[0] = True
    while q:
        v, v_idx, prev_color = q.popleft()
        curr = 1 if prev_color != 1 else 2
        for u, u_idx in g[v]:
            if used[u]:
                continue
            used[u] = True
            e[u_idx] = curr
            q.append((u, u_idx, curr))
            curr += 1
            if curr == prev_color:
                curr += 1

    ret = e[:-1]
    return len(set(ret)), ret


l, ret = solve()
print(l)
print(*ret, sep='\n')