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):

from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))



ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    


visited=[False for i in range(n+1)]
visited[start_node]=True




def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    

print(K)

for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])

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

    k=max(len(E[i]) for i in range(n))
    
    ans=[None]*(n-1)
    Q=[(0,-1)]
    while(Q):
        v,p=Q.pop()
        
        if(p==-1):
            col=1
            for nv in E[v]:
                ans[idx[(v,nv)]]=col
                col+=1
                Q.append((nv,v))
        
        else:
            col=1
            for nv in E[v]:
                if(nv==p): continue
                col+=(col==ans[idx[(v,p)]]) 
                ans[idx[(v,nv)]]=col
                col+=1
                Q.append((nv,v))

    print(k)
    print(*ans,sep='\n')
resolve()

Solution (Python):

from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))



ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    


visited=[False for i in range(n+1)]
visited[start_node]=True




def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    

print(K)

for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])

Solution (Python):

from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))



ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    


visited=[False for i in range(n+1)]
visited[start_node]=True




def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    

print(K)

for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])

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

class Node:
    nodes = {}
    max_c = 0
    @classmethod
    def get_root_node(cls):
        n = Node.nodes[1]
        for _ in range(1000000):
            if n.parent is None:
                return n
            else:
                n = n.parent

    @classmethod
    def dump_all_nodes(cls):
        for key, node in Node.nodes.items():
            print(str(node))

    @classmethod
    def get_instance(cls, id, parent):
        if id in Node.nodes:
            if Node.nodes[id].parent is None:
                Node.nodes[id].parent = parent
            return Node.nodes[id]
        else:
            return Node(id, parent)

    @classmethod
    def color_childs(clf, start_node):
        c = 1
        list_to_visit = deque(start_node.childs)
        list_to_visit.append(-1)
        ap = list_to_visit.append

        while(len(list_to_visit)>0):
            if list_to_visit[0]==-1:
                c = 1
                list_to_visit.popleft()
                continue
            node = list_to_visit[0]
            list_to_visit.popleft()
            if c == node.parent.parent_edge_color:
                c += 1
            node.parent_edge_color = c
            if c > Node.max_c:
                Node.max_c = c
            list_to_visit += deque(node.childs)
            ap(-1)
            c += 1

    def __init__(self, id, parent):
        self.id = id
        self.parent = parent 
        self.parent_edge_color = None
        self.childs = []
        Node.nodes[id] = self
        self.used_color = []

    def __str__(self):
        x = self.parent.id if self.parent else "None"
        
        return str(self.id)

    def append_child(self, node):
        self.childs.append(node)

    @property
    def num_color(self):
        if self.parent_edge_color is None:
            return len(self.childs)
        else:
            return len(self.childs) + 1

N = int(input())

Edges = []
Edges_color = []
ap = Edges.append
for i in range(N-1):
    edge = list(map(int, input().split()))
    ap(edge)
    pnode = Node.get_instance(edge[0], None)
    cnode = Node.get_instance(edge[1], pnode)
    pnode.append_child(cnode)

root = Node.get_root_node()

Node.color_childs(root)

K = Node.max_c
print(K)

for edge in Edges:
    print(Node.get_instance(edge[1], edge[0]).parent_edge_color)

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

class Node:
    nodes = {}
    max_c = 0
    @classmethod
    def get_root_node(cls):
        n = Node.nodes[1]
        for _ in range(1000000):
            if n.parent is None:
                return n
            else:
                n = n.parent

    @classmethod
    def dump_all_nodes(cls):
        for key, node in Node.nodes.items():
            print(str(node))

    @classmethod
    def get_instance(cls, id, parent):
        if id in Node.nodes:
            if Node.nodes[id].parent is None:
                Node.nodes[id].parent = parent
            return Node.nodes[id]
        else:
            return Node(id, parent)

    @classmethod
    def color_childs(clf, start_node):
        c = 1
        list_to_visit = deque(start_node.childs)
        list_to_visit.append(-1)
        ap = list_to_visit.append

        while(len(list_to_visit)>0):
            if list_to_visit[0]==-1:
                c = 1
                list_to_visit.popleft()
                continue
            node = list_to_visit[0]
            list_to_visit.popleft()
            if c == node.parent.parent_edge_color:
                c += 1
            node.parent_edge_color = c
            if c > Node.max_c:
                Node.max_c = c
            list_to_visit += deque(node.childs)
            ap(-1)
            c += 1

    def __init__(self, id, parent):
        self.id = id
        self.parent = parent 
        self.parent_edge_color = None
        self.childs = []
        Node.nodes[id] = self
        self.used_color = []

    def __str__(self):
        x = self.parent.id if self.parent else "None"
        
        return str(self.id)

    def append_child(self, node):
        self.childs.append(node)

    @property
    def num_color(self):
        if self.parent_edge_color is None:
            return len(self.childs)
        else:
            return len(self.childs) + 1

N = int(input())

Edges = []
Edges_color = []
ap = Edges.append
for i in range(N-1):
    edge = list(map(int, input().split()))
    ap(edge)
    pnode = Node.get_instance(edge[0], None)
    cnode = Node.get_instance(edge[1], pnode)
    pnode.append_child(cnode)

root = Node.get_root_node()

Node.color_childs(root)

K = Node.max_c
print(K)

for edge in Edges:
    print(Node.get_instance(edge[1], edge[0]).parent_edge_color)

Solution (Python):
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    e = [[] for _ in range(n + 1)]
    q = deque([1])
    c = [0] * (n + 1)
    for a, b in zip(*[iter(ab)] * 2):
        e[a].append(b)
    while q:
        s = q.popleft()
        d = 0
        for t in e[s]:
            d += 1 + (d + 1 == c[s])
            c[t] = d
            q.append(t)
    return str("{}\n{}".format(max(c), "\n".join(str(c[b]) for _, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
import sys

sys.setrecursionlimit(100000)

N = int(input())
palette = 1
colors = {}
ends = {}
edges = {}

for edge in range(1,N):
    ends[edge] = [int(n) for n in input().split()]

    a, b = ends[edge]
    if a not in edges:
        edges[a] = [edge]
    else:
        edges[a].append(edge)
    if b not in edges:
        edges[b] = [edge]
    else:
        edges[b].append(edge)


def color_edges(parent, root):
    ng = {}
    global palette
    if parent > 0:
        ng[colors[parent]] = True
    for edge in edges[root]:
        if edge in colors:
            color = colors[edge]
        elif palette - len(ng) > 0:
            color = 1
            while color in ng:
                color += 1
            colors[edge] = color
        else:
            palette += 1
            color = palette
            colors[edge] = color

        ng[color] = True
    for edge in edges[root]:
        if edge == parent:
            continue
        a, b = ends[edge]
        if a == root:
            color_edges(edge, b)
        else:
            color_edges(edge, a)

max_edges = 1
root = 1
for node in range(1,N+1):
    if len(edges[node]) > max_edges:
        max_edges = len(edges[node])
        root = node

color_edges(0, root)

print(palette)
for edge in range(1,N):
    print(colors[edge])

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
T = []
D = [0]*N
V = [[] for _ in range(N)]
argmax = 0
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    D[a] += 1
    D[b] += 1
    if D[argmax] < D[a]:
        argmax = a
    if D[argmax] < D[b]:
        argmax = b
    T.append((a, b))
    V[a].append(b)
    V[b].append(a)

K = D[argmax]
Q = deque([])
C = dict()
for i, v in enumerate(V[argmax]):
    C[tuple(sorted([argmax, v]))] = i+1
    Q.append((v, i+1))

check = [0]*N
check[argmax] = 1
while Q:
    v, color = Q.popleft()
    check[v] = 1
    i = 0
    for u in V[v]:
        if check[u]:
            continue
        i += 1
        if i == color:
            i += 1
        C[tuple(sorted([u, v]))] = i
        Q.append((u, i))

print(K)
for i in range(N-1):
    print(C[T[i]])

Solution (Python):

import sys
import collections
input = sys.stdin.readline
def ii(): return int(input().rstrip())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input().rstrip())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def exit(*arg): print(*arg); sys.exit()


class edge:
    def __init__(self, src, to, info):
        self.src = src
        self.to = to
        self.info = info
        return

def main():
    n = ii()
    g = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = mi()
        g[a - 1].append(edge(a - 1, b - 1, i))
        g[b - 1].append(edge(a - 1, b - 1, i))
    color = max(*map(len, g))
    print(color)
    q = collections.deque()
    ans = [-1 for i in range(n - 1)]
    idx = 0
    q.append((0, 0))
    while len(q):
        t, idx = q.popleft()
        for e in g[t]:
            if ans[e.info] != -1:
                continue
            idx += 1
            ans[e.info] = idx
            q.append((e.to, idx))
    print(*map(lambda x: x % color + 1, ans), sep="\n")
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import collections
input = sys.stdin.readline
def ii(): return int(input().rstrip())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input().rstrip())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def exit(*arg): print(*arg); sys.exit()



def main():
    n = ii()
    g = [[] for i in range(n)]
    edge = collections.namedtuple('edge', ['src', 'to', 'info'])
    for i in range(n - 1):
        a, b = mi()
        g[a - 1].append(edge(a - 1, b - 1, i))
        g[b - 1].append(edge(a - 1, b - 1, i))
    color = max(*map(len, g))
    print(color)
    q = collections.deque()
    ans = [-1 for i in range(n - 1)]
    idx = 0
    q.append((0, 0))
    while len(q):
        t, idx = q.popleft()
        for e in g[t]:
            if ans[e.info] != -1:
                continue
            idx += 1
            ans[e.info] = idx
            q.append((e.to, idx))
    print(*map(lambda x: x % color + 1, ans), sep="\n")
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import collections
input = sys.stdin.readline
def ii(): return int(input().rstrip())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input().rstrip())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def exit(*arg): print(*arg); sys.exit()



def main():
    n = ii()
    g = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = mi()
        g[a - 1].append((b - 1, i))
        g[b - 1].append((a - 1, i))
    color = max(*map(len, g))
    print(color)
    q = collections.deque()
    ans = [-1 for i in range(n - 1)]
    idx = 0
    q.append((0, 0))
    while len(q):
        t, idx = q.popleft()
        for e in g[t]:
            if ans[e[1]] != -1:
                continue
            idx += 1
            ans[e[1]] = idx
            q.append((e[0], idx))
    print(*map(lambda x: x % color + 1, ans), sep="\n")
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import collections
input = sys.stdin.readline
def ii(): return int(input().rstrip())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input().rstrip())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def exit(*arg): print(*arg); sys.exit()



def main():
    n = ii()
    g = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = mi()
        g[a - 1].append((b - 1, i))
        g[b - 1].append((a - 1, i))
    color = max([len(g[i]) for i in range(n)])
    print(color)
    q = collections.deque()
    ans = [-1 for i in range(n - 1)]
    idx = 0
    q.append((0, 0))
    while len(q):
        t, idx = q.popleft()
        for e in g[t]:
            if ans[e[1]] != -1:
                continue
            idx += 1
            ans[e[1]] = idx
            q.append((e[0], idx))
    print(*map(lambda x: x % color + 1, ans), sep="\n")
    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import queue
input = sys.stdin.readline
def ii(): return int(input().rstrip())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def exit(*arg): print(*arg); sys.exit()



def main():
    n = ii()
    g = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = mi()
        g[a - 1].append((b - 1, i))
        g[b - 1].append((a - 1, i))
    color = max([len(g[i]) for i in range(n)])
    print(color)
    q = queue.Queue()
    ans = [-1 for i in range(n - 1)]
    idx = 0
    q.put((0, 0))
    while not q.empty():
        t, idx = q.get()
        for e in g[t]:
            if ans[e[1]] != -1:
                continue
            idx += 1
            ans[e[1]] = idx
            q.put((e[0], idx))
    print(*map(lambda x: x % color + 1, ans), sep="\n")
    return


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
path_color=[None]*(n-1)
tree_path=[[] for x in range(n)]
path_num_to_edges=[]
tree_edge_flag=set()
for i in range(n-1):
    ai,bi=[int(x) -1 for x in input().split()]
    tree_path[ai].append((bi,i))
    tree_path[bi].append((ai,i))
    path_num_to_edges.append((ai,bi))

path_color[0]=1
from collections import deque
d=deque()
for i in path_num_to_edges[0]:
    d.append(i)
while d:
    temp_edge=d.pop()
    if temp_edge in tree_edge_flag:
        continue
    tree_edge_flag.add(temp_edge)
    new_path_color=1
    for other_edge,path_num in tree_path[temp_edge]:
        if path_color[path_num]!=None:
            old_color=path_color[path_num]
            break
    for other_edge,path_num in tree_path[temp_edge]:
        if path_color[path_num]!=None:
            continue
        if new_path_color==old_color:
            new_path_color+=1
        path_color[path_num]=new_path_color
        new_path_color+=1
        d.append(other_edge)

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

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

n = int(input())
edges = []

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

edges.sort()

used = [0]*(n)
ans = [0]*(n-1)
num = 1
prev = 0
for edge in edges:
    _from, to, id = edge
    if _from != prev:
        num = 1
    if used[_from] == num:
        num += 1
    ans[id] = num
    used[to] = num
    num += 1
    prev = _from

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

Solution (Python):
n = int(input())
edges = []

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

edges.sort()

used = [0]*(n)
ans = [0]*(n-1)
num = 1
prev = 0
for edge in edges:
    _from, to, id = edge
    if _from != prev:
        num = 1
    if used[_from] == num:
        num += 1
    ans[id] = num
    used[to] = num
    num += 1
    prev = _from

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

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

n = int(input())

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

    
ans = [0]*(n-1)

def col(now,color):
    c = 1
    for (b,j) in graph[now]:
        if c == color:
            c += 1
        ans[j] = c
        col(b,c)
        c += 1

col(0,0)
print(max(ans))
for a in ans:
    print(a)

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

def main():
    N = int(input())
    V = [set() for _ in range(N)]
    E = {}
    for j in range(N - 1):
        a, b = [int(i) - 1 for i in input().split()]
        V[a].add(j)
        V[b].add(j)
        E[(a, j)] = b
        E[(b, j)] = a
    C = [0] * (N - 1)
    clrs = max(len(i) for i in V)
    def color(n, p):
        for e in V[n]:
            if C[e] != 0:
                continue
            c = p + 1
            if c > clrs:
                c = 1
            C[e] = c
            color(E[(n, e)], c)
            p = c
    color(0, 0)
    print(clrs)
    for i in C:
        print(i)

main()

Solution (Python):
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    next_ = [dict([]) for _ in range(n + 1)]
    queue = deque([1])
    for a, b in zip(*[iter(ab)] * 2):
        next_[a][b] = 0
        next_[b][a] = 0
    while len(queue) > 0:
        c = queue.popleft()
        _next = next_[c]
        use = set(range(1, len(_next.keys()) + 1)) - set(next_[c].values())
        for _n, u in zip((k for k, v in _next.items() if v == 0), use):
            queue.append(_n)
            next_[c][_n] = u
            next_[_n][c] = u
    return str("{}\n{}".format(max(map(lambda x: len(x.keys()), next_)),
                               "\n".join(str(next_[a][b]) for a, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    next_ = [dict([]) for _ in range(n + 1)]
    queue = deque([1])
    for a, b in zip(*[iter(ab)] * 2):
        next_[a][b] = 0
        next_[b][a] = 0
    while len(queue) > 0:
        c = queue.popleft()
        _next = next_[c]
        use = set(range(1, len(_next.keys()) + 1)) - set(next_[c].values())
        _next = (k for k, v in _next.items() if v == 0)
        for _n, u in zip(_next, use):
            queue.append(_n)
            next_[c][_n] = u
            next_[_n][c] = u
    return str("{}\n{}".format(max(map(lambda x: len(x.keys()), next_)),
                               "\n".join(str(next_[a][b]) for a, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    next_ = [dict([]) for _ in range(n + 1)]
    
    queue = deque([1])
    for a, b in zip(*[iter(ab)] * 2):
        next_[a][b] = 0
        next_[b][a] = 0
    while len(queue) > 0:
        c = queue.popleft()
        _next = next_[c].items()
        
        use = set(range(1, len(_next) + 1)) - set(next_[c].values())
        _next = (k for k, v in _next if v == 0)
        for _n, u in zip(_next, use):
            queue.append(_n)
            next_[c][_n] = u
            next_[_n][c] = u
            
            
    return str("{}\n{}".format(max(map(lambda x: len(x.keys()), next_)),
                               "\n".join(str(next_[a][b]) for a, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    
    next_ = [dict([]) for _ in range(n + 1)]
    color = [set([]) for _ in range(n + 1)]
    queue = deque([1])
    for a, b in zip(*[iter(ab)] * 2):
        next_[a][b] = 0
        next_[b][a] = 0
    while len(queue) > 0:
        c = queue.popleft()
        _next = next_[c].items()
        use = set(range(1, len(_next) + 1)) - color[c]
        _next = (k for k, v in _next if v == 0)
        for _n, u in zip(_next, use):
            queue.append(_n)
            next_[c][_n] = u
            next_[_n][c] = u
            color[c].add(u)
            color[_n].add(u)
    return str("{}\n{}".format(max(map(lambda x: len(x.keys()), next_)),
                               "\n".join(str(next_[a][b]) for a, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

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

from collections import defaultdict
from collections import deque

g = defaultdict(list)
idx = defaultdict(int)

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


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

res = [0] * (N-1)
n = 0
while q:
  
  node, color = q.popleft()
  
  n = max(n, color)
  i = 1
  for nei in g[node]:
    if i == color:
      i += 1
    q.append((nei, i))
    res[idx[node, nei]] = i
    i += 1
print(n)
for c in res:
  print(c)

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

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

d = deque()
color = [0]*(n-1)
d.append(0)
while len(d):
    c = d.pop()
    cl = []
    for i in ls2[c]:
        if color[i]:
            cl.append(color[i])
    idx = 1
    for i in ls[c]:
        while(1):
            if not idx in cl:
                break
            else:
                idx += 1
        color[i] = idx
        cl.append(idx)
        d.append(edge[i][1])

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

Solution (Python):
from collections import deque

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

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    t[a].append((b, i))
q = deque([(0, 0)])
while q:
    v, pc = q.popleft()
    nc = 0
    for nv, edge in t[v]:
        nc += 1
        if nc == pc:
            nc += 1
        color[edge] = nc
        q.append((nv, nc))

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

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

n = int(input())
adj = [[] for _ in range(n)]
edge = {}

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

que = deque()
que.append(0)
usd = [0]+[-1]*(n-1)
ans = [0]*(n-1)

while que:
    v = que.pop()
    j = 1
    for u in adj[v]:
        if usd[u] < 0:
            if j == usd[v]:
                j += 1
            usd[u] = j
            ans[edge[(u, v)]] = j
            que.appendleft(u)
            j += 1
print(max(ans))
for a in ans:
    print(a)

Solution (Python):
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista

def kolorowe_grafy():
    N = wczytaj_liste()[0]
    lista_krawedzi = []
    listy_krawedzi = [[]]
    for i in range(N-1):
        lista_krawedzi.append(wczytaj_liste())
        listy_krawedzi.append([])
    for w1, w2 in lista_krawedzi: 
        listy_krawedzi[w1-1].append(w2)
        listy_krawedzi[w2-1].append(w1)
        
    do_przejrzenia = [1]
    kolory_zabronione = {1: 0}
    indeks_przegladanego = 0 
    kolor_tenczy = {}
    while indeks_przegladanego < len(do_przejrzenia): 
        aktualnie_przegladany = do_przejrzenia[indeks_przegladanego]
        kolor = 1
        if kolor == kolory_zabronione[aktualnie_przegladany]:
            kolor += 1
        for sasiad in listy_krawedzi[aktualnie_przegladany-1]: 
            if sasiad not in kolory_zabronione: 
                kolory_zabronione[sasiad] = kolor
                kolor_tenczy[(aktualnie_przegladany,sasiad)]=kolor
                kolor_tenczy[(sasiad,aktualnie_przegladany)]=kolor
                kolor += 1
                
                if kolor == kolory_zabronione[aktualnie_przegladany]:
                    kolor += 1
                do_przejrzenia.append(sasiad)
        indeks_przegladanego += 1
    maximum = 0
    for w1, w2 in lista_krawedzi:
        maximum = max(kolor_tenczy[(w1,w2)], maximum)
    print(maximum)
    for w1, w2 in lista_krawedzi:
        print(kolor_tenczy[(w1,w2)])

kolorowe_grafy()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n=int(input())
s=[[]for i in range(n+1)]
t=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    s[a-1].append([b-1,i])
def f(x,r):
    c=1
    for (i,j) in s[x]:
        if c==r:
            c+=1
        t[j]=c
        f(i,c)
        c+=1
f(0,0)
print(max(t))
for i in t:
    print(i)

Solution (Python):
from collections import defaultdict

children = defaultdict(list)
parent = defaultdict(list)
le = []

N = int(input())
for _ in range(N - 1):
    ai, bi = list(map(int, input().split()))
    le.append((ai, bi))
    children[ai].append(bi)
    parent[bi].append(ai)




K = -1
degree = {}
for n in range(1, N + 1):
    knp = 0 if n not in parent else len(parent[n])
    knc = 0 if n not in children else len(children[n])
    
    degree[n] = knp + knc
    K = max(K, knp + knc)

print(K)


root = 1
color = {}
queue = []


for idx, v in enumerate(children[root]):
    color[root, v] = idx + 1
    queue.append((v, idx + 1))

while queue:
    u, pc = queue.pop()
    new_color = 1
    for idx, v in enumerate(children[u]):
        if new_color == pc:
            new_color += 1
        
        color[u, v] = new_color
        queue.append((v, new_color))
        new_color += 1


for edge in le:
    print(color[edge])