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

from collections import deque

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

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

k = 0
root = 0
for i in range(1,n):
    if( k < len(graph[i]) ):
        root = i
        k = len(graph[i])

ans = [0] * (n+1)
d = deque()
d.append((root,0,0))

while(d):
    child,parent,color = d.pop()
    edges = graph[child]
    next_color = 1
    for tmp in edges:
        x,i = tmp
        if(x != parent):
            if(next_color == color):
                next_color += 1
            ans[i] = next_color
            d.append((x,child,next_color))
            next_color += 1

print(k)
for i in range(1,n):
    print(ans[i])

Solution (Python):
n=int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    g[a-1].append((b-1,i))
node_color = [0]*n
branch_color = [0]*(n-1)
for start_node, goal  in enumerate(g):
    
    color = 1
    for goal_node , i in goal:
        if node_color[start_node] == color:
            color += 1
        node_color[goal_node] = color
        branch_color[i] = color
        color += 1
        
print(max(branch_color))
for i in branch_color:
    print(i)

Solution (Python):
from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
    a, b = map(int, input().split())
    edges[a].append([edge_idx, b])
    edges[b].append([edge_idx, a])

used_edges = set()
colors = [1 for _ in range(1, N + 1)]
used_colors = [set() for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1

while stack:
    edge_info, parent_node_idx = stack.pop()
    cur_color = 1
    for edge_idx, node_idx in edge_info:
        if edge_idx in used_edges: continue
        while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
            cur_color += 1
        used_colors[node_idx].add(cur_color)
        colors[edge_idx] = cur_color
        stack.append([edges[node_idx], node_idx])
        used_edges.add(edge_idx)
        max_col = max(max_col, cur_color)
        cur_color += 1

print(max_col)
for c in colors[1:]:
    print(c)

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

vc=[0] * n
ec=[-1]*(n-1)
for p,ci in enumerate(g):
    color = 1
    for c, i in ci:
        if vc[p] == color:
            color += 1
        vc[c] = color
        ec[i] = color
        color += 1
        

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

Solution (Python):

 
import sys
from collections import deque                


def main():
    input = sys.stdin.readline      
    def ii():  return int(input())
            

    def bfs_tree_traverse(root):
        ' root から BFS し条件を満たすように彩色していく。各辺の色情報を color に記載。最後に使用した色の数を返す。'
        paths = deque([root])
        max_branch = 0
        while len(paths) != 0:
            edge_color = 0
            current = paths.popleft()
            parent_edge_color = color[current]
            for v in adj[current]:
                paths.append(v)
                edge_color += 1
                if edge_color == parent_edge_color:
                    edge_color += 1
                color[v] = edge_color
                max_branch = max(max_branch, edge_color)
        return max_branch
        
 
    n = ii()
    
    L = [tuple(map(lambda x: int(x)-1, input().rstrip().split())) for _ in range(n-1)]
    
    adj = [[] for _ in range(n)]
    for pair in L:
        a, b = pair
        adj[a].append(b)
    
    color = [0] * n
    
    print(bfs_tree_traverse(0))
    for pair in L:
        _, b = pair
        print(color[b])
 
if __name__ == "__main__":
    main()

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

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

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

num_colors = max(list(map(len, edges)))
edge_colors = [0] * (n-1)


def set_color(current, parent, color):
    next_color = 1
    for node, i in edges[current]:
        if next_color == color:
            next_color += 1
        if node != parent:
            edge_colors[i] = next_color
            set_color(node, current, next_color)
            next_color += 1


set_color(0, -1, 0)
print(num_colors)
for v in edge_colors:
    print(v)

Solution (Python):
from collections import deque
from collections import defaultdict
n=int(input())
E=[[] for _ in range(n)]
col=defaultdict(list)
l=[]
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  E[a].append(b)
  E[b].append(a)
  col[(a,b)]=-1
  col[(b,a)]=-1
  l.append((a,b))
s=-1
k=-1
for i in range(n):
  if len(E[i])>k:
    k=len(E[i])
    s=i
par=[-1]*n
stack=deque([s])
seen=[-1]*n
seen[s]=1
while stack:
  u=stack.pop()
  if u==s:
    cnt=1
  else:
    cnt=col[(par[u],u)]+1
  for v in E[u]:
    if seen[v]!=1:
      par[v]=u
      seen[v]=1
      if cnt<=k:
        col[(u,v)]=cnt
        cnt+=1
      else:
        col[(u,v)]=1
        cnt=2
      stack.append(v)
print(k)
for a,b in l:
  if col[(a,b)]==-1:
    print(col[(b,a)])
  else:
    print(col[(a,b)])

Solution (Python):
from collections import OrderedDict, deque


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    tree = [[] for _ in range(n)]  
    coloring = OrderedDict()
    for e in edges:
        a, b = e[0] - 1, e[1] - 1
        tree[a].append(b)
        
        
        coloring[(a, b)] = 0

    q = deque()
    q_append = q.append
    q_popleft = q.popleft
    seen = [False] * n
    q_append(0)
    col_count_by_v = [set() for _ in range(n)]
    while len(q):
        new_v = q_popleft()
        seen[new_v] = True
        color_i = 1  
        for adj in tree[new_v]:
            if seen[adj]:
                continue
            q_append(adj)
            while color_i in col_count_by_v[new_v]:
                color_i += 1
            coloring[(new_v, adj)] = color_i
            col_count_by_v[new_v].add(color_i)
            col_count_by_v[adj].add(color_i)

    print(len(set(coloring.values())))
    for c in coloring.values():
        print(c)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import OrderedDict, deque


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    tree = [[] for _ in range(n)]  
    coloring = OrderedDict()
    for e in edges:
        a, b = e[0] - 1, e[1] - 1
        tree[a].append(b)
        tree[b].append(a)
        coloring[(a, b)] = 0

    q = deque()
    q_append = q.append
    q_popleft = q.popleft
    seen = [False] * n
    q_append(0)
    col_count_by_v = [set() for _ in range(n)]
    while len(q):
        new_v = q_popleft()
        seen[new_v] = True
        color_i = 1  
        for adj in tree[new_v]:
            if seen[adj]:
                continue
            q_append(adj)
            while color_i in col_count_by_v[new_v]:
                color_i += 1
            coloring[(new_v, adj)] = color_i
            col_count_by_v[new_v].add(color_i)
            col_count_by_v[adj].add(color_i)

    print(len(set(coloring.values())))
    for c in coloring.values():
        print(c)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import OrderedDict, deque

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

q = deque()
q_append = q.append
q_popleft = q.popleft
seen = [False] * n
q_append(0)
col_count_by_v = [set() for _ in range(n)]
while len(q):
    new_v = q_popleft()
    seen[new_v] = True
    color_i = 1  
    for adj in tree[new_v]:
        if seen[adj]:
            continue
        q_append(adj)
        while color_i in col_count_by_v[new_v]:
            color_i += 1
        coloring[(new_v, adj)] = color_i
        col_count_by_v[new_v].add(color_i)
        col_count_by_v[adj].add(color_i)
        color_i += 1

print(len(set(coloring.values())))
for c in coloring.values():
    print(c)

Solution (Python):
from collections import OrderedDict, deque


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    tree = [[] for _ in range(n)]  
    coloring = OrderedDict()
    for e in edges:
        a, b = e[0] - 1, e[1] - 1
        tree[a].append(b)
        tree[b].append(a)
        coloring[(a, b)] = 0

    q = deque()
    q_append = q.append
    q_popleft = q.popleft
    seen = [False] * n
    q_append(0)
    col_count_by_v = [set() for _ in range(n)]
    while len(q):
        new_v = q_popleft()
        seen[new_v] = True
        color_i = 1  
        for adj in tree[new_v]:
            if seen[adj]:
                continue
            q_append(adj)
            while color_i in col_count_by_v[new_v]:
                color_i += 1
            coloring[(new_v, adj)] = color_i
            col_count_by_v[new_v].add(color_i)
            col_count_by_v[adj].add(color_i)
            color_i += 1

    print(len(set(coloring.values())))
    for c in coloring.values():
        print(c)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import OrderedDict, deque


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    tree = [[] for _ in range(n)]  
    coloring = OrderedDict()
    for e in edges:
        a, b = e[0] - 1, e[1] - 1
        tree[a].append(b)
        tree[b].append(a)
        coloring[(a, b)] = 0

    q = deque()
    q_append = q.append
    q_popleft = q.popleft
    seen = [False] * n
    q_append(0)
    col_count_by_v = [set() for _ in range(n)]
    while len(q):
        new_v = q_popleft()
        seen[new_v] = True
        color_i = 1  
        for adj in tree[new_v]:
            if seen[adj]:
                continue
            q_append(adj)
            while color_i in col_count_by_v[new_v]:
                color_i += 1
            coloring[(new_v, adj)] = color_i
            col_count_by_v[new_v].add(color_i)
            col_count_by_v[adj].add(color_i)
            color_i += 1

    print(len(set(coloring.values())))
    for c in coloring.values():
        print(c)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import OrderedDict, deque


def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    tree = [[] for _ in range(n)]  
    coloring = OrderedDict()
    for e in edges:
        a, b = e[0] - 1, e[1] - 1
        tree[a].append(b)
        tree[b].append(a)
        coloring[(a, b)] = 0

    q = deque()
    seen = [False] * n
    q.append(0)
    col_count_by_v = [set() for _ in range(n)]
    while len(q):
        new_v = q.popleft()
        seen[new_v] = True
        color_i = 1  
        for adj in tree[new_v]:
            if seen[adj]:
                continue
            q.append(adj)
            while color_i in col_count_by_v[new_v]:
                color_i += 1
            coloring[(new_v, adj)] = color_i
            col_count_by_v[new_v].add(color_i)
            col_count_by_v[adj].add(color_i)
            color_i += 1

    print(len(set(coloring.values())))
    for c in coloring.values():
        print(c)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(G, v, p, color, prev_c):
    """G: graph, v: vertex, p: parent"""
    c = 1
    
    for e in G[v]:
        if e[0] == p:
            continue
        if c == prev_c:
            c += 1
        color[e[1]] = c
        dfs(G, e[0], v, color, c)
        c += 1


def main():
    N = int(input())
    G = [[] for _ 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))

    color = [-1] * (N - 1)
    dfs(G, 0, -1, color, -1)
    K = max(color)
    print(K)
    print(*color, sep="\n")


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque,defaultdict
n=int(input())
es=[[] for i in range(n)]
es2=[]
for i in range(n-1):
    a,b=map(int,input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)
    es2.append((a-1,b-1))
k=0
col=[1]+[0]*(n-1)

a=defaultdict()
par= [0]*n
total = 0
q = deque()
q.append(0)

while q:
    c = 1
    p = q.popleft()
    for i in es[p]:
        if col[i] == 0:
            col[i] = 1
            if c == par[p]:
                c += 1
            a[(p,i)] = c
            par[i] = c
            c += 1
            q.append(i)
    total = max(total,c-1)

print(total)
for pair in es2:
    print(a[pair])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
ab = [list(map(int, readline().split())) for i in range(n - 1)]
gragh = [[] for j in range(n + 1)]
for a, b in ab:
    gragh[a].append(b)
    gragh[b].append(a)
root = 1
parent = [0] * (n + 1)
stack = [root]
order = []

while stack:
    x = stack.pop()
    order.append(x)
    for y in gragh[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
color = [-1] * (n + 1)

for x in order:
    ng = color[x]
    cnt = 1
    for y in gragh[x]:
        if y == parent[x]:
            continue
        if cnt == ng:
            cnt += 1
        color[y] = cnt
        cnt += 1

ans = []
append = ans.append
for a, b in ab:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])
print(max(ans))
print('\n'.join(map(str, ans)))

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

n = int(input())
edge = [[] for i 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))

k = max(len(e) for e in edge)
print(k)

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

def dfs(v=0, p=-1, to_p_col = -1):
    col = 1
    for u, idx in edge[v]:
        if u != p:
            if col == to_p_col:
                col += 1
            ans[idx] = col
            dfs(u, v, col)
            col += 1
dfs()
print('\n'.join(map(str,ans)))

Solution (Python):
from collections import deque

n = int(input())

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

ver = [[] for i in range(n)]

for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    ver[a-1].append(b-1)
    ver[b-1].append(a-1)



color = [dict() for i in range(n)]
q = deque()
i = 1
for v in ver[0]:
    color[0][v] = i
    color[v][0] = i
    q.append((0,v))
    i += 1



while q:
    f,t = q.popleft()
    i = 1
    for v in ver[t]:
        if v == f:
            continue
        if i == color[f][t]:
            i += 1
        color[t][v] = i
        color[v][t] = i
        q.append((t,v))
        i += 1


k = 0
for i in range(n):
    k = max(k,len(ver[i]))
print(k)
for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    print(color[a-1][b-1])

Solution (Python):
from collections import deque

n = int(input())

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

ver = [[] for i in range(n)]

for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    ver[a-1].append(b-1)
    ver[b-1].append(a-1)



color = [dict() for i in range(n)]
q = deque()
i = 1
for v in ver[0]:
    color[0][v] = i
    color[v][0] = i
    q.append((0,v))
    i += 1



while q:
    f,t = q.popleft()
    i = 1
    for v in ver[t]:
        if v == f:
            continue
        if i == color[f][t]:
            i += 1
        color[t][v] = i
        color[v][t] = i
        q.append((t,v))
        i += 1


k = 0
for i in range(n):
    k = max(k,len(ver[i]))
print(k)
for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    print(color[a-1][b-1])

Solution (Python):
from collections import deque

n = int(input())

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

ver = [[] for i in range(n)]

for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    ver[a-1].append(b-1)
    ver[b-1].append(a-1)



color = [dict() for i in range(n)]
q = deque()
i = 1
for v in ver[0]:
    color[0][v] = i
    color[v][0] = i
    q.append((0,v))
    i += 1



while q:
    f,t = q.popleft()
    i = 1
    for v in ver[t]:
        if v == f:
            continue
        if i == color[f][t]:
            i += 1
        color[t][v] = i
        color[v][t] = i
        q.append((t,v))
        i += 1


k = 0
for i in range(n):
    k = max(k,len(ver[i]))
print(k)
for i in range(n-1):
    a,b = ab[i][0],ab[i][1]
    print(color[a-1][b-1])

Solution (Python):
from collections import deque

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


used = [0]*N
used[0] = 1
a = dict()
parent = [0]*N
total = 0
q = deque()
q.append(0)

while(len(q) > 0):
    c = 1
    r = q.popleft()
    for j in T[r]:
        if used[j] == 0:
            used[j] = 1
            if c == parent[r]:
                c += 1
            a[(r,j)] = c
            parent[j] = c
            c += 1
            q.append(j)
    total = max(total,c-1)


print(total)
for pair in ans:
    print(a[pair])

Solution (Python):
n=int(input())
import sys
sys.setrecursionlimit(10**6)
s=[[] for _ in range(n)]

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

l=[0]*(n-1)

def dfs(node,pre_col,par):
    col=1
    for nei,i in s[node]:
        if nei==par:
            continue
        if col==pre_col:
            col+=1
        l[i]=col
        dfs(nei,col,node)
        col+=1
dfs(0,-1,-1)
print(max(l))
for i in l:
    print(i)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

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

    adj = [[] for _ in range(n)]
    order = []
    for a,b in ab:
        adj[a-1].append(b-1)
        order.append(b-1)

    

    c = [0]*n
    d = deque([0])
    while d:
        v = d.popleft()
        cnt = 1
        for nv in adj[v]:
            if c[v] == cnt:
                cnt += 1
            c[nv] = cnt
            cnt += 1
            d.append(nv)

    print(max(c))

    for i in order:
        print(c[i])

if __name__ == '__main__':
    main()

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

N = int(input())
edges = [[int(i) for i in input().split()] for _ in range(N-1)]
edge_col = [0]*(N-1)
gp = [[] for _ in range(N)]

for ind, (a, b) in enumerate(edges):
    gp[a-1].append((b-1, ind))
    gp[b-1].append((a-1, ind))

cols = [set(list([x+1 for x in range(len(gp[i]))])) for i in range(N)]

seen = set()
stk = [0]
max_col = 0
while stk:
    pt = stk.pop()
    
    if(pt in seen):
        continue
    seen.add(pt)
    for nxt, ind in gp[pt]:
        if(nxt in seen):
            continue
        col = cols[pt].pop()
        max_col = max(col, max_col)
        edge_col[ind] = col
        try:
            cols[nxt].remove(col)
        except:
            pass

        stk.append(nxt)

print(max_col)
for i in edge_col:
    print(i)

Solution (Python):
from collections import deque

N = int(input())
edges = [[] for _ in range(N)]
edge_index = {}
ab = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
for i, (a, b) in enumerate(ab):
    edges[a].append(b)
    edges[b].append(a)
    edge_index[(a, b)] = edge_index[(b, a)] = i


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

color = [-1]*(N-1)
visited = [False]*N
visited[root] = True

stack = deque()  
for i, to in enumerate(edges[root]):
    color[edge_index[(root, to)]] = i+1
    visited[to] = True
    stack.append((to, i+1))

while stack:
    v, v_col = stack.pop()
    color_condidate = 0
    for to in edges[v]:
        assert color_condidate <= max_degree, "hello"
        if visited[to]:
            continue
        visited[to] = True
        color_condidate += 1
        if color_condidate == v_col:
            color_condidate += 1
        idx = edge_index[(v, to)]
        color[idx] = color_condidate
        stack.append((to, color_condidate))

print(max_degree)
print(*color, sep='\n')

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = [[] for _ in range(N+1)]
AB = [lr() for _ in range(N-1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [(root, 0)]
color = [0] * (N+1)

while stack:
    cur, ng = stack.pop()
    c = 1
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        if c == ng:
            c += 1
        parent[next] = cur
        color[next] = c
        stack.append((next, c))
        c += 1

answer = []
append = answer.append
for a, b in AB:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])

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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque, defaultdict

def bfs():
    q = deque([(0, 0)])
    visited = [False]*N
    visited[0] = True
    
    while q:
        v, c = q.popleft()
        now = 1
        
        for nv in G[v]:
            if not visited[nv]:
                if now==c:
                    now += 1
                    
                k = 10**6*min(v, nv)+max(v, nv)
                ans[k] = now
                q.append((nv, now))
                visited[nv] = True
                now += 1

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

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

ans = defaultdict(int)
bfs()
K = max(list(ans.values()))

print(K)

for a, b in edges:
    print(ans[10**6*a+b])

Solution (Python):

from collections import deque

class Edge:
    def __init__(self, to, d):
        self.to = to
        self.d = d

def main():
    n = int(input())
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        g[a].append(Edge(b, i))
        g[b].append(Edge(a, i))

    dq = deque() 
    dq.append(0) 
    done = [0 for _ in range(n)]
    done[0] = 1
    ans = [0 for _ in range(n-1)]


    while len(dq):
        v = dq.pop()
        c = -1
        for i in range(len(g[v])):
            u = g[v][i].to
            ei = g[v][i].d
            if done[u]:
                c = ans[ei]
        k = 1
        for i in range(len(g[v])): 
            u = g[v][i].to
            ei = g[v][i].d
            if done[u]:
                continue 
            if k == c:
                k += 1
            ans[ei] = k
            k += 1
            dq.append(u)
            done[u] =  1
            

    mx = 0
    for i in range(len(g)):
        mx = max(mx, len(g[i]))

    print(mx)
    for i in ans:
        print(i)
main()

Solution (Python):
import sys
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
AB = [lr() for _ in range(N-1)]
graph = [[] for _ in range(N+1)] 
for i in range(N-1):
    a, b = AB[i]
    AB[i] = tuple(sorted([a, b]))
    graph[a].append(b)
    graph[b].append(a)

AB_to_C = defaultdict(int)
root = 1
parent = [0] * (N+1)
stack = [root]
while stack:
    cur = stack.pop()
    used = 0
    if parent[cur] != 0:
        used = AB_to_C[tuple(sorted([cur, parent[cur]]))]
    color = 1
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        while True:
            if color == used:
                color += 1
            else:
                AB_to_C[tuple(sorted([cur, next]))] = color
                color += 1
                break
        stack.append(next)

answer = [0] * (N-1)
for i in range(N-1):
    answer[i] = AB_to_C[AB[i]]

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

Solution (Python):
from collections import deque, OrderedDict

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

tree = [[] for _ in range(n)]

edge_color = OrderedDict()  
for e in edges:
    a = e[0] - 1
    b = e[1] - 1
    tree[a].append(b)
    tree[b].append(a)
    edge_color[(min(a, b), max(a, b))] = 0

print(max(len(v) for v in tree))

seen = [False] * n  
que = deque()
que_append = que.append
que_popleft = que.popleft
start = 0
seen[start] = True
que_append(start)

v_based_color = [set() for _ in range(n)]
while len(que):
    v = que_popleft()
    color_i = 1  
    for adj in tree[v]:
        if seen[adj]:
            continue
        seen[adj] = True
        que_append(adj)
        while color_i in v_based_color[v]:
            
            color_i += 1
        edge_color[(min(v, adj), max(v, adj))] = color_i
        
        v_based_color[v].add(color_i)
        v_based_color[adj].add(color_i)
        color_i += 1

{print(c) for c in edge_color.values()}

Solution (Python):
from collections import deque, OrderedDict

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

tree = [[] for _ in range(n)]

edge_color = OrderedDict()  
for e in edges:
    a = e[0] - 1
    b = e[1] - 1
    tree[a].append(b)
    tree[b].append(a)
    edge_color[(min(a, b), max(a, b))] = 0

print(max(len(v) for v in tree))

seen = [False] * n  
que = deque()
que_append = que.append
que_popleft = que.popleft
start = 0
seen[start] = True
que_append(start)

v_based_color = [set() for _ in range(n)]
while len(que):
    v = que_popleft()
    color_i = 1  
    for adj in tree[v]:
        if seen[adj]:
            continue
        seen[adj] = True
        que_append(adj)
        while color_i in v_based_color[v]:
            
            color_i += 1
        edge_color[(min(v, adj), max(v, adj))] = color_i
        
        v_based_color[v].add(color_i)
        v_based_color[adj].add(color_i)
        color_i += 1

{print(c) for c in edge_color.values()}

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

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


s = []
s.append(0)
parent = [-1]*n
order = []
while s:
    x = s.pop()
    order.append(x)
    for nx in g[x]:
        if nx == parent[x]:
            continue
        parent[nx] = x
        s.append(nx)

color = [0]*n
for v in order:
    ng = color[v]
    c = 1
    for u in g[v]:
        if u == parent[v]:
            continue
        if c == ng:
            c += 1
        color[u] = c
        c += 1

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

print(len(set(ans)))
print('\n'.join(map(str,ans)))

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

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


s = []
s.append(0)
parent = [-1]*n
order = []
while s:
    x = s.pop()
    order.append(x)
    for nx in g[x]:
        if nx == parent[x]:
            continue
        parent[nx] = x
        s.append(nx)

color = [0]*n
for v in order:
    ng = color[v]
    c = 1
    for u in g[v]:
        if u == parent[v]:
            continue
        if c == ng:
            c += 1
        color[u] = c
        c += 1

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

print(len(set(ans)))
print('\n'.join(map(str,ans)))

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

Solution (Python):
from collections import deque
N = int(input())
ab = [list(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
T = [[] for i in range(N)]
for a,b in ab:
    T[a].append(b)
q = deque([0])
color = [0]*N
while q:
    x = q.popleft()
    c = 1
    for y in T[x]:
        if c==color[x]:
            c+=1
        color[y] = c
        c+=1
        q.append(y)
print(max(color))
for i in range(N-1):
    print(color[ab[i][1]])

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

import sys
sys.setrecursionlimit(4100000)
S=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  S[a-1].append((b-1, i))
  S[b-1].append((a-1, i))

L=[0]*(N-1)


def dfs(node, pre_col,pre_node):
  col=1
  for next_node, i in S[node]:
    if next_node==pre_node:
      continue
    if col==pre_col:
      col+=1
    L[i]=col
    dfs(next_node, col, node)
    col+=1

dfs(0,-1,-1)

print(max(L))
for l in L:
  print(l)