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(10 ** 7)

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = [int(_) - 1 for _ in input().split()]
    edge[a].append((b, i))
    edge[b].append((a, i))
ans = [0] * (N - 1)
colors_num = max([len(_) for _ in edge])
colors = list(range(colors_num))


def dfs(v, pv, pc):
    valid_colors = filter(lambda c: c != pc, colors)
    childs = filter(lambda c: c[0] != pv, edge[v])
    for ((cv, ci), color) in zip(childs, valid_colors):
        ans[ci] = color + 1
        dfs(cv, v, color)


dfs(0, -1, -1)
print(colors_num)
print(*ans)

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

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = [int(_) - 1 for _ in input().split()]
    edge[a].append((b, i))
    edge[b].append((a, i))
ans = [0] * (N - 1)
colors_num = max([len(_) for _ in edge])
colors = list(range(colors_num))


def dfs(v, pv, pc):
    valid_colors = filter(lambda c: c != pc, colors)
    childs = list(filter(lambda c: c[0] != pv, edge[v]))
    for ((cv, ci), color) in zip(childs, valid_colors):
        ans[ci] = color + 1
        dfs(cv, v, color)


dfs(0, -1, -1)
print(colors_num)
print(*ans)

Solution (Python):
from collections import deque

def main():
    n = int(input())
    adj = [[]for i in range(n+1)]
    ab = [list(map(int, input().split())) for i in range(n-1)]
    for a, b in ab:
        adj[a].append(b)
        adj[b].append(a)
    
    
    
    order  = []
    parent = [0] * (n+1)
    visited = [0] * (n+1)
    visited[1] = 1
    q = deque([1])
    while q:
        par = q.popleft()
        order.append(par)
        for chl in adj[par]:
            if visited[chl]:
                continue
            
            visited[chl] = 1
            parent[chl] = par
            q.append(chl)
    
    
    cl = [None] * (n+1)
    for par in order:
        
        pc = cl[par]
        
        color = 1
        for chl in adj[par]:
            
            if chl == parent[par]:
                continue
            
            if pc == color:
                color += 1
            
            cl[chl] = color
            
            color += 1
    
    g = max([len(i) for i in adj]) 
    print(g)   
    for a, b in ab:
        
        if parent[a] != b:
            print(cl[b])
        else:
            print(cl[a])
            
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def main():
    n = int(input())
    adj = [[]for i in range(n+1)]
    ab = [list(map(int, input().split())) for i in range(n-1)]
    for a, b in ab:
        adj[a].append(b)
        adj[b].append(a)
    
    
    
    order  = []
    parent = [None] * (n+1)
    q = deque([1])
    while q:
        par = q.popleft()
        order.append(par)
        for chl in adj[par]:
            if chl == parent[par]:
                continue
            parent[chl] = par
            q.append(chl)
    
    
    cl = [None] * (n+1)
    for par in order:
        
        pc = cl[par]
        
        color = 1
        for chl in adj[par]:
            
            if chl == parent[par]:
                continue
            
            if pc == color:
                color += 1
            
            cl[chl] = color
            
            color += 1
    
    g = max([len(i) for i in adj]) 
    print(g)   
    for a, b in ab:
        
        if parent[a] != b:
            print(cl[b])
        else:
            print(cl[a])    
    
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

tree = [[] for _ in range(N + 1)]
for i, (a, b) in enumerate(X):
    tree[a].append((b, i))
    tree[b].append((a, i))

visited = [False] * (N + 1)
visited[1] = True
color = [0] * (N - 1)
stack = deque()
stack.append((1, 0))
while stack:
    u, c = stack.popleft()
    tmp = 0
    for v, i in tree[u]:
        if visited[v]:
            continue
            
        tmp += 1
        if tmp == c:
            tmp += 1
            
        visited[v] = True
        color[i] = tmp
        stack.append((v, tmp))

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

Solution (Python):

n = int(input())
v = []
for i in range(n+1):
    v.append([])

colorv = [None] * (n+1)

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

for cur in range(1, n+1):

    

    used = dict()

    for i in range(len(v[cur])):
        next, linenum = v[cur][i]
        if colorv[linenum] is None:
            continue
        
        used[colorv[linenum]] = True

    ncolor = 1

    for i in range(len(v[cur])):
        next, linenum = v[cur][i]
        if colorv[linenum] is not None:
            continue
        while ncolor in used:
            ncolor += 1
        colorv[linenum] = ncolor
        
        used[ncolor] = True

print(max(colorv[:-2]))
for i in range(n-1):
    print(colorv[i])

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

K = 0
for i in range(N):
    d[i+1].sort()
    K = max(K, len(d[i+1]))
print(K)

q = deque([])
q.append((1, 0))
visited = [0 for i in range(N+1)]
visited[1] = 1
while q:
    l, r = q.popleft()
    flag = 0
    cur = 1
    for i, x in enumerate(d[l], start=1):
        if visited[x] == 1:
            continue
        if flag == 0:
            if cur == r:
                q.append((x, cur+1))
                m[(l, x)] = cur+1
                m[(x, l)] = cur+1
                cur += 2
                visited[x] = 1
                flag = 1
                continue
            m[(l, x)] = cur
            m[(x, l)] = cur
            q.append((x, cur))
            cur += 1
            visited[x] = 1
        else:
            q.append((x, cur))
            m[(l, x)] = cur
            m[(x, l)] = cur
            cur += 1
            visited[x] = 1
for i in range(N-1):
    a, b = ls[i]
    print(m[(a, b)])

Solution (Python):
from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

N  = int(input())
Gb = [ [] for _ in range(N) ]
Gu = [ [] for _ in range(N) ]
Es = {}

for n in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())

    Es[f'{a:06}{b:06}'] = None

    Gb[a].append(b)
    Gb[b].append(a)
    Gu[a].append(b)

colors = list(range(max(map(len, Gb))))

def dfs(base_node, edge_color):
    global Es

    valid_colors = filter(lambda color: color != edge_color, colors)

    for child_node, color in zip(Gu[base_node], valid_colors):
        Es[f'{base_node:06}{child_node:06}'] = color + 1

        dfs(child_node, color)

print(len(colors))

dfs(0, None)

for color in Es.values():
    print(color)

Solution (Python):
"""2020/7/2再挑戦"""

from collections import deque
N = int(input())
connection ={i:set() for i in range(1,N+1)}
connection_parent =[]
for i in range(1,N):
    a,b = (int(i) for i in input().split())
    connection[a].add(b)
    connection[b].add(a)
    connection_parent.append(b)


c =[]
for i in connection.values():
    c.append(len(i))
color_min =max(c)


start =1
color={i:0 for i in range(1,N+1)} 
passed =set() 
dq =deque([start]) 
color[start] =0
while len(dq) >0:
    now =dq.popleft()
    passed.add(now)
    c1 =color[now]
    for next in connection[now]:
        if next not in passed:
            c1 +=1
            c1 %=color_min
            color[next] =c1  
            dq.append(next)
print(color_min)
for i in connection_parent:
    print(color[i] +1)

Solution (Python):
import sys
 
n = int(input())
links = [set() for _ in range(n)]
for i, line in enumerate(sys.stdin):
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add((i, b))
    links[b].add((i, a))
 
ans = [-1] * (n - 1)
k = max(map(len, links))
q = [(0, -1)]
fixed = set()
 
while q:
    v, c = q.pop()
    color = 1
    if c == color:
        color += 1
    for i, u in links[v]:
        if ans[i] != -1:
            continue
        ans[i] = color
        q.append((u, color))
        color += 1
        if c == color:
            color += 1
 
print(k)
print('\n'.join(map(str, ans)))

Solution (Python):
from collections import deque

n = int(input())

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

mx_color = 0    
for i in range(n):
    mx_color = max(mx_color,len(adj[i]))

dist = [-1]*n

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

q = deque([])
q.append([0,-1])
dist[0] = 0

while len(q) > 0:
    v,c = q.popleft()
    color = 1
    
    if color == c:
        color += 1
        
    for nv,nc in adj[v]:
        if dist[nv] == -1:
            dist[nv] = dist[v] + 1
            q.append([nv,color])
            res[nc] = color
            color += 1
            if color == c:
                color += 1

print(mx_color)

for i in res:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def II(): return int(input())
def MI(): return map(int, input().split())
N=II()
edge=[[] for i in range(N)]
a=[0]*N
b=[0]*N
for i in range(N-1):
  a[i],b[i]=MI()
  a[i]-=1
  b[i]-=1
  edge[a[i]].append(b[i])
  edge[b[i]].append(a[i])
k=0
color_dict={}
def dfs(to,fm=-1,ban_color=-1):
  global k
  color=1
  for nxt in edge[to]:
    if nxt==fm:
      continue
    if color==ban_color:
      color+=1
    color_dict[(to,nxt)]=color
    dfs(nxt,to,color)
    color+=1
  k=max(k,color-1)
dfs(0)
print(k)
for i in range(N-1):
  print(color_dict[(a[i],b[i])])

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

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

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

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

Solution (Python):
from collections import deque

N = int(input())

dic = {i:[] for i in range(1,N+1)}

rlt = [0]*(N-1)

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

while h:
  j = 1
  c = 0
  t = h.popleft()
  for k in dic[t[0]]:
    if k[0] == t[1]:
      c = rlt[k[1]]
      break
  for k in dic[t[0]]:
    if k[0] == t[1]:
      continue
    if c == j:
      j += 1
    rlt[k[1]] = j
    h.append((k[0],t[0]))
    j += 1
    
print(max(rlt))  
for l in rlt:
  print(l)

Solution (Python):
n = int(input())
V = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    V[a].append([b,i])
    V[b].append([a,i])
m = 0
for W in V:
    m = max(m, len(W))
from collections import deque
q = deque([])
reach = [-1]*(n+1)
q.append([1,0])
reach[1] = 0
color = [0]*(n-1)
while q:
    x,c = q.popleft()
    j = 1
    for W,i in V[x]:
        if c == j:
            j += 1
        if reach[W] == -1:
            reach[W] = 0
            q.append([W, j])
            color[i] = j
            j += 1
print(m)
for i in range(n-1):
    print(color[i])

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

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

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

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


n = int(input())
edges = []
paths = {}
for i in range(n-1):
    a, b = list(map(int, input().split(' ')))
    edges.append((a, b))
    paths[a] = paths.get(a, []) + [b]
    paths[b] = paths.get(b, []) + [a]


colors = {}  
current = 1
biggest = 1
def f(current, prev, prev_color):
    global biggest
    color = 0
    for vertex in paths[current]:
        if vertex == prev:
            continue
        color += 1
        if color == prev_color:
            color += 1
        biggest = max(biggest, color)
        colors[(current, vertex)] = color
        f(vertex, current, color)
f(1, None, None)

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

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]

    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    queue = deque([0])
    parent = [-1] * N
    order = []

    while queue:
        v = queue.popleft()
        order.append(v)
        for nv in G[v]:
            if nv == parent[v]:
                continue
            parent[nv] = v
            queue.append(nv)

    color = [0] * N
    for v in order:
        c = 1
        for nv in G[v]:
            if nv == parent[v]:
                continue
            if c == color[v]:
                c += 1
            color[nv] = c
            c += 1

    ans = [0] * (N - 1)
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        if parent[a - 1] == b - 1:
            ans[i] = color[a - 1]
        else:
            ans[i] = color[b - 1]

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        G[a - 1].append((i, b - 1))
        G[b - 1].append((i, a - 1))

    queue = deque([0])
    color = [0] * (N - 1)
    color_from_parent = [0] * N
    color_from_parent[0] = -1

    while queue:
        v = queue.popleft()
        c = 1
        for i, nv in G[v]:
            if color_from_parent[nv] != 0:
                continue
            if c == color_from_parent[v]:
                c += 1
            color_from_parent[nv] = c
            color[i] = c
            c += 1
            queue.append(nv)

    print(max(color))
    print(*color, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        G[a - 1].append((i, b - 1))
        G[b - 1].append((i, a - 1))

    color = [0] * (N - 1)

    def dfs(v, p, pc):
        c = 1
        for i, nv in G[v]:
            if nv == p:
                continue
            if c == pc:
                c += 1
            color[i] = c
            dfs(nv, v, c)
            c += 1

    dfs(0, -1, 0)

    print(max(color))
    print('\n'.join(map(str, color)))
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        G[a - 1].append((i, b - 1))
        G[b - 1].append((i, a - 1))

    queue = deque([0])
    seen = [False] * N
    seen[0] = True
    color = [0] * (N - 1)
    color_parent = [-1] * N

    while queue:
        v = queue.popleft()
        c = 1
        for i, nv in G[v]:
            if seen[nv]:
                continue
            if c == color_parent[v]:
                c += 1
            color_parent[nv] = c
            color[i] = c
            queue.append(nv)
            seen[nv] = True
            c += 1

    print(max(color))
    print(*color, sep='\n')
    return


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

from collections import deque
        
n = int(input())
uf = UnionFind(n)
g = [[] for i in range(n)]
cnt = [0] * n
ans = [0] * (n - 1)

for i in range(n - 1):
    a, b = map(lambda x:int(x) - 1, input().split())
    uf.union(a, b)
    g[a].append((b, i))
    g[b].append((a, i))
    cnt[a] += 1
    cnt[b] += 1
    

for i in uf.roots():
    visited = [0] * n
    visited[i] = 1
    que = deque()
    que.append([i, 0])
    while que:
        s = que.popleft()
        k = 0
        for j in g[s[0]]:
            if not visited[j[0]]:
                while True:
                    k += 1
                    if k != s[1]:
                        que.append([j[0], k])
                        visited[j[0]] = 1
                        ans[j[1]] = k
                        break

print(max(cnt))
print(*ans, sep = "\n")

Solution (Python):
from collections import deque

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

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

ans = [0] * (n - 1)

q = deque([[1, 0, -1]])

while q:
    node, pcol, p_node = q.popleft()
    cnt = 1
    for n_node in graph[node]:
        if n_node[0] == p_node:
            continue
        if cnt == pcol:
            cnt += 1
        ans[n_node[1]] = cnt
        q.append([n_node[0], cnt, node])
        cnt += 1

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

Solution (Python):
import collections
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])
q = collections.deque()
q.append([0,-1,-1])
colors = [0]*(N-1)
while len(q) != 0:
    v, color, num = q.popleft()
    if colors[num] == 0 and color != -1:
        colors[num] = color
    next_color = 0
    for w in edges[v]:
        if colors[w[1]] != 0:
            continue
        next_color += 1
        if next_color == colors[num]:
            next_color += 1
        q.append([w[0],next_color,w[1]])
print(len(set(colors)))
for i in colors:
    print(i)

Solution (Python):
import collections
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])


q = collections.deque()
q.append([0,-1,-1])
colors = [0]*(N-1)
check = [0]*N
while len(q) != 0:
    v, color, num = q.popleft()
    check[v] = 1
    
    if colors[num] == 0 and color != -1:
        colors[num] = color
    next_color = 0
    for w in edges[v]:
        if check[w[0]] != 0:
            continue
        next_color += 1
        if next_color == colors[num]:
            next_color += 1
        q.append([w[0],next_color,w[1]])

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

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    way = [[] for i in range(n+1)]
    for i in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append((b,i))
        way[b].append((a,i))

    q = queue.Queue()
    q.put((1,-1,-1)) 
    col = [-1]*(n-1)
    while not q.empty():
        np,pp,hen = q.get()
        nc = 1
        for i,wn in way[np]:
            if i == pp:
                continue
            if nc == hen:
                nc += 1
            col[wn] = nc
            q.put((i,np,nc))
            nc += 1
    print(max(col))
    for i in col:
        print(i)

    return

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

n = int(input())

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

mx_color = 0    
for i in range(n):
    mx_color = max(mx_color,len(adj[i]))

dist = [-1]*n

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

q = deque([])
q.append([0,-1])
dist[0] = 0

while len(q) > 0:
    v,c = q.popleft()
    color = 1
    
    if color == c:
        color += 1
        
    for nv,nc in adj[v]:
        if dist[nv] == -1:
            dist[nv] = dist[v] + 1
            q.append([nv,color])
            res[nc] = color
            color += 1
            if color == c:
                color += 1

print(mx_color)

for i in res:
    print(i)

Solution (Python):
from collections import deque

n = int(input())

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

mx_color = 0    
for i in range(n):
    mx_color = max(mx_color,len(adj[i]))

dist = [-1]*n

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

q = deque([])
q.append([0,-1])
dist[0] = 0

while len(q) > 0:
    v,c = q.popleft()
    color = 1
    
    if color == c:
        color += 1
        
    for nv,nc in adj[v]:
        if dist[nv] == -1:
            dist[nv] = dist[v] + 1
            q.append([nv,color])
            res[nc] = color
            color += 1
            if color == c:
                color += 1

print(mx_color)

for i in res:
    print(i)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


class Edge:
    def __init__(self, to_, id_):
        self.to = to_
        self.id = id_


ans = None
G = None
K = None


def dfs(to, c):
    global G
    global ans
    nc = c % K + 1
    for g in G[to]:
        if ans[g.id] != -1:
            continue
        ans[g.id] = nc
        dfs(g.to, nc)
        nc = nc % K + 1


def solve():
    global G
    global ans
    global K
    N = Scanner.int()
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = Scanner.map_int()
        x -= 1
        y -= 1
        G[x].append(Edge(y, i))
        G[y].append(Edge(x, i))

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

    ans = [-1 for _ in range(N - 1)]
    dfs(0, 0)
    print(K)
    print(*ans, sep='\n')


def main():
    sys.setrecursionlimit(1000000)
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
from collections import defaultdict

n = int(input())
graph = defaultdict(list)

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

ans = [0] * (n - 1)

q = deque([[1, 0, 0]])
while q:
    v, pcol, root = q.popleft()
    cnt = 1
    for node in graph[v]:
        if node[0] == root:
            continue
        if cnt == pcol:
            cnt += 1
        ans[node[1]] = cnt
        q.append([node[0], cnt, v])
        cnt += 1

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N)]
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
d = {}

for a, b in ab:
  graph[a] += [b]
  graph[b] += [a]

def dfs(u, pre, c):
  color = 0
  for v in graph[u]:
    if v != pre:
      color += 1
      if color == c:
        color += 1
      d[(u, v)] = color
      d[(v, u)] = color
      dfs(v, u, color)

dfs(0, -1, -1)
s = set()
for a, b in ab:
  s.add(d[(a, b)])

print(len(s))
for a, b in ab:
  print(d[(a, b)])

Solution (Python):

from sys import setrecursionlimit


def genid(a, b):
    if b < a:
        a, b = b, a
    return a * 100000 + b


def paint(currentNode, usedColor, parentNode, edges, colors):
    color = 1
    for childNode in edges[currentNode]:
        if childNode == parentNode:
            continue
        if color == usedColor:
            color += 1
        colors[genid(currentNode, childNode)] = color
        paint(childNode, color, currentNode, edges, colors)
        color += 1


setrecursionlimit(10 ** 6)

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

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

colors = {}
paint(0, -1, -1, edges, colors)

print(max(len(e) for e in edges))
for a, b in ab:
    print(colors[genid(a - 1, b - 1)])

Solution (Python):
from collections import deque
from collections import defaultdict

n = int(input())
graph = defaultdict(list)

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

ans = [0] * (n - 1)

q = deque([[1, 0, 0]])
while q:
    v, pcol, root = q.popleft()
    cnt = 1
    for node in graph[v]:
        if node[0] == root:
            continue
        if cnt == pcol:
            cnt += 1
        ans[node[1]] = cnt
        q.append([node[0], cnt, v])
        cnt += 1

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

Solution (Python):
n=int(input())
edges=[[] for i in range(1+n)]
e={}
for i in range(n-1):
    """
    edges[_].append((__,___))
    edges[__].append((_,___))
    """
    _,__=map(int,input().split())
    edges[_].append(__)
    edges[__].append(_)
    e[(_,__)]=i
    e[(__,_)]=i
    """
"""
f=max(len(j)for j in edges)
print(f)
ret=[0]*(n-1)
from collections import deque
dq=deque([(1,1)])

while dq:
    a,c=dq.popleft()
    for to in edges[a]:
        if ret[e[(a,to)]]:continue
        ret[e[(a,to)]]=c
        c=c%f+1
        dq.append((to,c))
        
print(*ret,sep="\n")

Solution (Python):
from collections import deque
N = int(input())
node_branch = [[] for _ in range(N+1)]
branch = [0] * (N)
link = [0] * (N+1)
checked = [False] * (N+1)

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

maxlen = 0
for i, node in enumerate(node_branch):
    if maxlen < len(node):
        maxlen = len(node)
        maxnode = i

print(maxlen)

d = deque()
d.append(maxnode)
link[1] = 0
checked[maxnode] = True

while len(d)>0:
    now = d.popleft()
    color = 1
    for n, b in node_branch[now]:
        if checked[n]:
            continue
        if color == link[now]:
            color += 1
        branch[b] = color
        link[n] = color
        color += 1
        checked[n] = True
        d.append(n)

for i in range(1, N):
    print(branch[i])

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

A=[[] for _ in range(N-1)]
B=[0]*N
C=[0]*N
D=[0]*N

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

for i in range(N-1): 
    c=0
    for j in A[i]:
        while True:
            c+=1
            if c!=B[i]:
                B[j-1]=c
                break

print(max(B))            

for i in range(1,N):
    D[C[i]]=B[i]

for i in range(1,N):
    print(D[i])