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
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    P=[-1]*N
    C=[0]*(N-1)
    adj=[[]for _ in range(N)]
    
    from collections import defaultdict
    dd = defaultdict(lambda : -1)
    dd2 = defaultdict(lambda : -1)
    
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
        
        dd[(a,b)] = i
        dd2[i]=(a,b)
        
    
    import queue
    q=queue.Queue()
    q.put((0,-1))
    
    while not q.empty():
        v,p=q.get()
        
        col=0
        for i in range(len(adj[v])):
            nv=adj[v][i]
            
            if nv==p:
                continue
            
            if col==P[v]:
                col+=1
            
            a=min(v,nv)
            b=max(v,nv)
            ii=dd[(a,b)]
            C[ii]=col
            P[nv]=col
            col+=1
            
            q.put((nv,v))
            
    K=0
    for i in range(N):
        K=max(K,len(adj[i]))
    
    print(K)
    for i in range(N-1):
        print(C[i]+1)

            
    
    
    

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n = int(input())
ab = []
t = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(lambda x:int(x)-1,input().split())
  t[a].append(b)
  t[b].append(a)
  ab.append((min(a,b),max(a,b)))
k = max(map(len,t))
d = {}
def dfs(pre,cur,col):
  cn = 1 if col != 1 else 2
  for i in t[cur]:
    if i == pre:
      continue
    d[(min(i,cur),max(i,cur))] = cn
    dfs(cur,i,cn)
    cn += 1
    if col == cn:
      cn += 1
dfs(0,0,0)
print(k)
for i in ab:
  print(d[i])

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

ans = [0] * (N-1)
to = [[] for i in range(N-1)]
used = [0] * N

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

for i in range(N-1):
    unable = used[i]
    c = 1
    for j, id in to[i]:
        if c == unable:
            c += 1
        ans[id] = c
        used[j] = c
        c += 1

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

Solution (Python):
N = int(input())
from collections import deque
inp = []
for k in range(N-1):
  a, b = map(int, input().split())
  if a > b:
    a, b = b-1, a-1
  else:
    a, b = a-1, b-1
  inp.append((a, b, k))
inp.sort(key = lambda x: x[0])
inp = deque(inp)
mark = [[] for _ in range(N)]
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    
    return False

from bisect import insort
ans = [0 for _ in range(N-1)]
now = 0
cnt = 0
while inp:
  item = inp.popleft()
  cnt += 1
  if now < item[0]:
    now = item[0]
    cnt = 1
  while binary_search(mark[item[0]], cnt) or binary_search(mark[item[1]], cnt):
    cnt += 1
  insort(mark[item[1]], cnt)
  ans[item[2]] = cnt
color = max(ans)
print(color)
for k in range(N-1):
  print(ans[k])

Solution (Python):
N = int(input())
inp = []
for k in range(N-1):
  a, b = map(int, input().split())
  if a > b:
    a, b = b-1, a-1
  else:
    a, b = a-1, b-1
  inp.append((a, b, k))
inp.sort(key = lambda x: x[0])
mark = [[] for _ in range(N)]
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    
    return False

from bisect import insort


ans = [0 for _ in range(N-1)]
now = 0
cnt = 0
for item in inp:
  cnt += 1
  if now < item[0]:
    now = item[0]
    cnt = 1
  while binary_search(mark[item[0]], cnt) or binary_search(mark[item[1]], cnt):
    cnt += 1
  insort(mark[item[1]], cnt)
  ans[item[2]] = cnt
color = max(ans)
print(color)
for k in range(N-1):
  print(ans[k])

Solution (Python):
N = int(input())
inp = []
for k in range(N-1):
  a, b = map(int, input().split())
  if a > b:
    a, b = b-1, a-1
  else:
    a, b = a-1, b-1
  inp.append((a, b, k))
inp.sort(key = lambda x: x[0])
mark = [[] for _ in range(N)]
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    
    return False

from bisect import insort


ans = [0 for _ in range(N-1)]
now = 0
cnt = 0
for item in inp:
  cnt += 1
  if now < item[0]:
    now = item[0]
    cnt = 1
  while binary_search(mark[item[0]], cnt) or binary_search(mark[item[1]], cnt):
    cnt += 1
  insort(mark[item[1]], cnt)
  ans[item[2]] = cnt
color = max(ans)
print(color)
for k in range(N-1):
  print(ans[k])

Solution (Python):
N = int(input())
inp = []
for k in range(N-1):
  a, b = map(int, input().split())
  if a > b:
    a, b = b-1, a-1
  else:
    a, b = a-1, b-1
  inp.append((a, b, k))
inp.sort(key = lambda x: x[0])
mark = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]
now = 0
cnt = 0
for item in inp:
  cnt += 1
  if now < item[0]:
    now = item[0]
    cnt = 1
  while cnt in mark[item[0]] or cnt in mark[item[1]]:
    cnt += 1
  mark[item[1]].append(cnt)
  mark[item[0]].append(cnt)
  ans[item[2]] = cnt
color = max(ans)
print(color)
for k in range(N-1):
  print(ans[k])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N = int(input())

class vertex:
  def __init__(self,i):
    self.__i = i
    self.__e = []
    self.__d = 0
    self.__nei = []
  def add_e(self, e):
    self.__e.append(e)
    self.__d += 1
    self.__nei.append(e.get_pair_v(self.__i))
  def get_e(self):
    return self.__e
  def get_d(self):
    return self.__d
  def get_i(self):
    return self.__i
  def get_n(self):
    return self.__nei
  
class edge:
  def __init__(self, i, a, b):
    self.__i = i
    self.__c = -1
    self.__v = dict()
    self.__v[a] = b
    self.__v[b] = a
  def get_pair_v(self, a):
    return self.__v[a]
  def get_c(self):
    return self.__c
  def set_c(self, a):
    if self.__c == -1:
      self.__c = a
      return True
    else:
      return False
  def get_i(self):
    return self.__i
    
class tree:
  def __init__(self,N):
    self.__v = [vertex(i) for i in range(N+1)]
    self.__e = []
    self.__max_d = 0
    self.__max_v_idx = 0
    
  def add_e(self,i, a, b):
    ed = edge(i, a, b)
    self.__e.append(ed) 
    self.__v[a].add_e(ed)
    self.__v[b].add_e(ed)
  
  def reload_max_d(self):
    for i in self.__v:
      if i.get_d() > self.__max_d:
        self.__max_d = i.get_d()
        self.__max_v_idx = i.get_i()
        
  def painting(self):
    v = self.__max_v_idx
    edges = self.__v[v].get_e()
    for i, ver in enumerate(edges):
      ver.set_c(i+1)
      self.change_c(ver.get_pair_v(v),ver)   
    
  def change_c(self, idx, prev_e):
    edges = self.__v[idx].get_e()
    edges.remove(prev_e)
    offset = 0
    prev_e_c = prev_e.get_c()
    if not edges:
      return
    for ver in edges:
      offset += 1
      if offset == prev_e_c:
        offset += 1
      if ver.set_c(offset):
        self.change_c(ver.get_pair_v(idx),ver)   
  
  def show_max_d(self):
    print(self.__max_d)
    
  def show_colors(self):
    for i in self.__e:
      print(i.get_c()) 

t = tree(N)
for i in range(N-1):
  temp = list(map(int, input().split()))
  t.add_e(i, temp[0], temp[1])
t.reload_max_d()
t.painting()
t.show_max_d()
t.show_colors()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
edge_colors = [0]*(N-1)
g = [[] for _ in range(N)]
for i, (a, b) in enumerate(ab):
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))

q = deque([(0, 0)])
visited = [False] * N
visited[0] = True
while len(q) > 0:
    node, color = q.popleft()
    i = 1
    for v, edgeid in g[node]:
        if visited[v]:
            continue
        if i == color:
            i += 1
        visited[v] = True
        q.append((v, i))
        edge_colors[edgeid] = i
        i += 1


print(max(edge_colors))
for c in edge_colors:
    print(c)

Solution (Python):
from collections import deque

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

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

color = max([len(x) for x in graph])
print(color)

check = [False] * n
check[0] = True
DQ = deque()
DQ.append(0)

tree = [set() for i in range(n)]

while DQ:
    now = DQ.popleft()
    for node in graph[now]:
        if check[node] == False:
            check[node] = True
            tree[now].add(node)
            DQ.append(node)

memo = [False] * n
memo[0] = -1
DQ = deque()
DQ.append(0)

while DQ:
    now = DQ.popleft()
    if now == 0:
        c = 1
        for node in tree[now]:
            DQ.append(node)
            memo[node] = c
            c += 1
    else:
        c = 1
        for node in tree[now]:
            DQ.append(node)
            if c == memo[now]:
                c += 1
                memo[node] = c
                c += 1
            else:
                memo[node] = c
                c += 1

for a, b in edge:
    if a in tree[b]:
        print(memo[a])
    else:
        print(memo[b])

Solution (Python):
import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

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, itr):
        self.graph[start].append((end, itr))
        self.graph[end].append((start, itr))
    
    def BFS(self, start):
        from collections import deque
        dist = [-1] * self.v
        ret = [0] * (self.v-1)
        que = deque()
        que.append((start, -1))
        dist[start] = 0
        while que:
            now, _color = que.popleft()
            color = 1
            if _color == color: color += 1
            for to, itr in self.graph[now]:
                if dist[to] == -1:
                    que.append((to, color))
                    dist[to] = dist[now] + 1
                    ret[itr] = color
                    color += 1
                    if color == _color: color += 1
        return ret
    
    def color_types(self):
        ret = len(self.graph[0])
        for x in self.graph[1:]:
            ret = max(ret, len(x))
        return ret

def Main():
    n = read_int()
    g = Graph(n)
    for i in range(n - 1):
        a, b = read_ints()
        g.addEdge(~-a, ~-b, i)
    print(g.color_types())
    print(*g.BFS(0), sep='\n')

if __name__ == '__main__':
    Main()

Solution (Python):
n = int(input())
A = []
g  =[[] for _ in range(n+1)]
ans = {}
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    A.append([a,b])
 
 
from collections import deque
 
q = deque()
q.append(1)
 
color = [-1]*(n+1)
color[1] = 0
cnt = 0
 
while q:
    v = q.popleft()
    p = 1
    for u in g[v]:
        if p==color[v]:
            p += 1
        color[u] = p
        ans[v,u] = p
        q.append(u)
        cnt = max(cnt,p)
        p += 1
print(cnt)
 
for i in range(n-1):
    tmp = (A[i][0],A[i][1])
    print(ans[tmp])

Solution (Python):
if __name__ == "__main__":
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        edges[a].append((b,i))
        edges[b].append((a,i))

    color = [None]*(N-1)
    SIZE = 1
    q = deque([(0,None)])
    while q:
        v, prev_color = q.popleft()
        c = 1
        for w, i in edges[v]:
            if not color[i]:
                if c == prev_color:
                    c += 1
                color[i] = c
                c += 1
                q.append((w,color[i]))
        SIZE = max(SIZE, c-1)
    print(SIZE)
    for n in range(N-1):
        print(color[n])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append([b,i])
        edge[b].append([a,i])
    color = [0] * (N-1)
    def dfs(s,p,c):
        tmp_c = 1
        for v, num in edge[s]:
            if v == p:
                continue
            if tmp_c == c:
                tmp_c += 1
            color[num] = tmp_c
            dfs(v,s,tmp_c)
            tmp_c += 1
    dfs(0,-1,0)
    print(max(color))
    for c in color:
        print(c)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    edge = [-1] * (N-1)
    for i in range(N-1):
        a, b = (int(i)-1 for i in input().split())
        G[a].append(b*N + i)
        G[b].append(a*N + i)

    max_deg = max(len(G[i]) for i in range(N))

    from collections import deque

    def bfs(s):
        que = deque([])
        par = [-1]*N
        que.append(s)
        while que:
            pos = que.popleft()
            c = -1
            k = 1
            for vi in G[pos]:
                v, i = divmod(vi, N)
                if par[pos] == v:
                    c = edge[i]
            for vi in G[pos]:
                v, i = divmod(vi, N)
                if par[pos] == v:
                    continue
                if k == c:
                    k += 1
                par[v] = pos
                edge[i] = k
                k += 1
                que.append(v)

    bfs(0)

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


if __name__ == '__main__':
    main()

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

    max_deg = max(len(G[i]) for i in range(N))

    from collections import deque

    def bfs(s):
        que = deque([])
        par = [-1]*N
        que.append(s)
        while que:
            pos = que.popleft()
            c = -1
            k = 1
            for (v, i) in G[pos]:
                if par[pos] == v:
                    c = edge[i]
            for (v, i) in G[pos]:
                if par[pos] == v:
                    continue
                if k == c:
                    k += 1
                par[v] = pos
                edge[i] = k
                k += 1
                que.append(v)

    bfs(0)

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


if __name__ == '__main__':
    main()

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

    max_deg = max(len(G[i]) for i in range(N))

    from collections import deque

    def bfs(s):
        que = deque([])
        par = [-1]*N
        color = [-1]*N
        que.append(s)
        c = 1
        while que:
            pos = que.popleft()
            for (v, i) in G[pos]:
                if par[pos] == v:
                    continue
                if color[pos] == c:
                    c += 1
                    if max_deg < c:
                        c = 1
                par[v] = pos
                edge[i] = c
                color[v] = c
                c += 1
                if max_deg < c:
                    c = 1
                que.append(v)

    bfs(0)

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**5)
    N = int(input())
    G = [[] for _ in range(N)]
    edge = [-1] * (N-1)
    for i in range(N-1):
        a, b = (int(i)-1 for i in input().split())
        G[a].append((b, i))
        G[b].append((a, i))

    max_deg = max(len(G[i]) for i in range(N))

    def dfs(s, c=-1, p=-1):
        
        cur_color = 1
        for (v, i) in G[s]:
            if v == p:
                continue
            if c == cur_color:
                cur_color += 1
            edge[i] = cur_color
            dfs(v, edge[i], s)
            cur_color += 1
        

    dfs(0)

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


if __name__ == '__main__':
    main()

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

def bfs():
    q = deque([(0, -1)])
    visited = [False]*N
    visited[0] = True
    ans = [-1]*(N-1)

    while q:
        v, prev = q.popleft()
        now = 0

        for nv in G[v]:
            if not visited[nv]:
                if now==prev:
                    now += 1

                visited[nv] = True
                ans[idx[(min(v, nv), max(v, nv))]] = now
                q.append((nv, now))
                now += 1

    return ans

N = int(input())
G = [[] for _ in range(N)]
idx = defaultdict(int)

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

ans = bfs()
print(max(ans)+1)

for ans_i in ans:
    print(ans_i+1)

Solution (Python):
from collections import deque
N = int(input())
A = [[] for i in range(N)]
B = []
for i in range(N-1):
  a = list(map(int, input().split()))
  A[a[0]-1].append([a[1]-1, 0])
  A[a[1]-1].append([a[0]-1, 1])
  B.append(a)
K = 0
D = {}
C = [0 for i in range(N)]
de = deque([[0, -1]])
while len(de):
  n = de.pop()
  C[n[0]] = 1
  color = 1
  for a in A[n[0]]:
    if C[a[0]] == 1:
      continue
    if color == n[1]:
      color += 1
    if a[1] == 0:
      D[str(n[0])+","+str(a[0])] = color
    else:
      D[str(a[0])+","+str(n[0])] = color
    de.append([a[0], color])
    K = max(K, color)
    color += 1
print(K)
for b in B:
  print(D[str(b[0]-1)+","+str(b[1]-1)])

Solution (Python):


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

g = dict()
for i, (a, b) in enumerate(AB):
    a, b = a-1, b-1
    if a not in g:
        g[a] = set()
    if b not in g:
        g[b] = set()
    g[a].add((b, i))
    g[b].add((a, i))

col = [-1]*N
col[0] = -2
e_col = [-1]*(N-1)

q = [0]
while q:
    par = q.pop()
    par_col = col[par]

    c = 0
    for child, e_i in g[par]:
        
        if col[child] != -1:
            continue
        while c == par_col:
            c += 1
        e_col[e_i] = c
        col[child] = c
        c += 1
        q.append(child)




print(max(e_col)+1)
for e_col_i in e_col:
    print(e_col_i+1)

Solution (Python):

import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    graph = [[] for i in range(N)]
    prev = [-1 for i in range(N)]
    colors = {}
    edges = []
    for _ in range(N-1):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        edges.append([a-1, b-1])
    max_edge = 0
    max_edge_idx = -1
    for i in range(len(graph)):
        length = len(graph[i])
        if length >= max_edge:
            max_edge = length
            max_edge_idx = i

    deque = cl.deque([max_edge_idx])
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        pre_key = (target, pre) if target < pre else (pre, target)
        used_color = 0
        if pre != -1:
            used_color = colors[pre_key]

        connecteds = graph[target]
        color = 1
        for connected in connecteds:
            key = (target, connected) if target < connected else (
                connected, target)
            if key in colors:
                continue
            if color == used_color:
                color += 1
            colors[key] = color
            prev[connected] = target
            deque.append(connected)
            color += 1

    print(max_edge)

    for edge in edges:
        print(colors[(edge[0], edge[1])])


main()

Solution (Python):
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    edge_order = [0]*(N-1)
    for i in range(N-1):
        a, b = (int(i)-1 for i in input().split())
        G[a].append(b)
        G[b].append(a)
        edge[a*N + b] = -1  
        edge_order[i] = a*N + b
    
    
    
    
    
    max_deg = max(len(G[i]) for i in range(N))

    from collections import deque

    def bfs(s):
        que = deque([])
        par = [-1]*N
        par_color = [-1]*N
        c = 0
        que.append(s)
        while que:
            pos = que.popleft()
            for v in G[pos]:
                if par[pos] == v:
                    continue
                if par_color[pos] == c:
                    c += 1
                    if c == max_deg:
                        c = 0
                if pos < v:
                    edge[pos * N + v] = c
                else:
                    edge[v * N + pos] = c
                par[v] = pos
                par_color[v] = c
                que.append(v)
                c += 1
                if c == max_deg:
                    c = 0

    bfs(0)

    print(max_deg)
    for i in range(N-1):
        print(edge[edge_order[i]] + 1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())
tree = [[] for i in range(N)]
edges = []

for i in range(N - 1):
    edges.append(tuple(map(int, input().split())))
    tree[edges[-1][0] - 1].append(edges[-1][1] - 1)
    tree[edges[-1][1] - 1].append(edges[-1][0] - 1)

coloring = {}
c_max = 1

color_used = [0]*N
v_dist = [-1]*N

queue = deque([0])
v_dist[0] = 0

while queue:
    v = queue.popleft()
    
    c = 1
    for n_v in tree[v]:
        if v_dist[n_v] < 0:
            v_dist[n_v] = v_dist[v] + 1

            if color_used[v] == c:
                c += 1
            
            coloring[(v, n_v)] = c
            coloring[(n_v, v)] = c
            color_used[n_v] = c
            queue.append(n_v)

            c += 1
    
    c_max = max(c_max, c)

print(c_max - 1)

for edge in edges:
    print(coloring[(edge[0]-1, edge[1]-1)])

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(10**8)

N = int(input())
graph = [[] for _ in range(N)]
numOfEdges = [0 for _ in range(N)]
visited = [0 for _ in range(N)]
edges = defaultdict(int)

for i in range(1, N):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    numOfEdges[a] += 1
    numOfEdges[b] += 1
    edges[(a, b)] = 0
    graph[a].append(b)
    graph[b].append(a)

def dfs(prev, now, col):
    if visited[now]:
        return
    visited[now] = 1
    i = 1
    for adj in graph[now]:
        if adj == prev:
            continue
        if now < adj:
            edges[(now, adj)] = col + i
        else:
            edges[(adj, now)] = col + i
        dfs(now, adj, col+i)
        i += 1

dfs(-1, 0, 1)
maxColor = max(numOfEdges)
print(maxColor)

for k, i in edges.items():
    e = i % maxColor
    if e:
        print(e)
    else:
        print(maxColor)

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

from collections import deque

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

print(max(color))
for e in edge:
    print(color[e])

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

def dfs(v,c):
  now = 1
  for u,i in edge[v]:
    if color[i]==0:
      if now==c:
        now += 1
      color[i] = now 
      dfs(u,now)
      now += 1
  return 0

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  edge[a-1].append([b-1,i])
  edge[b-1].append([a-1,i])
color = [0]*(N-1)
dfs(0,1<<30)
print(max(color))
print(*color, sep='\n')

Solution (Python):
n = int(input())
A = []
g  =[[] for _ in range(n+1)]
ans = {}
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    A.append([a,b])


from collections import deque

q = deque()
q.append(1)

color = [-1]*(n+1)
color[1] = 0
cnt = 0

while q:
    v = q.popleft()
    p = 1
    for u in g[v]:
        if p==color[v]:
            p += 1
        color[u] = p
        ans[v,u] = p
        q.append(u)
        cnt = max(cnt,p)
        p += 1
print(cnt)

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

Solution (Python):
import sys

sys.setrecursionlimit(100000)

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    ID = [dict() for _ in range(n)]
    for i in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)
        G[b].append(a)
        ID[a][b] = i
        ID[b][a] = i
    m = max(len(g) for g in G)
    ans = [0] * (n - 1)
    def bfs(a, pre = -1, pre_c = -1):
        color = 1
        for b in G[a]:
            if b == pre: continue
            if color == pre_c: color += 1
            ans[ID[a][b]] = color
            bfs(b, a, color)
            color += 1

    bfs(0)
    print(m)
    [print(a) for a in ans]
      
if __name__ == '__main__':
    main()

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd


n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))

node=[[] for _ in range(n)]
k=0
used=[-1]*n
seen=[-1]*n
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])
    k=max(k,len(node[pair[0]]),len(node[pair[1]]))
print(k)
ans={}
d=deque()
d.append(0)
while d:
    i=d.pop()
    seen[i]=1
    res=1
    for j in node[i]:
        if seen[j]==1:
            continue
        d.appendleft(j)
        if res!=used[i]:
            ans[(i,j)]=res
        else:
            res+=1
            ans[(i,j)]=res
        used[j]=res
        res+=1
for pair in v:
    a,b=pair
    if (a,b) in ans:
        print(ans[(a,b)])
    else:
        print(ans[(b,a)])

Solution (Python):
n=int(input())
kotaezyun=[]
renketu=[[] for i in range(n+1)]
ans_dict={}
for i in range(n-1):
    a,b=map(int, input().split())
    renketu[a].append(b)
    kotaezyun.append([a,b])

from collections import deque
que=deque()

que.append(1)

iro=[-1]*(n+1)
iro[1]=0
irokazu=0

tansaku_moto=[1]

while que:
    tansaku_moto=que.popleft()
    ironuri=1
    for tansaku_saki in renketu[tansaku_moto]:
        if ironuri==iro[tansaku_moto]:
            ironuri+=1
        iro[tansaku_saki]=ironuri
        ans_dict[tansaku_moto,tansaku_saki]=ironuri
        que.append(tansaku_saki)
        irokazu=max(irokazu,ironuri)
        ironuri+=1
        
print(irokazu)
for i in range(n-1):
    tmp=(kotaezyun[i][0],kotaezyun[i][1])
    print(ans_dict[tmp])

Solution (Python):

from collections import deque
def resolve():
    N = int(input())
    G = [[] for _ in range(N)]
    nextV = []

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

    q = deque()
    q.append(0)
    color = [0] * N
    while q:
        v = q.popleft()
        parentC = color[v]
        c = 1
        for to in G[v]:
            if c == parentC:  
                c += 1
            color[to] = c
            c += 1
            q.append(to)

    print(max(color))
    for b in nextV:
        print(color[b])


if __name__ == "__main__":
    resolve()

Solution (Python):
"""
ABC146D Diff: 1175
"""




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

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