CodeEff/ECCO huggingface dataset:
# Original solution
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(eval(input()))
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list([int(x)-1 for x in input().split()])
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


k = 1
init_v = 0
for v in range(n):
    if k < len(edges[v]):
        k = len(edges[v])
        init_v = v


# v-v2間の色をぬる
def dfs(v, parent):
    # v-parent間で使用済みの色は使えない
    if v < parent:
        palette = [i for i in range(k, 0, -1) if i != colors[(v, parent)]]
    else:
        palette = [i for i in range(k, 0, -1) if i != colors[(parent, v)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        if v2 < v:
            colors[(v2, v)] = color
        else:
            colors[(v, v2)] = color
        dfs(v2, v)


dfs(init_v, -1)

print(k)
for a, b in ab:
    print((colors[(a, b)]))


# Optimized solution
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(eval(input()))
ab = []
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = list([int(x)-1 for x in input().split()])
    edges[a].append(b)
    edges[b].append(a)
    ab.append((a, b))

colors = defaultdict(int)


k = 1
init_v = 0
for v in range(n):
    if k < len(edges[v]):
        k = len(edges[v])
        init_v = v


def dfs(v, parent):
    palette = [i for i in range(len(edges[v])+1, 0, -1)
               if i != colors[(parent, v)]]
    for v2 in edges[v]:
        if v2 == parent:
            continue
        color = palette.pop()
        colors[(v2, v)] = color
        colors[(v, v2)] = color
        dfs(v2, v)


dfs(init_v, -1)

print(k)
for a, b in ab:
    print((colors[(a, b)]))
# Original solution
from collections import deque

n = int(eval(input()))
e = [list(map(int, input().split())) for _ in range(n-1)]
c = [0 for _ in range(n-1)]

cmap = [[0 for _ in range(n)] for _ in range(n)]
for l in e:
    cmap[l[0]-1][l[1]-1] = cmap[l[1]-1][l[0]-1]=-1
    
d = deque()
d.append(1)
while(d):
    ed = d.popleft() -1
    clist = list()
    usedc = set()
    for i in range(n):
        if cmap[ed][i]:
            clist.append([i, cmap[ed][i]])
            usedc.add(cmap[ed][i])
    for color in clist:
        if color[1] == -1:
            d.append(color[0]+1)
            cn = 1
            while(1):
                if cn in usedc:
                    cn+=1
                else:
                    usedc.add(cn)
                    break

            cmap[ed][color[0]] = cmap[color[0]][ed] = cn

for i in range(n-1):
    c[i] = cmap[e[i][0]-1][e[i][1]-1]

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




# Optimized solution
from collections import deque
n = int(eval(input()))

ls = [list() for _ in range(n)]
ls2 = [list() for _ in range(n)]
edge = []
for i in range(n-1):
    x,y = list(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)
# Original solution
class ColorMgmt:
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        if self.next_colors[v] != c:
            return
        cnt = 1
        while cnt in self.colors_hash[v]:
            cnt += 1
        self.next_colors[v] = cnt
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(eval(input()))
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print((r[2]))


# Optimized solution
class ColorMgmt:
    from heapq import heappop, heappush
    def __init__(self, n):
        self.colors_hash = [set() for _ in range(n)]
        self.next_colors = [1] * n
    
    def set_color(self, v, c):
        self.colors_hash[v].add(c)
        while self.next_colors[v] in self.colors_hash[v]:
            self.next_colors[v] += 1
    
    def get_color(self, v):
        return self.next_colors[v]


N = int(eval(input()))
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
edge_cnt = [0] * N
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])
    edge_cnt[a] += 1
    edge_cnt[b] += 1
K = max(edge_cnt)

next_list = []
now_list = [0]
color_mgmt = ColorMgmt(N)
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors1 = color_mgmt.get_color(nextv[1])
            colors2 = color_mgmt.get_color(nextv[0])
            color = max(colors1, colors2)
            color_mgmt.set_color(nextv[1], color)
            color_mgmt.set_color(nextv[0], color)
            edge[v][idx][2] = color
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for edges in edge:
    for e in edges:
        ret.append(e)
ret.sort(key=lambda x:x[3])
print(K)
for r in ret:
    print((r[2]))
# Original solution
import collections
import sys
input = sys.stdin.readline
N = int(eval(input()))
ab = [list(map(int, input().split())) for i in range(N-1)]
eda = [set() for i in range(N)]
for a, b in ab:
    eda[a-1].add(b)
    eda[b-1].add(a)
max_e = 0
for i in range(N-1):
    max_e = max(max_e, len(eda[i]))
id = 0
for i in range(N):
    if len(eda[i]) == max_e:
        id = i

q = collections.deque([(id, 0)])
print(max_e)
d = dict()
for a, b in ab:
    d[(a-1, b-1)] = 0
    d[(b-1, a-1)] = 0
eda2 = [set() for j in range(N)]

g = [set() for i in range(N)]

for a, b in ab:
    g[a-1].add(b-1)
    g[b-1].add(a-1)


while(q):
    x, color = q.popleft()
    i = 1
    for y in g[x]:
        if i == color:
            i += 1
        d[(x, y)] = i
        d[(y, x)] = i
        g[y].remove(x)
        q.append((y, i))
        i += 1

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


# Optimized solution
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')
# Original solution
n = int(eval(input()))
ab = [list([int(x)-1 for x in input().split()]) for _ in range(n-1)]

e = [[] for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]

c = [0] * n

for a, b in ab:
    c[a] += 1
    c[b] += 1
    e[a].append(b)
    e[b].append(a)

me = max(c)

print(me)

for a, b in ab:
    c = [0] * n
    for f in e[a]:
        c[d[a][f]] = 1
    for f in e[b]:
        c[d[b][f]] = 1
    for i, x in enumerate(c):
        if x == 0:
            print(i)
            d[a][b] = i
            d[b][a] = i
            break


# Optimized solution
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

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

e = [[] for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]

c = [0] * n

for a, b in ab:
    c[a] += 1
    c[b] += 1
    e[a].append(b)
    e[b].append(a)

me = max(c)

print(me)

def func(x, p, pc):
    color = 1
    for z in e[x]:
        if color == pc:
            color += 1
        if z == p:
            continue
        else:
            d[x][z] = color
            d[z][x] = color
            func(z, x, color)
        color += 1

func(0, -1, -1)

for a, b in ab:
    print((d[a][b]))
# Original solution
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

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

e = [[] for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]

c = [0] * n

for a, b in ab:
    c[a] += 1
    c[b] += 1
    e[a].append(b)
    e[b].append(a)

me = max(c)

print(me)

def func(x, p, pc):
    color = 1
    for z in e[x]:
        if color == pc:
            color += 1
        if z == p:
            continue
        else:
            d[x][z] = color
            d[z][x] = color
            func(z, x, color)
        color += 1

func(0, -1, -1)

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



# Optimized solution
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

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

e = [[] for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]

c = [0] * n

for a, b in ab:
    e[a].append(b)
    e[b].append(a)

me = 0
for i in range(n):
    me = max(me, len(e[i]))
print(me)

def func(x, p, pc):
    color = 1
    for z in e[x]:
        if color == pc:
            color += 1
        if z == p:
            continue
        else:
            d[x][z] = color
            d[z][x] = color
            func(z, x, color)
        color += 1

func(0, -1, -1)

for a, b in ab:
    print((d[a][b]))
# Original solution
from collections import defaultdict, deque

N = int(eval(input()))
E = [[] for _ in range(N+1)]
inp = []
for i in range(N-1):
    a, b = list(map(int, input().split()))
    E[a].append(b)
    E[b].append(a)
    inp.append((a, b))


# node: (id, parent_id)
root_node = (1, -1)
open_list = deque([root_node])
n2c = defaultdict(list)
ans = {}
colors = [-1]*(N-1)
while open_list:
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        color = 1
        while True:
            if not color in n2c[cur_id]:
                n2c[cur_id].append(color)
                n2c[child_id].append(color)
                ans[(cur_id, child_id)] = color
                break
            color += 1
        open_list.append((child_id, cur_id))

print((max(list([len(x) for x in list(n2c.values())]))))
for a, b in inp:
    if (a, b) in list(ans.keys()):
        print((ans[(a, b)]))
    else:
        print((ans[(b, a)]))

# Optimized solution
from collections import defaultdict, deque

N = int(eval(input()))
E = [[] for _ in range(N+1)]
edge_order = []
for i in range(N-1):
    a, b = list(map(int, input().split()))
    E[a].append(b)
    E[b].append(a)
    edge_order.append(b)


# node: (id, parent_id)
root_node = (1, -1)
open_list = deque([root_node])
ans = {}
colors = [-1]*(N+1)
while open_list:
    cur_node = open_list.popleft()
    cur_id, parent_id = cur_node
    adj_id_list = E[cur_id]
    c = 1
    for child_id in adj_id_list:
        if child_id == parent_id:
            continue
        if c == colors[cur_id]:
            c += 1
        colors[child_id] = c
        c += 1
        open_list.append((child_id, cur_id))

print((max(colors)))
for i in edge_order:
    print((colors[i]))
# Original solution
import sys
from collections import deque
input = sys.stdin.readline
N = int(eval(input()))
graph = [[] for _ in range(N)]
ab = [list([int(x)-1 for x in input().split()]) for _ in range(N-1)]

col_max = 0
for i in range(N-1):
  a, b = ab[i]
  graph[a] += [b]
  graph[b] += [a]

for i in range(N):
  col_max = max(col_max, len(graph[i]))
print(col_max)

def bfs(s):
  q = deque([s])
  col = [-1]*N
  col[s] = 0
  edge_col = {}

  while q:
    c = 1
    u = q.pop()
    for v in graph[u]:
      if col[v] == -1:
        if c == col[u]:
          c += 1
        col[v] = c
        q.append(v)
        edge_col[(u, v)] = c
        edge_col[(v, u)] = c
        c += 1
  return edge_col

col = bfs(0)

for a, b in ab:
  print((col[(a, b)]))

# Optimized solution
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
N = int(eval(input()))
graph = [[] for _ in range(N)]
ab = [list([int(x)-1 for x in input().split()]) for _ in range(N-1)]
d = {}

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

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

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

print((len(s)))
for a, b in ab:
  print((d[(a, b)]))
# Original solution
from collections import deque, Counter
 
N = int(eval(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 = list(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()
    col_list = [False] * K
    if not pre_col == -1:
        col_list[pre_col] = True
 
    is_visited[cur_node] = True
 
    for next_node in to[cur_node]:
        if not is_visited[next_node]:
            for i in range(K):
                if not col_list[i]:
                    col_list[i] = True
                    color[(cur_node,next_node)] = i
                    q.append([next_node, i])
                    break
 
print(K)
 
for i in range(N-1):
    print((color[tuple(edge[i])] + 1))
 

# Optimized solution
from collections import deque, Counter

N = int(eval(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 = list(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))
# Original solution
from collections import deque
n = int(eval(input()))
matrix= []
lis = [[] for i in range(n)]
ans = [[0 for i in range(n)] for j in range(n)]
for i in range(n-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    matrix.append(sorted([a,b]))
    lis[a].append(b)
    lis[b].append(a)
color = [-1 for _ in range(n)]
queue = deque([0])
color[0] = 1001001001
maxc = 0
while len(queue) > 0:
    now = queue.pop()
    used = color[now]
    tmp = 1
    for i in lis[now]:
        if color[i] == -1:
            queue.append(i)
            if tmp == used:
                tmp += 1
            color[i] = tmp
            ans[now][i] = tmp
            ans[i][now] = tmp
            maxc = max(maxc, tmp)
            tmp += 1
print(maxc)
for i in range(n-1):
    root = matrix[i]
    print((ans[root[0]][root[1]]))

# Optimized solution
from collections import deque
n = int(eval(input()))
matrix= []
lis = [[] for i in range(n)]
ans = {}
for i in range(n):
    ans[i] = {}
for i in range(n-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    matrix.append(sorted([a,b]))
    lis[a].append(b)
    lis[b].append(a)
color = [-1 for _ in range(n)]
queue = deque([0])
color[0] = 1001001001
maxc = 0
while len(queue) > 0:
    now = queue.pop()
    used = color[now]
    tmp = 1
    for i in lis[now]:
        if color[i] == -1:
            queue.append(i)
            if tmp == used:
                tmp += 1
            color[i] = tmp
            ans[now][i] = tmp
            ans[i][now] = tmp
            maxc = max(maxc, tmp)
            tmp += 1
print(maxc)
for i in range(n-1):
    root = matrix[i]
    print((ans[root[0]][root[1]]))
# Original solution

import heapq
import collections
from collections import deque

n = int(eval(input()))
ab = []
visit = [-1 for _ in range(n+1)]
tree = [[]  for _ in range(n+1)]
for i in range(n-1):
    a, b = list(map(int,input().split()))
    ab.append([a, b])
    tree[a].append(b)
    tree[b].append(a)

colors = [ [-1] * (n + 1)  for _ in range(n + 1)] # abの色を格納
visit[1]=1

q = deque([(1,0)]) #V,color のtuple
K = 0
while q:
    v,from_color = q.popleft()
    c = 1
    for next_v in tree[v]:
        if visit[next_v] == -1:
            visit[next_v] = 1
            if c == from_color:
               c += 1
            colors[v][next_v] = colors[next_v][v] = c
            q.append((next_v,c))
            c += 1
anss = []
K = 0
for temp in ab:
    a,b = temp
    K = max(K, colors[a][b])
    anss.append(colors[a][b])

print(K)
for c in anss:
    print(c)





# for k,v in di:
#     color = max(colors,len(v))


# Optimized solution

import heapq
import collections
from collections import deque

n = int(eval(input()))
ab = []
visit = [-1 for _ in range(n+1)]
tree = [[]  for _ in range(n+1)]
colors = {}
for i in range(n-1):
    a, b = list(map(int,input().split()))
    ab.append((a, b))
    tree[a].append(b)
    tree[b].append(a)
    colors[(a,b)] = -1
    colors[(b,a)] = -1

# abの色を格納
visit[1]=1

q = deque([(1,0)]) #V,color のtuple
K = 0
while q:
    v,from_color = q.popleft()
    c = 1
    for next_v in tree[v]:
        if visit[next_v] == -1:
            visit[next_v] = 1
            if c == from_color:
               c += 1
            colors[(v,next_v)] = colors[(next_v,v)] = c
            q.append((next_v,c))
            c += 1
anss = []
K = 0
for temp in ab:
    a,b = temp
    K = max(K, colors[(a,b)] )
    anss.append(colors[(a,b)])

print(K)
for c in anss:
    print(c)





# for k,v in di:
#     color = max(colors,len(v))
# Original solution
N = int(eval(input()))
ab = [list(map(int, input().split())) for i in range(N-1)]

tree = {i:[] for i in range(1, N+1)}
for a, b in ab:
    tree[a].append(b)
    tree[b].append(a)

stree = sorted(list(tree.items()), key=lambda x: -len(x[1]))
print((len(stree[0][1])))
start = stree[0][0]

colormap = {i:[0]*(N+1) for i in range(1, N+1)}
from collections import deque
q = deque([start])
visited = {start}
while q:
    n = q.popleft()
    for p in tree[n]:
        if p in visited:
            continue
        i = 1
        while True:
            if i not in colormap[n] and i not in colormap[p]:
                colormap[n][p] = i
                colormap[p][n] = i
                break
            i += 1
        if p not in visited:
            q.append(p)
            visited.add(p)

for a, b in ab:
    print((colormap[a][b]))


# Optimized solution
from collections import deque

N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
tree = [list() for _ in range(N+1)]
color = [0] * (N-1)

for i, (a, b) in enumerate(ab):
    tree[a].append((b, i))

q = deque([(1, 0)]) # パス先, パスの色でキューに追加
while q:
    v, pc = q.popleft()
    nc = 0 # 使用する色
    for nv, edge in tree[v]: # nv=パス先 edge=abでの順番
        nc += 1
        if nc == pc: # 渡ってきたパスの色と同じなら+1した色にする
            nc += 1
        color[edge] = nc # 使用する色を答えのリストに格納
        q.append((nv, nc))

print(max(color))
print(*color, sep="\n")
# Original solution
import sys

N = int(sys.stdin.buffer.readline())

neighbor = [[] for _ in range(N)]
edge = []
for i in range(N-1):
    a, b = list(map(int, sys.stdin.buffer.readline().split()))
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)
    edge.append([a-1, b-1, i])

K = len(max(neighbor, key=len))
print(K)
color = [set(range(1, K+1)) for _ in range(N)]

edge = sorted(edge, key = lambda x:x[0])
for idx in range(N-1):
    c = color[edge[idx][0]].pop()
    edge[idx].append(c)
    color[edge[idx][1]].remove(c)

edge = sorted(edge, key=lambda x: x[2])
for x in edge:
    print((x[-1]))

# Optimized solution
import sys
sys.setrecursionlimit(500000)

N = int(sys.stdin.buffer.readline())

neighbor = [[] for _ in range(N)]
for i in range(N-1):
    a, b = list(map(int, sys.stdin.buffer.readline().split()))
    neighbor[a-1].append([b-1, i])
    neighbor[b-1].append([a-1, i])

K = max(len(l) for l in neighbor)
print(K)
ans = [-1]*(N-1)

def dfs(current_point, parent_point, parent_edge_color):
    color = 1
    for next_point, idx in neighbor[current_point]:
        if next_point != parent_point:
            if parent_edge_color == color:
                color += 1
            ans[idx] = color
            dfs(next_point, current_point, color)
            color += 1

dfs(0, -1, -1)
print(("\n".join(map(str, ans))))