Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(100000)
def rad_reach(bfr,h,dist,E,rad,ne):
	cnt = 1
	if dist < rad:
		for nxt in E[h]:
			if nxt == bfr: continue
			cnt += rad_reach(h,nxt,dist+1,E,rad,ne) 
	return cnt
def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [set() for i in xrange(N)]
	for i in xrange(N-1):
		a,b = map(lambda x:int(x)-1,raw_input().split())
		E[a].add(b)
		E[b].add(a)
		pairs.append((a,b))
	ans = N
	rad = K/2
	if K % 2 == 0:
		for c in xrange(N):
			ans = min(ans,N-rad_reach(-1,c,0,E,rad,-1))
	else:
		for c1,c2 in pairs:
			E[c1].remove(c2); E[c2].remove(c1)
			ans = min(ans,N-rad_reach(-1,c1,0,E,rad,c2)-rad_reach(-1,c2,0,E,rad,c1))
			E[c1].add(c2); E[c2].add(c1)
	print ans
solve()

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(1000000)
def calc_dist(b,h,dist,E,D,ne):
	D[dist] += 1
	for nxt in E[h]:
		if nxt == b or nxt == ne:
			continue
		calc_dist(h,nxt,dist+1,E,D,ne) 

def solve():
	N,K = map(int,raw_input().split())
	pairs = []
	E = [[] for i in xrange(N)]
	for i in xrange(N-1):
		a,b = map(lambda x:int(x)-1,raw_input().split())
		E[a].append(b)
		E[b].append(a)
		pairs.append((a,b))
	ans = N
	rad = K/2
	if K % 2 == 0:
		for i in xrange(N):
			D = [0]*N
			calc_dist(-1,i,0,E,D,-1)
			for j in xrange(rad):
				D[rad-j-1] += D[rad-j]
			ans = min(N-D[0],ans)
	else:
		for a,b in pairs:
			D1 = [0]*N
			D2 = [0]*N
			calc_dist(-1,a,0,E,D1,b)
			calc_dist(-1,b,0,E,D2,a)
			for j in xrange(rad):
				D1[rad-j-1] += D1[rad-j]
				D2[rad-j-1] += D2[rad-j]
			ans = min(N-D1[0]-D2[0],ans)
	print ans

solve()
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())

l = []
for _ in range(H):
    l.append([0 if s=="." else 1 for s in input()])

def dfs(sh, sw, gh, gw):
    q = deque([(sh, sw)])
    dist = [[10**12]*W for _ in range(H)]
    dist[sh][sw] = 0
    while q:
        h, w = q.popleft()
        for h1, w1 in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
            if not (0<=h1<H and 0<=w1<W):continue
            if l[h1][w1]:continue
            if dist[h1][w1] > dist[h][w] + 1:
                dist[h1][w1] = dist[h][w] + 1
                q.append((h1, w1))
    return dist[gh][gw]

ans = 0
for sh in range(H):
    for sw in range(W):
        for gh in range(H):
            for gw in range(W):
                if gw==sw and gh==sh:
                    continue
                if l[gh][gw] or l[sh][sw]:
                    continue
                ans = max(ans, dfs(sh, sw, gh, gw))
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))
### BUGGY CODE ###

import fractions

number_of_integers = int(input())
integers = list(map(int, input().split()))

holed_integers = []
gcds = [0] * number_of_integers
for i in range(number_of_integers):
    holed_integers = integers[:i] + integers[i+1:]
    for hole_integer in holed_integers:
        gcds[i] = fractions.gcd(gcds[i], hole_integer)

print(max(gcds))

### FIXED CODE ###

import fractions

integral_count = int(input())
blackboard_integers = list(map(int, input().split()))

gcd_integers = list(set(blackboard_integers))

gcd = 0
result = 1
for i in range(len(gcd_integers)):
    gcd = 0
    if blackboard_integers.count(gcd_integers[i]) >= 2:
        for n in gcd_integers:
            gcd = fractions.gcd(gcd, n)
    else:
        for n in gcd_integers[:i]:
            gcd = fractions.gcd(gcd, n)
        for n in gcd_integers[i+1:]:
            gcd = fractions.gcd(gcd, n)
    if gcd > result:
        result = gcd

print(result)
### BUGGY CODE ###

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

def yoi(s, b):
  for i in range(n):
    for j in range(i):
      if s[i % n][(j + b) % n] != s[j % n][(i + b) % n]:
        return 0
  return 1


sol = n * sum(yoi(s, b) for b in range(n))
print(sol)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
st = [str().join(s_) for s_ in zip(*s)]

sol = 0

for i in range(n):
    for k in range(n):
        if s[k] != st[k]:
            break
    else:
        sol += 1
    
    s = [s_l[1:]+s_l[0] for s_l in s]
    st = st[1:] + [st[0]]
    
print(sol * n)
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
for i in range(n):
    a[i] -= i+1

def hoge(b):
    v = 0
    for x in a:
        v += abs(x-b)
    return v

tmp = float('inf')
for x in set(a):
    if hoge(x) < tmp:
        tmp = hoge(x)

print(tmp)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
for i in range(n):
    a[i] -= i+1

#中央値を求める
a.sort()
if len(a) % 2 == 0:
    c = (a[len(a)//2] + a[len(a)//2-1]) // 2
else:
    c = a[len(a)//2]

def hoge(b):
    v = 0
    for x in a:
        v += abs(x-b)
    return v

print(hoge(c))
### BUGGY CODE ###

d , g = map(int, input().split())
pc = [list(map(int, input().split()))for i in range(d)]
x=[]
y=[0]*d
ac=[0]*d
for i in range(d):
    ac[i]=pc[i][0]*(i+1)*100+pc[i][1]

def dfs(n,m,y,now):
    if now==n:
        z=y.copy()
        x.append(z)
        return
    for i in range(m):
        y[now]=i
        dfs(n,m,y,now+1)
dfs(d,3,y,0)

mi = 1000
for i in x:
    sum = 0
    cost = 0
    stock = []
    for j in range(d):
        if i[j]==1:
            sum+=ac[j]
            cost+=pc[j][0]
        if i[j]==2:
            stock+=[(j+1)*100]*pc[j][0]
    stock.sort()
    while sum<g and stock:
        sum+=stock.pop()
        cost+=1
    if sum>=g:
        mi=min(mi,cost)

print(mi)


### FIXED CODE ###

d , g = map(int, input().split())
pc = [list(map(int, input().split()))for i in range(d)]
x=[]
y=[0]*d
ac=[0]*d
for i in range(d):
    ac[i]=pc[i][0]*(i+1)*100+pc[i][1]

def dfs(n,m,y,now):
    if now==n:
        z=y.copy()
        x.append(z)
        return
    for i in range(m):
        y[now]=i
        dfs(n,m,y,now+1)
dfs(d,3,y,0)
mi = 1000
for i in x:
    sum = 0
    cost = 0
    stock = []
    sum2 = 0
    cost2 = 0
    for j in range(d):
        if i[j]==1:
            sum+=ac[j]
            cost+=pc[j][0]
            sum2+=ac[j]
            cost2+=pc[j][0]
        if i[j]==2:
            stock+=[(j+1)*100]*pc[j][0]
            sum2+=pc[j][0]*(j+1)*100
            cost2+=pc[j][0]
    if sum2<g:
        continue
    stock.sort()
    if abs(sum2-g)>abs(sum-g):
        while sum<g and stock:
            sum+=stock.pop()
            cost+=1
        if sum>=g:
            mi=min(mi,cost)
    else:
        while sum2>g and stock:
            sum2-=stock.pop()
            cost2-=1
        cost+=1
        mi=min(mi,cost2)

print(mi)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    inf = 1 << 60

    N, M, L = map(int, input().split())

    dist = [[inf] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        dist[A][B] = dist[B][A] = C

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(
                    dist[i][j],
                    dist[i][k] + dist[k][j]
                )

    g = [[inf] * N for _ in range(N)]  # 到達に必要な補充回数
    for A in range(N):
        for B in range(N):
            if dist[A][B] <= L:
                g[A][B] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                g[i][j] = min(
                    g[i][j],
                    g[i][k] + g[k][j]
                )

    Q = int(input())
    for _ in range(Q):
        s, t = (int(x) - 1 for x in input().split())
        d = g[s][t]
        if d == inf:
            print(-1)
        else:
            print(d - 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline

inf = 300 * (10 ** 9) + 10

n, m, max_tank = map(int, input().split())

dist = [[inf] * n for _ in range(n)]
for i in range(n):
    dist[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    if c > max_tank:
        continue
    # 燃料不足で通過できない

    a -= 1
    b -= 1

    dist[a][b] = c
    dist[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

g = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if dist[i][j] <= max_tank:
            g[i][j] = 0

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j] + 1)

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    print(-1 if g[s][t] == inf else g[s][t])
### BUGGY CODE ###

h, w, d = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

a_and_pos = {}
for i in range(h):
    for j in range(w):
        a_and_pos[a[i][j]] = (i, j)

for l, r in lr:
    ans = 0
    x = l
    i, j = a_and_pos[l]
    while x != r:
        i_next, j_next = a_and_pos[x+d]
        ans = ans +  abs(i_next-i) + abs(j_next-j)
        i, j = i_next, j_next
        x += d
    print(ans)


### FIXED CODE ###

h, w, d = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

a_and_pos = {}
for i in range(h):
    for j in range(w):
        a_and_pos[a[i][j]] = (i, j)

costs = [0]*(h*w+1)
for x in range(d+1, h*w+1):
    i_prev, j_prev = a_and_pos[x-d]
    i, j = a_and_pos[x]
    costs[x] = costs[x-d] + abs(i-i_prev) + abs(j-j_prev)
# print(costs)

for l, r in lr:
    print(costs[r] - costs[l])
### BUGGY CODE ###

import itertools
import numpy as np

H, W, K = map(int, input().split())
A = np.int32([[int(x) for x in input()] for _ in range(H)])

def solve(blocks):
    n_vert_cut = 0
    n_block = blocks.shape[0]
    sums = np.zeros(n_block, dtype=int)

    for c in range(W):
        adds = blocks[:, c]
        sums = sums + adds
        if np.any(sums > K):
            n_vert_cut += 1
            sums = adds

    return n_vert_cut + n_block - 1

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    pivots = [r + 1 for r in range(H - 1) if mask[r]]
    blocks = np.concatenate([block.sum(axis=0) for block in np.split(A, pivots)])
    blocks = blocks.reshape(len(pivots) + 1, W)
    if blocks.max() > K:
        continue
    ans = min(ans, solve(blocks))
print(ans)


### FIXED CODE ###

import itertools

H, W, K = map(int, input().split())
A = [[int(x) for x in input()] for _ in range(H)]


def solve(blocks):
    n_vert_cut = 0
    n_block = len(blocks)
    vals = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(add > K for add in adds):
            return H * W

        sums = [val + add for val, add in zip(vals, adds)]
        if any(x > K for x in sums):
            n_vert_cut += 1
            vals = adds
        else:
            vals = sums

    return n_vert_cut + n_block - 1


ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    # print(blocks, '->', solve(blocks))
    ans = min(ans, solve(blocks))
print(ans)
### BUGGY CODE ###

N=int(input())
S=list(input())

R=[]
G=[]
B=[]

# リストを作成
for i in range(0,N):
  if S[i]=="R":
    R += [i]
  elif S[i]=="G":
    G += [i]
  else:
    B += [i]

def search(ind, col):
  n=0
  useable_col = ["R","G","B"]
  useable_col.remove(col)
  for i,j in [[0,1],[1,0]]:
    l_col=useable_col[i]
    r_col=useable_col[j]
    if l_col=="R":
      l_col=R
    elif l_col=="G":
      l_col=G
    else:
      l_col=B
    if r_col=="R":
      r_col=R
    elif r_col=="G":
      r_col=G
    else:
      r_col=B
        
    l_useable = [ii for ii in l_col if ii<ind]
    r_useable = [ii for ii in r_col if ii>ind]
    if (l_useable == []) or (r_useable == []):
      continue

    # print(l_useable)
    # print(r_useable)
    l = min(ind, N-1-ind)
    for m in range(1,l+1):
      if ind-m in l_useable and ind+m in r_useable:
        n -= 1
    n += len(l_useable) * len(r_useable)
    # print(len(l_useable))
    # print(len(r_useable))
  return n

n=0
for pivot in range(1,N-1):
  if S[pivot] =="R":
    n += search(pivot, "R")
  elif S[pivot] =="G":
    n += search(pivot, "G")
  else:
    n += search(pivot, "B")

print(n)


### FIXED CODE ###

N=int(input())
S=list(input())

r=0
g=0
b=0

for i in range(N):
  if S[i]=="R":
    r+=1
  elif S[i]=="G":
    g+=1
  else:
    b+=1
    
n=r*g*b

for i in range(N):
  for j in range(i+1,N):
    if S[i]==S[j]:
      continue
    k = 2*j-i
    if k >= N:
      break
    if S[i]==S[k] or S[j]==S[k]:
      continue
    n -= 1
      
print(n)
### BUGGY CODE ###

from bisect import*
N,*L=map(int,open(0).read().split());L.sort()
a=0
for i in range(N):
    for j in range(i+1,N):
      	a+=bisect_left(L,L[i]+L[j],j+1)-bisect(L,abs(L[i]-L[j]),j+1)
print(a)

### FIXED CODE ###

from bisect import*
N,*L=map(int,open(0).read().split());L.sort()
a=0
l=[]
r=[]
for i in range(1001):
    l.append(bisect_left(L,i))
    r.append(bisect(L,i))
for p in L:
    for q in L:
        x=p+q
        y=abs(p-q)
        a+=(l[x]if x<1001else N)-(r[y]if 0<y<1001else(y>1000)*N)
for p in L:
    x=2*p
    a-=3*(l[x]if x<1001else N)
print((a+2*N)//6)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n,q = map(int, input().split())
a_b = [list(map(int, input().split())) for _ in range(n-1)]
p_x = [list(map(int, input().split())) for _ in range(q)]

v = [[] for i in range(n)]
for e in a_b:
    v[e[0]-1].append(e[1]-1)
    v[e[1]-1].append(e[0]-1)
score = [0 for i in range(n)]
for e in p_x:
    score[e[0]-1]+=e[1]
def dfs(p, visited):
    if visited ==[]:
        visited.append(p)
    for c in v[p]:
        if not c in visited:
            visited.append(c)
            score[c]+=score[p]
            if len(visited)==n:
                print(*score)
                #print(visited)
            else:
                dfs(c, visited)
dfs(0, [])

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(1000000)

n,q = map(int, input().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(n-1)]
p_x = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

v = [deque([]) for i in range(n)]
for e in a_b:
    v[e[0]-1]+=[e[1]-1]
    v[e[1]-1]+=[e[0]-1]
score = [0 for i in range(n)]
for e in p_x:
    score[e[0]-1]+=e[1]
def dfs(p, bp=-1):
    while v[p]:
        c =v[p].popleft()
        if c ==bp:
            continue
        #print(p, c, bp)
        score[c]+=score[p]
        dfs(c, bp=p)
visited = [0]                
dfs(0)
print(*score)
### BUGGY CODE ###

from collections import deque


def main():
    K = int(input())
    q = deque([(1, 1)])
    visited = [False] * K
    while len(q):
        n, s = q.popleft()
        if n % K == 0:
            print(s)
            return
        if visited[n % K]:
            continue
        visited[n % K] = True
        q.appendleft((n*10, s))
        q.append((n+1, s+1))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    K = int(input())
    q = deque([(1, 1)])
    visited = [False] * K
    while len(q):
        n, s = q.popleft()
        if visited[n]:
            continue
        visited[n] = True
        if n == 0:
            print(s)
            return
        q.appendleft((n*10 % K, s))
        q.append(((n+1) % K, s+1))


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
from math import factorial
n, m, k = map(int, input().split())
prime_mod = 998244353

def prime_cycle_division(a, b):
  inverted = pow(b, prime_mod-2, prime_mod)
  return (a*inverted)%prime_mod

def prime_factorial(lower, upper):
  total = 1
  for i in range(lower+1, upper+1):
    total = (total*i)%prime_mod
  return total

def mod_comb(places, objects):
  numerator = prime_factorial(places-objects, places)
  denominator = prime_factorial(0, objects)
  ans = prime_cycle_division(numerator, denominator)
  return ans

def combos(j):
  ans = (m*mod_comb(n-1, j))%prime_mod
  ans = (ans*pow(m-1, n-1-j, prime_mod))%prime_mod
  return ans

total = 0
for j in range(k+1):
  total = (total + combos(j))%prime_mod
print(total)

### FIXED CODE ###

import sys
n, m, k = map(int, input().split())
prime_mod = 998244353

def prime_cycle_division(a, b):
  inverted = pow(b, prime_mod-2, prime_mod)
  return (a*inverted)%prime_mod

def gen_mod_combs(places):
  k = 0
  x = 1
  while True:
    yield x
    factor = prime_cycle_division(places-k, k+1)
    x = (x*factor)%prime_mod
    k += 1

def combos(j):
  ans = (m*next(gen))%prime_mod
  ans = (ans*pow(m-1, n-1-j, prime_mod))%prime_mod
  return ans

total = 0
gen = gen_mod_combs(n-1)
for j in range(k+1):
  total = (total + combos(j))%prime_mod
print(total)
### BUGGY CODE ###

N,M = map(int, input().split())
A = sorted(map(int, input().split()))[::-1]

total = 0
for i in range(M):
    A[0] = A[0] // 2
    for j in range(N-1):
        if A[j] < A[j+1]:
            tmp = A[j]
            A[j] = A[j+1]
            A[j+1] = tmp
        else:
            break
print(sum(A))
            



### FIXED CODE ###

import heapq
import math

N,M = map(int, input().split())
A = list(map(lambda x : int(x) * -1, input().split()))

heapq.heapify(A)
 
for i in range(M):
    tmp = heapq.heappop(A)
    heapq.heappush(A, int(tmp / 2))
print(-sum(A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
a=[int(input()) for i in range(int(input()))]
count=0
for x in a:
    if a.count(x)%2==1:
        count+=1
print(count)

### FIXED CODE ###

import collections
n=int(input())
count=0
a=[int(input()) for _ in range(n)]
a=collections.Counter(a)

for key,value in a.items():
    if value%2==1:
        count+=1
print(count)
### BUGGY CODE ###

N = int(input())
nums = list(map(int, input().split()))
ans = [0] * N

for i in reversed(range(1,N+1)):
    count = 0
    total = 0
    for j in range(i,N+1):
        if j % i == 0:
            count += 1
            # 既にfixされた数を加算
            total += ans[j-1]
    # 倍数が一つのとき
    if count == 1:
        if nums[i-1] == 0:
            ans[i-1] = 0
        else:
            ans[i-1] = 1
    # 倍数が複数ある
    else:
        # 指定が偶数
        if nums[i-1] == 0:
            if total % 2 != 0:
                ans[i-1] = 1
        else:
            if total % 2 == 0:
                ans[i-1] = 1


result = [i+1 for i in range(len(ans)) if ans[i] == 1]
result = [str(i) for i in result]
print(len(result))
print(" ".join(result))


### FIXED CODE ###

N = int(input())
nums = list(map(int, input().split()))
ans = [0] * N

for i in reversed(range(1,N+1)):
    count = 0
    total = 0
    # 倍数
    for j in range(i, N+1, i):
        count += 1
        total += ans[j-1]
    # 倍数が一つのとき
    if count == 1:
        if nums[i-1] == 0:
            ans[i-1] = 0
        else:
            ans[i-1] = 1
    # 倍数が複数ある
    else:
        # 指定が偶数
        if nums[i-1] == 0:
            if total % 2 != 0:
                ans[i-1] = 1
        else:
            if total % 2 == 0:
                ans[i-1] = 1


# 出力フォーマット処理
result = [i+1 for i in range(len(ans)) if ans[i] == 1]
result = [str(i) for i in result]
print(len(result))
print(" ".join(result))
### BUGGY CODE ###

from collections import deque

# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]


# bfsによる色付けを行う
def bfs(now_node):
    queue = deque([[tree[now_node], 0, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1


bfs(0)
max_val = 0
for row in visited_edge:
    tmp_max = max(row)
    if max_val < tmp_max:
        max_val = tmp_max
print(max_val)
for a, b in input_list:
    print(visited_edge[a][b])

### FIXED CODE ###

from collections import deque
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
# visited_edge = [[0] * N for _ in range(N)]
dict = {}
'''
# bfsによる色付けを行う
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val
'''
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            key = tuple(sorted([now_node, next_node]))
            if not dict.get(key) is None:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            dict[key] = now_color
            # visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val

ans = bfs(0)
print(ans)
for a, b in input_list:
    # print(visited_edge[a][b])
    print(dict[tuple(sorted([a,b]))])