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
from collections import defaultdict

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

def main():
    def dfs(u,pu=-1,pc=-1):
        c=0
        for cu in to[u]:
            if cu==pu:continue
            c+=1
            if c==pc:c+=1
            ei=etoi[(u,cu)]
            e_color[ei]=c
            dfs(cu,u,c)

    to=defaultdict(list)
    n=int(input())
    etoi={}
    for i in range(n-1):
        a,b=map(int1,input().split())
        to[a].append(b)
        to[b].append(a)
        etoi[(a,b)]=etoi[(b,a)]=i
    
    e_color=[-1]*(n-1)
    max_deg_u=max(to.items(),key=lambda x:len(x[1]))[0]
    dfs(max_deg_u)
    print(max(e_color))
    print(*e_color,sep="\n")

main()

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

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

maxp = 0
ce = [0] * n
cr = [0] * (n+1)
for i in range(1, n+1):
  ptr = 1
  while len(ne[i]) != 0:
    if ptr == cr[i]:
      ptr += 1
      continue
    else:
      cur,root = ne[i].pop()
      if ce[cur] == 0:
        ce[cur] = ptr
        cr[root] = ptr
        if ptr > maxp:
          maxp = ptr
        ptr += 1

print(maxp)
for i in range(1, n):
  print(ce[i])

Solution (Python):
from collections import deque

n = int(input())
t = [list() for _ in range(n)]
color = [0] * (n-1)

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

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

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

Solution (Python):
from collections import defaultdict, deque


def pair(a, b):
    return (a, b) if a < b else (b, a)


N = int(input())
E = []
V = defaultdict(list)
C = {}
for i in range(N - 1):
    a, b = map(lambda s: int(s) - 1, input().split())
    E.append((a, b))
    V[a].append(b)
    V[b].append(a)
    C[(a, b)] = 0

K = 1
Q = deque([1])
visited = [False] * N
while Q:
    v = Q.popleft()
    visited[v] = True
    used = []
    to_paint = []
    for nb in V[v]:
        if visited[nb]:
            used.append(C[pair(v, nb)])
        else:
            Q.append(nb)
            to_paint.append(nb)
    i = 0
    for tp in to_paint:
        i += 1
        while i in used:
            i += 1
        C[pair(v, tp)] = i
    K = max(i, K)

print(K)
for e in E:
    print(C[e])

Solution (Python):
def main():
    n=int(input())
    ab=[list(map(int,input().split())) for _ in [0]*(n-1)]
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    [g[b-1].append(a-1) for a,b in ab]
    color=[-1]*n
    color[0]=0
    q=[[0,0]]
    while q:
        qq=[]
        while q:
            i,root=q.pop()
            cnt=1
            for j in g[i]:
                if j==root:
                    continue
                if cnt==color[i]:
                    cnt+=1
                color[j]=cnt
                cnt+=1
                qq.append([j,i])
        q=qq
    print(max(color[1:]))
    for i,j in ab:
        print(color[j-1])
main()

Solution (Python):
from collections import deque

N = int(input())
EhasV = [set() for x in range(N)]
EhasVnums = [0] * N
EE = [0] * (N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    EE[i] = {a,b}
    EhasV[a].add(i)
    EhasV[b].add(i)
    EhasVnums[a] += 1
    EhasVnums[b] += 1

K = len(max(EhasV,key=len))
Vcolor = [set(range(1,EhasVnums[x]+1)) for x in range(N)]
Ecolor = [-1] * (N-1)

q = deque()
q.append(0)
while q:
    v1 = q.pop()
    for e in EhasV[v1]:
        if Ecolor[e] != -1:
            continue
        color = Vcolor[v1].pop()
        Ecolor[e] = color
        edgeside = EE[e]
        edgeside.discard(v1)
        v2 = edgeside.pop()
        Vcolor[v2].discard(color)
        q.append(v2)

print(*([K]+Ecolor),sep='\n')

Solution (Python):


import sys
sys.setrecursionlimit(10000000)

def readInts():
  return [int(s) for s in input().split(" ")]

def next_color(c, exclude):
  if c == exclude:
    return c + 1
  else:
    return c

def traverse(N, edges, k, ans, v, exclude = 0):
  c = next_color(1, exclude)
  for (b, i) in edges[v]:
    ans[i] = c
    traverse(N, edges, k, ans, b, c)
    c = next_color(c + 1, exclude)

def main():
  N = readInts()[0]
  edges = [[] for _ in range(N)]
  counts = [0 for _ in range(N)]
  for i in range(N-1):
    a, b = readInts()
    a -= 1
    b -= 1
    edges[a].append((b, i))
    counts[a] += 1
    counts[b] += 1

  k = max(counts)
  ans = [0 for _ in range(N-1)]
  traverse(N, edges, k, ans, 0)

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

if __name__ == "__main__":
  main()

Solution (Python):

ans = 1


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    

    n = int(input())

    edges = [list() for _ in range(n)]
    colors = [-1] * (n - 1)

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

    def dfs(i, color, pre):
        nc = 0 if color != 0 else 1
        for e in edges[i]:
            if e[0] == pre:
                continue
            global ans
            if ans < len(edges[i]):
                ans = len(edges[i])
            colors[e[1]] = nc
            dfs(e[0], nc, i)
            nc += 1
            if nc == color:
                nc += 1
    dfs(0, -1, -1)
    print(ans)
    for i in colors:
        print(i+1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque








def main():
    N = int(input())
    mawari = [[] for _ in range(N)]
    e_num = [0] * N 
    for l in range(N-1):
        i, j = [int(x)-1 for x in input().split()]
        e_num[i] += 1
        e_num[j] += 1
        mawari[i].append((j, l))
        mawari[j].append((i, l))
    look = -1
    for ind, l in enumerate(e_num):
        if l == 1:
            look = ind
            break
    color = [-1]*(N-1)
    c_prev = deque([-1])
    to_visit = deque([look])
    maxc = 0
    while len(to_visit)>=1:
        look = to_visit.pop()
        c = 0
        prevc = c_prev.pop()
        for i,j in mawari[look]:
            if color[j] != -1:
                continue
            if c == prevc:
                c += 1
            color[j] = c
            c_prev.append(c)
            to_visit.append(i)
            maxc = max(maxc, c)
            c += 1
        
    
    print(maxc+1)
    for i in color:
        print(i+1)












    

main()

Solution (Python):
N = int(input())
E ={i:[] for i in range(N+1)}
ab = []
for i in range(N-1):
  a,b = [int(x)  for x in input().split()]
  ab.append((a,b,i))
  E[a].append((b,i))
  E[b].append((a,i))
visited=[0]*(N+1)
stk = [[1,-1,0]]
ans = [0]*(N-1)
while stk:
  v,p,r = stk.pop()
  if visited[v]:
    continue
  visited[v]=1
  a = 1
  for i,j in E[v]:
    if i!=p:
      if a!=r:
        stk.append([i,v,a])
        ans[j]=a
        a=a+1
      else:
        a=a+1
        stk.append([i,v,a])
        ans[j]=a
        a = a+1
print(max(ans))
for i in range(N-1):
	print(ans[i])

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

N=int(input())
edges = [0 for i in range(N)]
edge_l = [[] for i in range(N)]
cols = [0 for i in range(N)]
out = 0
seen = [False for i in range(N)]
seen2 = [False for i in range(N)]

def paint(cur, parC):
  if seen[cur]:
    return
  curC = 1
  seen[cur] = True
  for e in edge_l[cur]:
    if not seen2[e[1]]:
      seen2[e[1]] = True
      if curC == parC:
        curC+=1
      cols[e[1]] = curC
      paint(e[0], curC)
      curC+=1
  return

for i in range(N-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edges[a]+=1
  edges[b]+=1
  edge_l[a].append([b,i])
  edge_l[b].append([a,i])
  out = max(out,edges[a],edges[b])
print(out)
paint(0,0)
for i in range(N-1):
  print(cols[i])

Solution (Python):
import collections
def main():

    N = int(input())
    edge = [[] for _ in range(N)]
    ncol = 0
    start = None
    graph = collections.defaultdict(list)
    pair = collections.defaultdict(dict)
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(i)
        edge[b-1].append(i)
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        pair[a-1][b-1] = i
        pair[b-1][a-1] = i
        if len(graph[a-1]) > ncol:
            ncol = len(graph[a-1])
            start = a-1
        if len(graph[b-1]) > ncol:
            ncol = len(graph[b-1])
            start = b-1

    n = max(edge)
    cols = [0 for _ in range(N-1)]
    idx = 1
    for i in edge[start]:
        cols[i] = idx
        idx += 1
    visited = set([start])
    m = ncol
    cur = [[h, cols[pair[start][h]]] for h in graph[start]]

    while cur:
        temp = []
        for node, c in cur:
            idx = 1
            for h in graph[node]:
                if cols[pair[node][h]] == 0:
                    if idx == c:
                        idx += 1
                    cols[pair[node][h]] = idx
                    idx += 1
                    temp.append([h, cols[pair[node][h]]])
        cur = temp
    print(m)
    for i in range(N-1):
        print(cols[i])

if __name__ == '__main__':
    main()

Solution (Python):


import itertools


UNDEF = 0


def color_edges(n, edges):
    adj_list = [set() for _ in range(n)]
    for i, (a, b) in enumerate(edges):
        adj_list[a].add(i)
        adj_list[b].add(i)
    colors = [UNDEF] * (n - 1)
    for v in range(n):
        adj_es = adj_list[v]
        num_adj = len(adj_es)
        cur_cols = set(colors[i] for i in adj_es if colors[i] != UNDEF)
        new_cols = set()
        for i in itertools.count(1):
            if len(cur_cols) + len(new_cols) >= num_adj:
                break
            elif i not in cur_cols:
                new_cols.add(i)
        for u in adj_es:
            if colors[u] == UNDEF:
                colors[u] = new_cols.pop()
    return max(colors), colors


def main():
    n = int(input())
    edges = []
    for _ in range(n - 1):
        a, b = (int(z) - 1 for z in input().split())
        edges.append((a, b))
    k, cs = color_edges(n, edges)
    print(k)
    print(*cs, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    a=[0]*(N-1)
    b=[0]*(N-1)
    for i in range(N-1):
        a[i],b[i]=map(int,input().split())
    a_i=np.argsort(a)
    l=[]
    d={1:0}
    p_color=0
    currentcolor=0
    currentnum=0
    K=0
    for i in a_i:
        if a[i]!=currentnum:
            p_color=d[a[i]]
            currentnum=a[i]
            currentcolor=0
        currentcolor+=1
        if currentcolor == p_color:
            currentcolor+=1
        l.append(currentcolor)
        K=max(K,currentcolor)
        d[b[i]]=currentcolor
    print(K)
    l2=[0]*(N-1)
    for i,ai in enumerate(a_i):
        l2[ai]=l[i]
    for z in l2:
        print(z)
    

if __name__ == '__main__':
    main()

Solution (Python):
import collections
n = int(input())
neibors = [dict() for i in range(n + 1)] 
edges = []
for i in range(n-1):
    e = [int(s) for s in input().split()]
    edges.append(e)
for a,b in edges:
    neibors[a][b] = None
    neibors[b][a] =  None

colorCount = 0
for i in range(1,n+1):
    colorCount = max(colorCount, len(neibors[i]))

visited = set()
queue = collections.deque()

visited.add(1)
color = 0
for node in neibors[1]:
    color += 1
    neibors[1][node] = color
    queue.append(node)

while queue:
    x = queue.popleft()
    for node in neibors[x]:
        if node in visited:
            fatherColor = neibors[node][x]
            neibors[x][node] = fatherColor
    color = 0
    for node in neibors[x]:
        if neibors[x][node] is None:
            color += 1
            if color == fatherColor:
                color += 1
            neibors[x][node] = color
            queue.append(node)
    visited.add(x)

print(colorCount)
for a, b in edges:
    print(neibors[a][b])

Solution (Python):
from collections import deque
N = int(input())
g = [[] for _ in range(N)]
d = {}
for i in range(N-1):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
    d[i] = (min(a,b)-1,max(a,b)-1)

q = deque([])
m = 0
s = 0
for i in range(N):
    if len(g[i])>m:
        s = i
        m = len(g[i])
done = [-1]*N
done[s] = 0
ans = {}
cnt = 1
for i in g[s]:
    done[i] = cnt
    ans[(min(i,s),max(i,s))] = cnt
    cnt += 1
    q.append(i)

while q:
    cnt = 1
    i = q.popleft()
    for j in g[i]:
        if done[j]==-1:
            if done[i]==cnt:
                cnt += 1
            ans[min(i,j),max(i,j)] = cnt
            done[j] = cnt
            cnt += 1
            q.append(j)
m = 0
for k in ans:
    m = max(m,ans[k])
print(m)
for i in range(N-1):
    print(ans[d[i]])

Solution (Python):
from collections import deque         
N = int(input())
G = {}
E = {}
E1 = []
for _ in range(N-1):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
    E[(a,b)] = 0
    E[(b,a)] = 0
    E1.append((a,b))
col = 0
for x in G:
    col = max(col,len(G[x]))
hist = [0 for _ in range(N+1)]
heap = deque([(1,0)])
while heap:
    x = heap.popleft()
    hist[x[0]] = 1
    if x[1]!=0:
        c = E[(x[0],x[1])]
    else:
        c = 0
    for y in G[x[0]]:
        if hist[y]==0:
            c = c%col+1
            E[(x[0],y)] = c
            E[(y,x[0])] = c
            heap.append((y,x[0]))
print(col)
for i in range(N-1):
    print(E[E1[i]])

Solution (Python):
from collections import defaultdict
N = int(input())
dic = defaultdict(list)
ls = []
for i in range(N-1):
  a, b = map(int, input().split())
  dic[a-1] += [(b-1, i)]
  dic[b-1] += [(a-1, i)]
  ls += [(a-1,b-1)]
K = 0
for k in dic.keys():
  if K<len(dic[k]):
    K = len(dic[k])

print(K)
log = [1]*N
ls = [0]*N
stuck = [(0, 0)]
log[0] = 0
ls[0] = 1
ans = [0]*(N-1)
while stuck:
  e, i = stuck.pop()
  b = 1
  for j in range(len(dic[e])):
    ce, h = dic[e][j]
    if log[ce]:
      log[ce] = 0
      ans[h] = (ls[e]+b)%K
      ls[ce] = (ls[e]+b)%K

      b += 1
      stuck += [(ce,h)]
      
for x in ans:
  if x==0:
    print(K)
  else:
    print(x)

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

ans=[0]*(N-1)


stack=[]

stack.append([0,-1,0])
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
  parentcolor=node[2]
  childs=EV[v]
  color=1
  
  for i in range(len(childs)):
    child=childs[i]
    child_v=child[0]
    if child_v==parent:
      continue
    if color==parentcolor:
      color+=1
    childs[i][1]=color
    position=child[2]
    if position!=-1:
      ans[position]=color
    stack.append([child_v,v,color])
    color+=1
    

print(max(ans))
for i in range(len(ans)):
  print(ans[i])

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

N=int(input())

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

def bfs(x, c, b):
    if seen[x]:
        return
    seen[x] = True
    if b!=-1:
        global k
        color[b] = c
        k = max(k,c)
    t = 1
    for i,b in G[x]:
        if t==c:
            t+=1
        if not(seen[i]):
            bfs(i,t,b)
            t+=1

seen = [False]*N
color = [0]*N
k=0
bfs(0, 0, -1)


print(k)
print(*color[:-1],sep='\n')

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)
        
    s = [(1, -1)]
    done = set([1])
    K = 1
    ans = {}
    while s:
        u, c = s.pop()
        used = set([c])
        c = 1
        for v in g[u]:
            if v in done:
                continue
            while c in used:
                c += 1 
                K = max(K, c)
            used.add(c)
            s.append((v, c))
            i, j = min(u, v), max(u, v)
            ans[(i, j)] = c
            done.add(v)
    print(K)
    for a, b in AB:
        print(ans[(a, b)])
    


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    (slv(N, AB))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
graph = [[] for i in range(n)]
irohash = {}
irojyun = []
for i in range(n-1):
    a,b = list(map(int,input().split()))
    a -= 1;b -= 1
    graph[a].append(b)
    graph[b].append(a)
    s = str(min(a,b)) + "," + str(max(a,b))
    irohash[s] = -1
    irojyun.append(s)


ii = 0
for i in range(n):
    if len(graph[i]) == 1:
        ii = i
        break


iro = max([len(i) for i in graph])
stack = [[ii,graph[ii][0]]]
s = str(min(ii,graph[ii][0])) + "," + str(max(ii,graph[ii][0]))
irohash[s] = 1
while stack:
    oo = stack.pop()
    b,p = oo[0],oo[1]
    s = str(min(b,p)) + "," + str(max(b,p))
    piro = irohash[s]
    count = 1
    for v in graph[p]:
        s = str(min(p,v)) + "," + str(max(v,p))
        if irohash[s] != -1:continue
        if count == piro:count += 1
        irohash[s] = count
        stack.append([p,v])
        count += 1
print(iro)
for i in range(n-1):
    print(irohash[irojyun[i]])

Solution (Python):
import sys
from collections import deque
input = sys.stdin.buffer.readline
from collections import defaultdict
N = int(input())
g = defaultdict(list)
color = defaultdict(int)
gn = [0]*(N+1)
edges = []
for i in [0]*(N-1):
    a,b = map(int,input().split())
    edges.append((a,b))
    g[a].append(b)
    g[b].append(a)
    gn[a]+= 1
    gn[b]+= 1

M = max(gn)

dq = deque([1])
visited = [False] * (N+1)
ncolor = [-1]*(N+1)
ncolor[1] = 0
while dq:
    s = dq.popleft()
    visited[s] = True
    s_clr = ncolor[s]
    for t in g[s]:
        if not visited[t]:
            s_clr = (s_clr + 1) % M
            ncolor[t] = s_clr
            if s < t:
                color[(s,t)] = s_clr
            else:
                color[(t,s)] = s_clr
            dq.append(t)
print(M)
for edge in edges:
    print(color[edge]+1)

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

n = int(input())
edges = [[] for _ in range(n)]

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

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

q = [0]
visit = [False] * n
visit[0] = True

while q:
    l = q.pop(-1)
    li = []
    for i,j in edges[l]:
        if not visit[i]:
            q.append(i)
            visit[i] = True
        li.append(j)
    li = list(set(li))
    li2 = []
    for i in li:
        li2.append(ans[i])
    li2.sort()
    if li2[0] == -1:
        li2 = li2[1:]
    count = 1
    for i in li:
        while ans[i] == -1:
            if count not in li2:
                ans[i] = count
            count += 1

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

Solution (Python):
from collections import defaultdict

def bfs(i, V, E, Ec):
    V[i] = 1
    Q = [(i, 0)]
    while(True):
        Qi = []
        for q, cq in Q:
            c = 1
            for j, idx in E[q]:
                if V[j] == 0:
                    if cq == c:
                        c += 1

                    V[j] = 1
                    Qi.append((j, c))
                    Ec[idx] = c
                    c += 1
        if len(Qi) == 0:
            break
        else:
            Q = Qi
    return V, Ec


n = int(input())
E = defaultdict(list)
for i in range(n - 1):
    a, b = map(int, input().split())
    E[a].append((b, i))
    E[b].append((a, i))
Ec = [None for _ in range(n - 1)]
V = [0 for _ in range(n + 1)]
_, Ec = bfs(1, V, E, Ec)
print(max(Ec))
for c in Ec:
    print(c)

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

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

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

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

N = int(input())
P = [[] for i in range(N)]
ans = [0] * (N - 1)

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


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

while len(q) > 0:
    c, n = q.popleft()
    ac = 1
    for l, i in P[n]:
        if ac == c:
            ac += 1
        q.append((ac, l))
        ans[i] = ac
        ac += 1

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

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


N = int(input())
AB = [list(map(int,input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for i in range(N-1):
    adj[AB[i][0]-1].append([AB[i][1]-1,i])
    adj[AB[i][1]-1].append([AB[i][0]-1,i])


col = [0]*(N-1)
visited = [False] * N
visited[0] = True
def dfs(v, color):
    child = adj[v]
    ctmp = 1
    for u,idx in child:
        if not(visited[u]):
            if ctmp == color:
                ctmp += 1
            col[idx] = ctmp
            visited[u] = True
            dfs(u,ctmp)
            ctmp += 1
    return 
            
    
    
    

dfs(0,0)
K = max(col)
print(K)
for k in col:
    print(k)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    idx={}
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)
        idx[(a,b)]=i

    ans=[None]*(n-1)
    k=max(len(E[v]) for v in range(n))

    
    Q=[0]
    while(Q):
        v=Q.pop()
        if(v):
            p=min(E[v]) 
            c=ans[idx[(p,v)]] 
        cnt=1
        for nv in E[v]:
            if(v==0):
                ans[idx[(v,nv)]]=cnt
                cnt+=1
                Q.append(nv)
            else:
                if(cnt==c): cnt+=1
                if(nv==p): continue
                ans[idx[(v,nv)]]=cnt
                cnt+=1
                Q.append(nv)

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

resolve()

Solution (Python):
N=int(input())
E=[tuple(sorted(map(int,input().split()))) for i in range(N-1)]

EDICT={x:ind for ind,x in enumerate(E)}

ELIST=[[] for i in range(N+1)]
ED=[0]*(N+1)

for x,y in E:
    ELIST[x].append(y)
    ELIST[y].append(x)
    ED[x]+=1
    ED[y]+=1

MAX=max(ED)
print(MAX)

from collections import deque

Q=deque()
Q.append(1)

USED=[0]*(N+1)

ANS=[-1]*(N-1)
count=1
BAN=[set() for i in range(N+1)]

while Q:
    x=Q.pop()
    USED[x]=1

    for to in ELIST[x]:
        if USED[to]==1:
            continue

        while count in BAN[x] or count in BAN[to]:
            count=count%MAX+1
            
        ANS[EDICT[tuple(sorted([x,to]))]]=count
        BAN[x].add(count)
        BAN[to].add(count)
        Q.append(to)

for a in ANS:
    print(a)

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

n = int(input())

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

m_node = 0
for e in nodes:
    m_node = max(len(e), m_node)

use_node = [0 for i in range(n)]
dic = {}
def dfs(node, start_color):
    use_node[node] = 1
    for e in nodes[node]:
        if use_node[e] == 0:
            dic[(node,e)] = (start_color%m_node)+1
            dic[(e,node)] = (start_color%m_node)+1
            dfs(e, (start_color%m_node)+1)
            start_color += 1

dfs(0,0)
print(m_node)
for a,b in abl:
    print(dic[(a-1,b-1)])

Solution (Python):


def main():
    N = int(input())
    AB = [tuple(map(int, input().split())) for _ in range(N-1)]
    
    nodes = [[] for _ in range(N+1)]

    for a, b in AB:
        nodes[a].append(b)
        nodes[b].append(a)

    K = max(map(lambda x: len(x), nodes))
    print(K)
    C = {}

    Q = [(1, None, None)]
    while len(Q) > 0:
        nodeIdx, parent, parentNodeColor = Q.pop()
        colorIdx = 1
        
        for subNodeIdx in nodes[nodeIdx]:
            if subNodeIdx == parent:
                continue

            if colorIdx == parentNodeColor:
                colorIdx += 1

            C[(nodeIdx, subNodeIdx)] = colorIdx
            Q.append((subNodeIdx, nodeIdx, colorIdx))
            colorIdx += 1

    for a, b in AB:
        if (a, b) in C:
            print(C[(a, b)])
        else:
            print(C[(b, a)])



if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
n = int(input())

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, i))
    g[b].append((a, i))

k = 0

memo = [-1] * (n-1)
used = [0] * n


q = deque([(0, 0)])
used[0] = 1
while q:
    v, used_number = q.popleft()
    mark = 1
    for nv, i in g[v]:
        if used[nv] > 0:
            continue
        if mark == used_number:
            mark += 1
        k = max(k, mark)
        used[nv] = 1
        memo[i] = mark
        q.append((nv, mark))
        mark += 1
        

print(k)
for m in memo:
    print(m)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
mlmis = lambda: [-int(x) for x in input().split()]
INF = float('inf')
def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok



def main():
    N = ii()
    class Edge:
        def __init__(self, a, b):
            self.a = a
            self.b = b
            self.color = None
        def get_con(self, i):
            return self.b if self.a==i else self.a
    edges = []
    tree = tuple([] for _ in range(N))
    for _ in range(N-1):
        a, b = mis()
        a -= 1
        b -= 1
        edge = Edge(a, b)
        edges.append(edge)
        tree[a].append(edge)
        tree[b].append(edge)
    tasks = [(0, 0)]
    max_color = 1
    for used, node in tasks:
        color = 1
        for edge in tree[node]:
            if color == used:
                color += 1
            if edge.color is not None:
                continue
            edge.color = color
            tasks.append((color, edge.get_con(node)))
            max_color = max(max_color, color)
            color += 1
    print(max_color)
    for edge in edges:
        print(edge.color)



main()

Solution (Python):

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()




























from collections import defaultdict, deque
tree = defaultdict(lambda: [])
inputls = []
ans = dict()
for _ in range(N - 1):
    a, b = read_ints()
    inputls.append((a, b))
    tree[a].append(b)  
    ans[(a, b)] = 0  


que = deque([(1, 0)])  
defcolor = 1
while que:
    cur, pre_color = que.popleft()
    cur_color = defcolor
    for nx in tree[cur]:
        if cur_color == pre_color:
            cur_color += 1

        que.append((nx, cur_color))
        ans[(cur, nx)] = cur_color
        cur_color += 1


print(max(ans.values()))
for a, b in inputls:
    print(ans[(a, b)])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append( [b, i])
    graph[b].append( [a, i])

maxc = 0

nexts = [1]
color = [0] * (n-1)
while len(nexts) > 0:
    target = nexts.pop()
    used = set()
    fillable = set()
    for i in range(len(graph[target])):
        cr = color[graph[target][i][1]]
        if cr == 0:
            fillable.add(i)
        else:
            used.add(cr)
    mins = 1
    for i in list(fillable):
        while mins in used:
            mins += 1
        color[graph[target][i][1]] = mins
        nexts.append(graph[target][i][0])
        if mins > maxc:
            maxc = mins
        mins += 1

print(maxc)
for i in color:
    print(i)