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):
'''catupper
ポイントA.再帰DFSで全ての頂点というか、辺をチェック。
ポイントB.入力に注意。頂点の連結が辺になっている。
辺は頂点を結ぶので(a[i], b[i])で表現され、対応する色を
color_dict[(a[i], b[i])]としている。
配列が二重配列になっているので、注意。
ポイントC.色を頂点の順番で辺毎に出力する。辺の数は頂点-1個。
for i in range(n-1):  
    print(color_dict[(a[i], b[i])])
'''

import sys
sys.setrecursionlimit(1000000)

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

a = [0] * n
b = [0] * n

color_dict = {}
k = 0

def dfs(x, last = -1, ban_color = -1):

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

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

dfs(0)


print(k)
for i in range(n-1):
    print(color_dict[(a[i], b[i])])
'''  以下の場合分けは不要。
    if (a[i], b[i]) in color_dict:
        print(color_dict[(a[i], b[i])])
    else:
        print(color_dict[(b[i], a[i])])
'''

Solution (Python):
'''catupper
ポイントA.再帰DFSを使う。
ポイントB.入力に注意。
辺は頂点を結ぶので(a[i], b[i])で表現され、対応する色を
color_dict[(a[i], b[i])]としている。
配列が二重配列になっているので、注意。
ポイントC.色を頂点の順番で辺毎に出力する。辺の数は頂点-1個。
for i in range(n-1):    if (a[i], b[i]) in color_dict:
'''

import sys
sys.setrecursionlimit(1000000)

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

a = [0] * n
b = [0] * n

color_dict = {}
k = 0

def dfs(x, last = -1, ban_color = -1):

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

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

dfs(0)


print(k)

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

Solution (Python):
import sys

sys.setrecursionlimit(1000000)  

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

color_dict = {}  
k = 0


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


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

dfs(0)  
print(k)  

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

Solution (Python):
'''catupper

'''

import sys
sys.setrecursionlimit(1000000)

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

color_dict = {}
k = 0

def dfs(x, last = -1, ban_color = -1):

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

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

dfs(0)
print(k)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)
if __name__ == '__main__':
    n = int(input())
    tree = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        tree[a - 1].append([b - 1, i])

    ans = 0
    for i in tree:
        ans = max(ans, len(i))

    ans = [0] * (n - 1)


    def solve(cur_index, color):
        cnt = 1

        for to, j in tree[cur_index]:
            if cnt == color:
                cnt += 1
            ans[j] = cnt
            solve(to, cnt)
            cnt += 1


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

Solution (Python):
from collections import defaultdict, deque


def main():
    N = int(input())
    edges = list()
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        edges.append((a, b))
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
    MAX_COLORS = max([len(nodes) for nodes in adj_nodes.values()])
    
    edge_colors = dict()
    frontier = deque()
    frontier.append((None, 0, None))  
    explored = [0 for _ in range(N)]
    while len(frontier) > 0:
        n = frontier.popleft()
        explored[n[1]] = 1
        next_from_node = n[1]
        before_color = n[2] if n[2] is not None else (MAX_COLORS - 1)
        next_color = before_color
        next_to_nodes = adj_nodes[next_from_node]
        for next_to_node in next_to_nodes:
            if explored[next_to_node] == 1:
                continue
            next_color = (next_color + 1) % MAX_COLORS
            frontier.append((next_from_node, next_to_node, next_color))
            edge_colors[(next_from_node, next_to_node)] = next_color
            edge_colors[(next_to_node, next_from_node)] = next_color
    
    print(MAX_COLORS)
    for edge in edges:
        print(edge_colors[edge] + 1)


if __name__ == '__main__':
    main()

Solution (Python):
'''ika tako  色は1～からの番号で表すとする。
適当な頂点①から、順に辺で繋がった頂点を探索し、辺の色を、
まだ使われてない最小の色で確定していけば、条件を満たすように作れる。
①--- 1 ---②--- 2 ---⑤
 |           `-- 3 ---⑥
 |--- 2 ---③--- 1 ---⑦
 |           `-- 3 ---⑧
 `--- 3 ---④--- 1 ---⑨
             `-- 2 ---⑩
木の場合は、根から順に確定する限り、相手先の頂点の他の辺が必ず
未確定である（後でその頂点の処理時に何とでも調整できる）ので、
この方法が使える。
'''
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):
'''ika tako  色は1～からの番号で表すとする。
適当な頂点①から、順に辺で繋がった頂点を探索し、辺の色を、
まだ使われてない最小の色で確定していけば、条件を満たすように作れる。
①--- 1 ---②--- 2 ---⑤
 |           `-- 3 ---⑥
 |--- 2 ---③--- 1 ---⑦
 |           `-- 3 ---⑧
 `--- 3 ---④--- 1 ---⑨
             `-- 2 ---⑩
木の場合は、根から順に確定する限り、相手先の頂点の他の辺が必ず
未確定である（後でその頂点の処理時に何とでも調整できる）ので、
この方法が使える。
'''
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):
import sys

input = sys.stdin.readline

N = int(input())

Graph = [[] for _ in range(N)]
edges = []

for _ in range(N - 1):
  a, b = [int(x) - 1 for x in input().split()]
  edges.append((a, b))
  
for a, b in edges:
  Graph[a].append(b)
  Graph[b].append(a)
  
k = max(len(edges) for edges in Graph)

colors = [color for color in range(1, k + 1)]
usedcolor = [None for _ in range(N)]
colored = {}

def colors_except(x):
  for c in colors:
    if c == x:
      continue
    yield c

for v in range(N):
  unused_colors = colors_except(usedcolor[v])
  for edge in Graph[v]:
    
    if (v, edge) not in colored and (edge, v) not in colored:
      color = next(unused_colors)
      colored[(v, edge)] = colored[(edge, v)] = color
      usedcolor[edge] = color

print(k)

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

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

G = {}

for i in range(1,N+1):
    G[i] = []

for i in range(N-1):
    G[data[i][0]].append((data[i][1],i+1))
    G[data[i][1]].append((data[i][0],i+1))

M = max(len(G[i]) for i in range(1,N+1))

print(M)

from collections import deque

E = [0]+[-1]*(N-1)  
E[1] = 1
q = deque([[data[0][0],1],[data[0][1],1]])

while q:
    n,i = q.pop()
    c = 1
    for dn,di in G[n]:
        if E[di] != -1:
            continue
        else:
            if c == E[i]:
                E[di] = M
                c += 1
                q.append([dn,di])
            else:
                E[di] = c
                c += 1
                q.append([dn,di])
for i in range(1,N):
    print(E[i])

Solution (Python):
"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

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

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

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

ret = color_edge[:-1]


    

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

Solution (Python):
"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

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

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

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

ret = e[:-1]


    

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float('inf')
MOD=10**9+7
input=sys.stdin.readline

n=int(input())


from collections import defaultdict
tree = defaultdict(lambda: set([])) 

color={}
key=[]

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

checked=[0]*n
cnt=0

def DEF(parent_color,node_no):
    global color,checked,tree,cnt
    checked[node_no]=1
    cnt=max(cnt,parent_color)
    i=1
    
    for item in tree[node_no]:
        if checked[item]==0:
            if i==parent_color:
                i+=1
            
            color[(min(item,node_no),max(item,node_no))]=i
            DEF(i,item)
            i+=1
DEF(0,1)

print(cnt)
for item in key:
    print(color[item])

Solution (Python):
from collections import deque

N = int(input())

data = [[] for i in range(N)]


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

l = 0

for i in range(N):
    l = max(l,len(data[i]))

print(l)

stack = deque([(0,-1)]) 
visit = [0]*N
visit[0] = 1
color = [0]*(N-1)

while stack:
    x = stack.pop()
    c = 1
    for y in data[x[0]]:
        if visit[y[1]] == 1:
            continue
        else:
            visit[y[1]] = 1
            if c != x[1]:
                color[y[0]]=c
                stack.append((y[1],c))
                c += 1
            else:
                color[y[0]]=c+1
                stack.append((y[1],c+1))
                c += 2


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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N=int(input())

def dfs(u,par):
  col=1
  for v in graph[u]:
    if col==par:
      col+=1
    color_dic[(u,v)]=col
    dfs(v,col)
    col+=1

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


color_dic={}
dfs(1,-1)


K=len(set(color_dic.values()))
print(K)
for e in elist:
  print(color_dic[e])

Solution (Python):
import queue

N=int(input())
G=[[] for index1 in range(N+1)]
for index in range(1,N):
    a,b=map(int,input().split())
    G[a].append((b,index))
    G[b].append((a,index))


A=[0]*N
q=queue.Queue()



q.put((1,0,0))
while not q.empty():
    now=q.get()
    i=1 
    for next in G[now[0]]:
        if next[0]==now[2]: 
            continue
        else:
            if i==now[1]:
                i+=1
            A[next[1]]=i    
            q.put((next[0],i,now[0]))
            i+=1

    


print(max(A))
for j in range(N-1):
    print(A[j+1])

Solution (Python):
'''ika tako  色は1～からの番号で表すとする。
適当な頂点①から、順に辺で繋がった頂点を探索し、辺の色を、
まだ使われてない最小の色で確定していけば、条件を満たすように作れる。
①--- 1 ---②--- 2 ---⑤
 |           `-- 3 ---⑥
 |--- 2 ---③--- 1 ---⑦
 |           `-- 3 ---⑧
 `--- 3 ---④--- 1 ---⑨
             `-- 2 ---⑩
木の場合は、根から順に確定する限り、相手先の頂点の他の辺が必ず
未確定である（後でその頂点の処理時に何とでも調整できる）ので、
この方法が使える。
'''
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):
import sys
sys.setrecursionlimit(10**9)

n = int(input())
graph = [[] for _ in range(n)]
ans = [0] * (n-1)

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


def dfs(now, color):
    cnt = 1
    for to, num in graph[now]:
        if cnt == color:
            cnt += 1
        ans[num] = cnt
        dfs(to, cnt)
        cnt += 1    

dfs(0, 0)

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

Solution (Python):
from collections import defaultdict,deque

graph = defaultdict(list)
N, *AB = map(int, open(0).read().split())
for a, b in zip(*[iter(AB)] * 2):
    graph[a].append(b)


stack = deque([1])
C = [0] * (N + 1)
while stack:
    v = stack.popleft()
    c = 0
    for w in graph[v]:
        c += 1 + (c + 1 == C[v])
        C[w] = c
        stack.append(w)
        
print(max(C))
print("\n".join(str(C[b]) for b in AB[1::2]))

Solution (Python):
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
input = sys.stdin.readline 
sys.setrecursionlimit(500000)

N = int(input())
G = [dict() for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a-1][b-1] = i
    G[b-1][a-1] = i
ans = [0]*(N-1)
visited = [0]*N
def dfs(i,color):
    visited[i] += 1
    c = 1
    for j in G[i]:
        if visited[j]:
            continue
        if c==color:
            c += 1
        ans[G[i][j]] = c
        dfs(j,c)
        c += 1
dfs(0,0)
print(max(ans))
for i in range(N-1):
    print(ans[i])

Solution (Python):

from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())

edge = [[] for i in range(N)]
seen = [0]*N
colors = [0]*(N-1)

for i in range(N-1):
    x, y = list(map(int, input().split()))
    edge[x-1].append((i, y-1))
    edge[y-1].append((i, x-1))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)


que = deque()
que.append([(root, -1)])
while que[0]:
    nque = []
    cque = que.popleft()
    
    for tupl in cque:
        index, pcolor = tupl
        seen[index] = 1
        color = 1
        if (color == pcolor): color += 1
        for tupl2 in edge[index]:
            findex, edgei = tupl2
            if seen[edgei] == 0:
                nque.append((edgei, color))
                colors[findex] = color
                color += 1
                if (color == pcolor): color += 1
    que.append(nque)



for color in colors:
    print(color)

Solution (Python):

from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())

edge = [[] for i in range(N)]
seen = [0]*N
colors = [0]*(N-1)

for i in range(N-1):
    x, y = list(map(int, input().split()))
    edge[x-1].append((i, y-1))
    edge[y-1].append((i, x-1))

lenedge = [len(val) for val in edge]
mledge = max(lenedge)
root = lenedge.index(mledge)
print(mledge)


que = deque()
que.append([(root, -1)])
while que[0]:
    nque = []
    cque = que.popleft()
    
    for tupl in cque:
        index, pcolor = tupl
        seen[index] = 1
        color = 1
        if (color == pcolor): color += 1
        for tupl2 in edge[index]:
            findex, edgei = tupl2
            if seen[edgei] == 0:
                nque.append((edgei, color))
                colors[findex] = color
                color += 1
                if (color == pcolor): color += 1
    que.append(nque)



for color in colors:
    print(color)

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

n = int(input())
neighbors = [[] for i in range(n+1)]
ab = []
for i in range(n-1):
    line = list(map(int, input().split()))
    neighbors[line[0]].append(line[1])
    neighbors[line[1]].append(line[0])
    ab.append((line[0], line[1]))
maximum = 0
neighbors_max = 0
for i in range(n):
    if maximum < len(neighbors[i]):
        neighbors_max = i
        maximum = len(neighbors[i])
edgecolors = {}
reached = {neighbors_max}
def make_other_colors(c, m):
    res = []
    if c > m:
        res += [i+1 for i in range(m)]
    else:
        res += [i+1 for i in range(c-1)]
        res += [maximum-i for i in range(m-c+1)]
    return res
def coloring(v, c):
    if c == 0:
        reached.add(v)
        for i in range(len(neighbors[v])):
            edgecolors[(v, neighbors[v][i])] = i + 1
            edgecolors[(neighbors[v][i], v)] = i + 1
            reached.add(neighbors[v][i])
            coloring(neighbors[v][i], i+1)
        return
    l = len(neighbors[v])
    if l == 1 and neighbors[v][0] in reached:
        reached.add(v)
        return
    other_colors = make_other_colors(c, l-1)
    i = 0
    j = 0
    while i < l:
        if neighbors[v][i] in reached:
            i += 1
            continue
        edgecolors[(v, neighbors[v][i])] = other_colors[j]
        edgecolors[(neighbors[v][i], v)] = other_colors[j]
        reached.add(neighbors[v][i])
        coloring(neighbors[v][i], other_colors[j])
        i += 1
        j += 1
coloring(neighbors_max, 0)
print(maximum)
for i in ab:
    print(edgecolors[i])

Solution (Python):
from collections import deque

n = int(input())
g = {i: set() for i in range(n)}
edge = []
for i in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edge.append('{} {}'.format(a, b))
    g[a].add(b)
    g[b].add(a)

k = 0
ans = dict()
p_color = [0] * n
used = [1] + [0] * (n - 1)
que = deque([0])
while que:
    now = que.popleft()
    k = max(k, len(g[now]))
    color = 1
    for i in g[now]:
        if used[i]:
            continue
        if p_color[now] == color:
            color += 1
        p_color[i] = ans['{} {}'.format(now, i)] = ans['{} {}'.format(i, now)] = color
        color += 1
        used[i] = 1
        que.append(i)

print(k)
for e in edge:
    print(ans[e])

Solution (Python):
import queue

n = int(input())

e = []
f = [{} for i in range(n)]

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

k = 0
for i in range(n-1):
    k = max(k,len(f[i]))

q = queue.Queue()
q.put(0)
used = [[0] for i in range(n)]

while not q.empty():
    p = q.get()
    for key,c in f[p].items():
        if c == 0:
            if used[p][-1]<k:
                col = used[p][-1]+1
            else:
                col = 1
            f[p][key] = col
            f[key][p] = col
            used[p].append(col)
            used[key].append(col)
            q.put(key)

print(k)
for a,b in e:
    print(max(f[a][b],f[b][a]))

Solution (Python):
import queue

n = int(input())

e = []
f = [{} for i in range(n)]

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

k = 0
for i in range(n-1):
    k = max(k,len(f[i]))

q = queue.Queue()
q.put(0)
used = [[0] for i in range(n)]
visited = [0]*n
visited[0]=1

while not q.empty():
    p = q.get()
    for key,c in f[p].items():
        if c == 0 and visited[key]==0:
            if used[p][-1]<k:
                col = used[p][-1]+1
            else:
                col = 1
            f[p][key] = col
            used[p].append(col)
            used[key].append(col)
            q.put(key)
            visited[key]=1

print(k)
for a,b in e:
    print(max(f[a][b],f[b][a]))

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

kind = max([len(i) for i in branch])
print(kind)


color = [0 for _ in range(n)]
todo = [0]
color[0] = 1
while len(todo) > 0:
    num = todo.pop(-1)
    col = color[num]
    if col == kind:
        col = 1
    else:
        col = col + 1
    for i in range(len(branch[num])):
        if color[branch[num][i]] == 0:
            color[branch[num][i]] = col
            todo.append(branch[num][i])
            branch[num][i] = -col
            if col == kind:
                col = 1
            else:
                col = col + 1
            

for i in range(n-1):
    if branch[a[i]][inda[i]] < 0:
        print(-branch[a[i]][inda[i]])
    else:
        print(-branch[b[i]][indb[i]])

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

kind = max([len(i) for i in branch])
print(kind)


color = [0 for _ in range(n)]
todo = [0]
color[0] = 1
while len(todo) > 0:
    num = todo.pop(-1)
    col = color[num]
    if col == kind:
        col = 1
    else:
        col = col + 1
    for i in range(len(branch[num])):
        if color[branch[num][i]] == 0:
            color[branch[num][i]] = col
            todo.append(branch[num][i])
            branch[num][i] = -col
            if col == kind:
                col = 1
            else:
                col = col + 1
            

for i in range(n-1):
    if branch[a[i]][inda[i]] < 0:
        print(-branch[a[i]][inda[i]])
    else:
        print(-branch[b[i]][indb[i]])

Solution (Python):


n = int(input())

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

ans = [0] * (n - 1)
stack = [0]
visited = [-1] * n
visited[0] = 0
while stack:
    node = stack.pop()
    color = 1
    for p in graph[node]:
        if visited[p] < 0:
            if visited[node] == color:
                color += 1
            visited[p] = color
            t = edges[(p, node)]
            ans[t] = color
            stack.append(p)
            color += 1

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

Solution (Python):
import sys
import math  
import bisect  
import queue  


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


def main():
    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)
        G[b].append(a)
        edge.append((a, b))

    que = queue.Queue()
    used = [0 for _ in range(N)]
    parent = [0 for _ in range(N)]
    max_color = 0
    edge_num = {}
    que.put(0)
    used[0] = 1
    while not que.empty():
        cn = que.get()
        color_num = 0
        for nn in G[cn]:
            if used[nn] != 1:
                color_num += 1
                used[nn] = 1
                if (color_num == parent[cn]):
                    color_num += 1
                edge_num[(cn, nn)] = color_num
                parent[nn] = color_num
                que.put(nn)
        max_color = max(max_color, color_num)

    print(max_color)
    for a, b in edge:
        print(edge_num[(a, b)])


if __name__ == '__main__':
    main()

Solution (Python):

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




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


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def search(x,col_befedge):
    
    global col

    k=1
    for n in adj[x]:
        
        e=tuple(sorted((n,x)))
        
        if col[e]>0:
            continue
        if k==col_befedge:
            k+=1
        
        
        
        col[e]=k
        search(n,k)
        k+=1
    
            
        

N=int(input())

adj=[[] for i in range(N+1)]

edges=[]
col={}
for i in range(N-1):
    tmp=acinput()
    adj[tmp[0]].append(tmp[1])
    
    adj[tmp[1]].append(tmp[0])
    col[tuple(sorted(tmp))]=0
    edges.append(tuple(sorted(tmp)))

    





search(1,0)


print(max(col.values()))

for se in edges:
    print(col[se])

Solution (Python):
import sys
from collections import deque, OrderedDict
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N)]
inputs = OrderedDict()

for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
    inputs["-".join(list(map(str, sorted([a - 1, b - 1]))))] = 0

K = 0
for e in edge:
    K = max(K, len(e))
print(K)

def dfs(root, edge, inputs):
    done = [True for _ in range(N)]
    done[root] = False
    d = deque([])
    tmp = 1
    for e in edge[root]:
        if done[e]:
            d.append([e, root, tmp])
            tmp += 1
            done[e] = False
    while d:
        data = d.pop()
        inputs["-".join(list(map(str, sorted(data[:2]))))] = data[2]
        tmp = 1
        for e in edge[data[0]]:
            if done[e]:
                if tmp != data[2]:
                    d.append([e, data[0], tmp])
                else:
                    tmp += 1
                    d.append([e, data[0], tmp])
                tmp += 1
                done[e] = False
    
    return inputs

inputs = dfs(0, edge, inputs)

for i in inputs.values():
    print(i)

Solution (Python):
import sys
from collections import deque, OrderedDict
sys.setrecursionlimit(10 ** 7)

N = int(input())
count = [[] for _ in range(N)]
inputs = OrderedDict()

for _ in range(N - 1):
    a, b = map(int, input().split())
    count[a - 1].append(b - 1)
    count[b - 1].append(a - 1)
    inputs["-".join(list(map(str, sorted([a - 1, b - 1]))))] = 0

K = 0
for c in count:
    K = max(K, len(c))
print(K)

def dfs(root, count, inputs):
    done = [-1 for _ in range(N)]
    done[root] = 0
    d = deque([root])
    r = d.pop()
    childs = count[r]
    tmp = 1
    for c in childs:
        if done[c] == -1:
            d.append([c, r, tmp])
            tmp += 1
            done[c] += 1
    while d:
        data = d.pop()
        inputs["-".join(list(map(str, sorted(data[:2]))))] = data[2]
        childs = count[data[0]]
        tmp = 1
        for c in childs:
            if done[c] == -1:
                if tmp != data[2]:
                    d.append([c, data[0], tmp])
                else:
                    tmp += 1
                    d.append([c, data[0], tmp])
                tmp += 1
                done[c] += 1
    
    return inputs

inputs = dfs(0, count, inputs)

for i in inputs.values():
    print(i)

Solution (Python):
from collections import deque
N = int(input())
connected = [[] for _ in range(N)]
ans = [0] * (N-1)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connected[a-1].append([b,i])
    connected[b-1].append([a,i])
colors = max(len(d) for d in connected)
print(colors)
init = 1
d = deque()
parents = deque()
for edge in connected[0]:
    ans[edge[1]] = init
    init += 1
    d.append(edge)
    parents.append(1)
while d:
    temp = d.popleft()
    parent = parents.popleft()
    l = len(connected[temp[0]-1])
    if l > 1:
        used = deque(range(1,l+1))
        for edge in connected[temp[0]-1]:
            if edge[0] != parent:
                color = used.popleft()
                if color == ans[temp[1]]:
                    ans[edge[1]] = used.popleft()
                else:
                    ans[edge[1]] = color
                d.append(edge)
                parents.append(temp[0])
for i in range(N-1):
    print(ans[i])