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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque 

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

def main():
    
    n = int(readline())
    g = [[] for _ in range(n)]

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

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

    while len(dq) > 0: 
        v = dq.pop()
        c = -1
        for i in range(len(g[v])):
            nx = g[v][i].to
            edge_id = g[v][i].id
            if done[nx]:
                c = edgecolor[edge_id]
        k = 1
        for i in range(len(g[v])):
            nx = g[v][i].to
            edge_id = g[v][i].id
            if done[nx]:
                continue
            if k == c:
                k += 1
            edgecolor[edge_id] = k
            k += 1  
            done[nx] = 1
            dq.append(nx)

    mx = max(edgecolor) 
    print(mx)
    for ec in edgecolor:
        print(ec)

if __name__ == '__main__':
    main()

Solution (Python):
import sys













import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n = ni()
    edge = [[] for i in range(n)]
    origin_edge = []
    edge_dic = {}
    for i in range(n - 1):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        edge_dic[(a, b)] = -1
        origin_edge.append((a, b))

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

    que = queue.Queue()
    que.put((0, -1))

    while que.qsize() > 0:
        node, used_color = que.get()
        current_color = 0 if used_color != 0 else 1
        for k in edge[node]:
            ai = min(node, k)
            bi = max(node, k)

            if edge_dic[(ai, bi)] > -1:
                continue

            edge_dic[(ai, bi)] = current_color
            que.put((k, current_color))
            current_color = current_color + 1 if used_color != current_color + 1 else current_color + 2

    print(max_root)
    for a, b in origin_edge:
        print(edge_dic[(a, b)] + 1)


if __name__ == '__main__':
    main()

Solution (Python):
import sys













import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n = ni()
    edge = [[] for i in range(n)]
    origin_edge = []
    edge_dic = {}
    for i in range(n - 1):
        a, b = ns()
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
        edge_dic[(a, b)] = -1
        origin_edge.append((a, b))

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

    que = queue.Queue()
    que.put((0, -1))

    while que.qsize() > 0:
        node, used_color = que.get()
        current_color = 0 if used_color != 0 else 1
        for k in edge[node]:
            ai = min(node, k)
            bi = max(node, k)

            if edge_dic[(ai, bi)] > -1:
                continue

            edge_dic[(ai, bi)] = current_color
            que.put((k, current_color))
            current_color = current_color + 1 if used_color != current_color + 1 else current_color + 2

    print(max_root)
    for a, b in origin_edge:
        print(edge_dic[(a, b)] + 1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())

g = [[] for _ in range(N)]
hen = []
dic = {}
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))


ans = [0 for _ in range(N-1)]

Q = deque([])
Q.append(0)
used = [0 for _ in range(N)] 
used[0] = 1


while Q:
  v = Q.popleft()
  
  c = -1
  for i in range(len(g[v])): 
    TO = g[v][i][0]
    ID = g[v][i][1]
    if used[TO] == 1:
      c = ans[ID]
  k = 1
  for i in range(len(g[v])): 
    TO = g[v][i][0]
    ID = g[v][i][1]
    if used[TO] == 1:
      continue
    if k == c:
      k += 1
    ans[ID] = k
    k += 1
    Q.append(TO)
    used[TO] = 1
    



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

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")











N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
tree = [[] for _ in range(N)]
for i in range(N-1):
    a,b = ab[i]
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    index = -1
    MAX = 0
for i in range(N):
    li = tree[i]
    n = len(li)
    if n > MAX:
        MAX = n
        index = i
d = defaultdict(int)

def dfs(cur,parent,prevcolor):
    li = tree[cur]
    n = len(li)
    if n == 0:
        return
    flag = 0
    for i in range(n):
        chi = li[i]
        if chi == parent:
            flag = 1
            continue
        a = (prevcolor+1+i)%MAX
        if flag == 1:
            a -= 1
        d[(cur,chi)] = a
        d[(chi,cur)] = a
        dfs(chi,cur,a)
dfs(index,-1,0)
print(MAX)
for i in range(N-1):
    a,b = ab[i]
    ans = d[(a-1,b-1)]
    if ans == 0:
        ans += MAX
    print(1+ans%MAX)

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

child = [[] for _ in range(N+1)]
par = [0]*(N+1)

for ab in AB:
    a,b = ab[0], ab[1]
    child[a].append(b)
    par[b] = a

k = 0
for i in range(1,N+1):
    l = len(child[i])
    if par[i] > 0:
        l += 1
    k = max(k, l)

print(k)
col = [0] * (N+1)
col[1] = 1
for i in range(1, N):
    cnt = 0
    for c in child[i]:
        cnt += 1
        col[c] = (col[i] + cnt) % k

for ab in AB:
    b = ab[1]
    print(col[b] + 1)

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

child = [[] for _ in range(N+1)]
par = [0]*(N+1)

for ab in AB:
    a,b = ab[0], ab[1]
    child[a].append(b)
    par[b] = a

k = 0
for i in range(1,N+1):
    l = len(child[i])
    if par[i] > 0:
        l += 1
    k = max(k, l)

print(k)
col = [0] * (N+1)
col[1] = 1
for i in range(1, N):
    cnt = 0
    for c in child[i]:
        cnt += 1
        col[c] = (col[i] + cnt) % k
        

for ab in AB:
    b = ab[1]
    print(col[b] + 1)

Solution (Python):
"""bfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())

to = [[] for _ in range(n)]
eid = [[] for _ in range(n)]
ans = [0]*(n-1)

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

import queue

q = queue.Queue()
used = [0]*n
q.put(0)
used[0] = 1
while not q.empty():
    v = q.get()
    c = -1
    for i in range(len(to[v])):
        u = to[v][i]; ei = eid[v][i]
        if used[u]: c = ans[ei]
    k = 1
    for i in range(len(to[v])):
        u = to[v][i]; ei = eid[v][i]
        if used[u]: continue
        if k == c: k += 1
        ans[ei] = k
        k += 1
        q.put(u)
        used[u] = 1

mx = 0
for i in range(n):
    mx = max(mx, len(to[i]))
print(mx)
for i in range(n-1):
    print(ans[i])

Solution (Python):
"""dfs"""

import sys
sys.setrecursionlimit(10**6)

n = int(input())

to = [[] for _ in range(n)]
eid = [[] for _ in range(n)]
ans = [0]*(n-1)

def dfs(v, c=-1, p=-1): 
    k = 1
    for i in range(len(to[v])):
        u = to[v][i]
        ei = eid[v][i]
        if u == p: continue 
        if k == c: k += 1 
        ans[ei] = k
        k += 1
        dfs(u,ans[ei],v)

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

dfs(0)

mx = 0
for i in range(n):
    mx = max(mx, len(to[i]))
print(mx)
for i in range(n-1):
    print(ans[i])

Solution (Python):
"""dfs"""

n = int(input())
import sys
sys.setrecursionlimit(10**6)

to = [[] for _ in range(n)]
eid = [[] for _ in range(n)]
ans = [0]*n

def dfs(v, c=-1, p=-1):
    k = 1
    for i in range(len(to[v])):
        u = to[v][i]
        ei = eid[v][i]
        if u == p: continue
        if k == c: k += 1
        ans[ei] = k
        k += 1
        dfs(u,ans[ei],v)

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

dfs(0)
mx = 0
for i in range(n):
    mx = max(mx, len(to[i]))
print(mx)
for i in range(n-1):
    print(ans[i])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def dfs(v, p, p_col):
        col = 1
        for u, idx in tree[v - 1]:
            if u == p:
                continue
            if col == p_col:
                col += 1
            res[idx] = col
            col += 1
            dfs(u, v, res[idx])

    res = [0 for _ in range(n - 1)]
    dfs(1, -1, -1)
    print(max(res))
    print("\n".join(map(str, res)))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
def color_available(unavailable, K):
    idx = 0
    L = len(unavailable)
    unavailable = sorted(unavailable)
    for color in range(K):
        if idx < L and color == unavailable[idx]:
            idx += 1
        else:
            yield color

def bfs(graph, N, K, start):
    colors = [dict() for _ in range(N)]
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        gen = color_available(colors[node].values(), K)
        for n in graph[node]:
            if not visited[n]:
                visited[n] = 1
                colors[node][n] = colors[n][node] = next(gen)
                que.append(n)
    return colors

N = int(input())
graph = [[] for _ in range(N)]
inputs = tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(N - 1))
counts = [0] * N
for i, j in inputs:
    graph[i].append(j)
    graph[j].append(i)
    counts[i] += 1
    counts[j] += 1
K = max(counts)
colors = bfs(graph, N, K, 0)
print(K)
for i, j in inputs:
    print(colors[i][j] + 1)

Solution (Python):
from collections import deque
def color_available(unavailable, K):
    idx = 0
    L = len(unavailable)
    unavailable = sorted(unavailable)
    for color in range(K):
        if idx < L and color == unavailable[idx]:
            idx += 1
        else:
            yield color

def bfs(graph, N, K, start):
    colors = [dict() for _ in range(N)]
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        gen = color_available(colors[node].values(), K)
        color = 1
        for n in graph[node]:
            if not visited[n]:
                visited[n] = 1
                color = next(gen)
                colors[node][n] = color
                colors[n][node] = color
                que.append(n)
    return colors

N = int(input())
graph = [[] for _ in range(N)]
inputs = tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(N - 1))
counts = [0] * N
for i, j in inputs:
    graph[i].append(j)
    graph[j].append(i)
    counts[i] += 1
    counts[j] += 1
K = max(counts)
colors = bfs(graph, N, K, 0)
print(K)
for i, j in inputs:
    print(colors[i][j] + 1)

Solution (Python):
from collections import deque, Counter

N = int(input())

edge =  [[] for i in range(N-1)]
to = [[] for i in range(N)]
color = {}
edge_list = []

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

K = Counter(edge_list).most_common()[0][1]

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

is_visited = [False] * N

while(len(q) != 0):
    cur_node, pre_col = q.popleft()

    is_visited[cur_node] = True
    col_use = 0

    for next_node in to[cur_node]:
        if not is_visited[next_node]:
            if col_use == pre_col:
                col_use += 1

            color[(cur_node,next_node)] = col_use
            q.append([next_node, col_use])
            col_use += 1

print(K)

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

Solution (Python):
N = int(input())
query = [[] for _ in range(N)]
color = []
m = [0]*N
for n in range(N-1):
    a, b = map(int, input().split())
    query[a-1].append(b-1) 
    query[b-1].append(a-1)
    color.append((min(a, b), max(a, b)))
    m[a-1] += 1
    m[b-1] += 1

print(max(m))
from collections import deque
queue = deque()
queue.appendleft(0)
checked = [-1]*N
checked[0] = 0
dic = {}
while queue:
    v = queue.pop()
    oya = checked[v]
    lis = query[v]
    cnt = 1
    for i in lis:
        if checked[i]!=-1:
            continue
        if cnt==oya:
            cnt += 1
        queue.appendleft(i)
        dic[(min(v+1, i+1), max(v+1, i+1))] = cnt
        checked[i] = cnt
        cnt += 1

for n in range(N-1):
    a, b = color[n]
    print(dic[(min(a, b), max(a, b))])

Solution (Python):

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

def bfs(v, c, p):
    n_c = 1
    for i in range(len(g[v])):
        to = g[v][i][0]
        ID = g[v][i][1]
        if to == p:
            continue
        if n_c == c:
            n_c += 1
        ans[ID] = n_c
        bfs(to, n_c, v)
        n_c += 1

bfs(0, 0, -1)
print(max(ans))
for i in range(N-1):
    print(ans[i])

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

    N = int(input())

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

    dq = deque()
    dq.append([0, -1])
    color = [-1] * (N - 1)
    while dq:
        v, skip = dq.popleft()
        color_to_use = 1
        for u, i in g[v]:
            if ~color[i]: continue
            if color_to_use == skip:
                color_to_use += 1
            color[i] = color_to_use
            dq.append((u, color_to_use))
            color_to_use += 1

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict

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


def solve():
    N = int(rl())
    graph = [[] for _ in range(N)]
    counter = defaultdict(int)
    edges = []
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        edges.append(b)
        counter[a] += 1
        counter[b] += 1
    
    ans = [0] * N
    
    def bfs(parent, p_color):
        c_color = 1
        for child in graph[parent]:
            if c_color == p_color:
                c_color += 1
            ans[child] = c_color
            bfs(child, c_color)
            c_color += 1
    
    bfs(0, 0)
    print(max(counter.values()))
    for edge in edges:
        print(ans[edge])


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
sys.setrecursionlimit(500000)

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


ans = [-1 for _ in range(N-1)]


def dfs(v, color, p):
  k = 1 
  for i in range(len(g[v])): 
    TO = g[v][i][0]
    ID = g[v][i][1]
    if TO == p: 
      continue
    if k == color: 
      k += 1
    ans[ID] = k
    k += 1 
    dfs(TO,ans[ID],v)

dfs(0,0,-1) 
print(max(ans))
for i in ans:
  print(i)

Solution (Python):
import sys
sys.setrecursionlimit(500000)

N = int(input())

g = [[] for _ in range(N)]
hen = []
dic = {}
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))


ans = [-1 for _ in range(N-1)]


def dfs(v, color, p):
  k = 1 
  for i in range(len(g[v])): 
    TO = g[v][i][0]
    ID = g[v][i][1]
    if TO == p: 
      continue
    if k == color: 
      k += 1
    ans[ID] = k
    k += 1 
    dfs(TO,ans[ID],v)

dfs(0,0,-1) 
print(max(ans))
for i in ans:
  print(i)

Solution (Python):
import collections
N = int(input())
G = [set() for i in range(N)]
ab = [tuple(map(int, input().split())) for i in range(N-1)]

d = dict()
i = 0
for a, b in ab:
    a -= 1
    b -= 1
    d[(a, b)] = i
    d[(b, a)] = i
    i += 1
    G[a].add(b)
    G[b].add(a)


q = collections.deque()
r = set()
r.add(0)
q.append((0, 0))
ans = [0]*(N-1)

while(q):
    x, s = q.popleft()
    i = 1
    for y in G[x]:
        if y in r:
            continue
        else:
            r.add(y)
            if i == s:
                i += 1
            ans[d[(x, y)]] = i
            q.append((y, i))
            i += 1
print(max(ans))
print(*ans, sep='\n')

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    graph=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        graph[a-1].append((b-1,i))
        graph[b-1].append((a-1,i))
    queue=deque([0])
    visited=[False]*n
    visited[0]=True
    colors=[0]*n
    ans=[0]*(n-1)
    while queue:
        node=queue.popleft()
        c=1
        for xnode,edge in graph[node]:
            if visited[xnode]:continue
            if colors[node]==c:c+=1
            ans[edge]=c
            colors[xnode]=c
            visited[xnode]=True
            queue.append(xnode)
            c+=1
    print(max(ans))
    for a in ans:
        print(a)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    graph=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        graph[a-1].append((b-1,i))
        graph[b-1].append((a-1,i))
    queue=deque([0])
    visited=[False]*n
    visited[0]=True
    colors=[0]*n
    ans=[0]*(n-1)
    while queue:
        node=queue.popleft()
        c=1
        for xnode,edge in graph[node]:
            if visited[xnode]:continue
            if colors[node]==c:c+=1
            ans[edge]=c
            colors[xnode]=c
            visited[xnode]=True
            queue.append(xnode)
            c+=1
    print(max(ans))
    for a in ans:
        print(a)

if __name__=='__main__':
    main()

Solution (Python):
def main():
    import sys
    readline = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    N = int(readline())
    R = [[int(i) for i in r.split()] for r in read().rstrip().split(b'\n')]
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for a, b in R:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def dfs(max_g):
        todo = [0]
        seen = [False]*N
        seen[0] = True
        par = [-1]*N
        while todo:
            u = todo.pop()
            k = 0
            c = edge[(par[u], u)] if u != 0 else 0
            for v in G[u]:
                if seen[v]:
                    continue
                seen[v] = True
                todo.append(v)
                par[v] = u
                k += 1
                if k == c:
                    k += 1
                    if max_g < k:
                        k = 1
                if u < v:
                    edge[(u, v)] = k
                else:
                    edge[(v, u)] = k

    dfs(max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()

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

int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    n = II()
    e = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = MI1()
        e[a].append((b, i))
        e[b].append((a, i))
    

    ans = [0] * (n-1)
    def dfs(v, v_pre=-1, c_pre=-1):
        c = 1
        for (nv, id) in e[v]:
            if nv == v_pre: continue
            if c_pre == c: c += 1
            
            ans[id] = c
            dfs(nv, v, c)
            c += 1

    dfs(0)
    print(max(ans))
    printlist(ans)


if __name__ == '__main__':
    solve()

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

color = [0] * N

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

dfs(0, 0, 0)
color[0] = max(color)
print(*color, sep="\n")

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

queue = deque([0])
seen = [False]*n
seen[0] = True
colors = [None]*n
ans = [None]*(n-1)
while len(queue)>0:
    node = queue.popleft()
    c = 1
    for c_node, edge in graph[node]:
        if seen[c_node]:
            continue
        if colors[node]==c:
            c += 1
        ans[edge] = c
        colors[c_node] = c
        seen[c_node] = True
        queue.append(c_node)
        c += 1
print(max(ans))
for i in ans:
    print(i)

Solution (Python):
from collections import Counter
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

color = [-1] * (N - 1)


def dfs(s, p=-1, pc=-1):
    c = 0
    for t, x in edge[s]:
        if color[x] != -1:
            continue
        if t == p:
            continue
        c += 1
        if c == pc:
            c += 1
        color[x] = c
        dfs(t, s, c)


dfs(1)

print(len(Counter(color)))
print(*color, sep="\n")

Solution (Python):
N = int(input())
edges = [[] for _ in range(N)]

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

ans = [-1] * (N - 1)
A = [set() for _ in range(N)]

st = [0]
while st:
    now = st.pop()
    s = 1
    for i, to in edges[now]:
        if ans[i] != -1:
            continue
        while s in A[now]:
            s += 1
        ans[i] = s
        A[to].add(s)
        A[now].add(s)
        st.append(to)

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

Solution (Python):


from collections import deque

n = int(input())

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

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

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


color_list = {}
check_list = [0]*n

color_max = max(map(len, connect_list))

vertex = [0 for i in range(n)]
d = deque([0])

while(len(d) > 0):
    
    index = d.pop()
    check_list[index] = 1

    index_list = connect_list[index]

    for i in index_list:
        if check_list[i] == 1:
            continue

        check_list[i] = 1
        d.append(i)
        num = vertex[index] % color_max+1
        color_list[(min(index, i), max(index, i))] = num
        vertex[index], vertex[i] = num, num


print(color_max)
for a, b in ab:
    print(color_list[(a-1, b-1)])

Solution (Python):
from collections import deque
n=int(input())
graph=[[] for i in range(n)]
edges=[tuple(map(int,input().split())) for i in range(n-1)]
edge_color={(edges[i][0]-1,edges[i][1]-1):0 for i in range(n-1)}
vertex=[0 for i in range(n)]
for i in edges:
  a,b=i[0],i[1]
  a-=1;b-=1
  graph[a].append(b)
  graph[b].append(a)
color=0;most_connected=0
for i in range(n):
  if len(graph[i])>color:
    color=len(graph[i])
    most_connected=i
visited=[False]*n
bfs=deque([most_connected])
while bfs:
  v=bfs.popleft()
  visited[v]=True
  for i in graph[v]:
    if visited[i]:continue
    I,V=i,v
    if i<v:
      I,V=v,i
    
    edge_color[(V,I)]=vertex[v]%color+1
    vertex[V],vertex[I]=edge_color[(V,I)],edge_color[(V,I)] 
    bfs.append(i)
print(color)
for i in edges:
  print(edge_color[(i[0]-1,i[1]-1)])

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

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([b, i])
    G[b].append([a, i])

stack = deque([[0, 0]])
visited = [0] * N
visited[0] = 1
ans = [0] * (N-1)
while stack:
    i, pc = stack.pop()
    c = 1
    for ni, ln in G[i]:
        if not visited[ni]:
            visited[ni] = 1
            if c == pc:
                c += 1
            ans[ln] = c
            c += 1
            stack.append([ni, ans[ln]])

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
N = int(input())
nood = [[]for i in range(0,N+1,1)]
h_color = [1]*(N+1)
for i in range(1,N,1):
    a,b=map(int,input().split())
    nood[a].append([b,i])
    nood[b].append([a,i])

max_color_count = -1

def bfs(nowNood,preNood,preColor):
    global max_color_count
    colorCount=1
    for i in range(0,len(nood[nowNood]),1):
        if nood[nowNood][i][0]!=preNood:
            if colorCount == preColor:
                colorCount+=1
            h_color[nood[nowNood][i][1]]=colorCount
            bfs(nood[nowNood][i][0],nowNood,colorCount)
            max_color_count = max(max_color_count,colorCount)
            colorCount+=1

bfs(1,-1,-1)
print(max_color_count)
for i in range(1,N,1):
    print(h_color[i])

Solution (Python):


import sys

sys.setrecursionlimit(10 ** 5)

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

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

def dfs(key, color=-1, parent=-1):
    k = 1
    for i in range(len(G[key])):
        if G[key][i][0] == parent:
            continue
        if color == k:
            k += 1
        ans[G[key][i][1]] = k
        dfs(G[key][i][0], k, key)
        k += 1

dfs(0)

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

Solution (Python):

import collections


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

    color[a][b] = -1
    color[b][a] = -1

    edges.append((a, b))


buf = collections.deque()
buf.append(0)

while buf:
    src = buf.popleft()
    used = [color[src][dst] for dst in graph[src]
                if color[src][dst] != -1]
    dst_color = 1
    while dst_color in used:
        dst_color += 1

    for dst in graph[src]:
        if color[src][dst] == -1:
            color[src][dst] = dst_color
            color[dst][src] = dst_color
            buf.append(dst)

            used.append(dst_color)
            while dst_color in used:
                dst_color += 1




print(max([max(c.values()) for c in color]))
for a,b in edges:
    print(color[a][b])

Solution (Python):
import queue

N = int(input())
ab = []
deg = [0 for i in range(N)]
child = [[] for _ in range(N)]
edge = {}
color = [0 for _ in range(N-1)]
for i in range(N-1):
  tmp = list(map(int, input().split()))
  deg[tmp[0]-1] += 1
  deg[tmp[1]-1] += 1
 
  child[tmp[0]-1].append(tmp[1]-1)
  child[tmp[1]-1].append(tmp[0]-1)
  tmp = [tmp[0]-1, tmp[1]-1]
  edge[tuple(tmp)] = i
  
q = queue.Queue()
q.put([None, 0, None])
used = [0]

while not q.empty():
  current = q.get()
  if current[0] is not None:
    cnt = 1
    for c in child[current[1]]:
  
  
      used.append(c)
      if cnt == current[2]:
        cnt += 1
      q.put([current[1], c, cnt])
      ind = [current[1], c] if current[1] < c else [c, current[1]]
      
      color[edge[tuple(ind)]] = cnt
      child[c].remove(current[1])
      cnt += 1
  else:
    for i, c in enumerate(child[current[1]]):
      used.append(c)
      q.put([current[1], c, i+1])
      ind = [current[1], c] if current[1] < c else [c, current[1]]
      
      color[edge[tuple(ind)]] = i+1
      child[c].remove(current[1])

print(max(deg))
for c in color:
  print(c)

Solution (Python):



import sys


import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peers = [[] for _ in range(N)]
colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peers[a].append(b)
    colors[a][b] = 0


def draw(node, parent_edge_color):
    _peers = peers[node]
    if len(_peers) == 0:
        return 0
    color = 1
    max_nrof_color = 1
    for peer in _peers:
        
        if color == parent_edge_color:
            color +=1
        colors[node][peer] = color
        max_nrof_color = max(max_nrof_color, color, draw(peer, color))
        color += 1

    return max_nrof_color


print(draw(0,0))
for a,b in pairs:
    print(colors[a][b])