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

def 通るかな():
    X,Y,Z,K = [int(_) for _ in input().split()]
    #aA = sorted((int(_) for _ in input().split()),reverse=True)
    #aB = sorted((int(_) for _ in input().split()),reverse=True)
    #aC = sorted((int(_) for _ in input().split()),reverse=True)
    aA = [int(_) for _ in input().split()]
    aB = [int(_) for _ in input().split()]
    aC = [int(_) for _ in input().split()]

    aD =[0] *(X*Y)
    i=0
    for a in aA:
        for b in aB:
            aD[i]=a+b
            i+=1
    aD.sort(reverse=True)
    if 3000 < X*Y :
        aD=aD[:3000]
    iL = len(aD)
    aE = [0] * (iL*Z)
    i = 0
    for d in aD:
        for c in aC:
            aE[i] = d+c
            i+=1
    aE.sort(reverse=True)
    print(*aE[:K],sep="\n")
通るかな()


### FIXED CODE ###

def 解法3優先度付きキュー():
    import heapq
    X,Y,Z,K = [int(_) for _ in input().split()]
    aA = sorted((int(_) for _ in input().split()),reverse=True)
    aB = sorted((int(_) for _ in input().split()),reverse=True)
    aC = sorted((int(_) for _ in input().split()),reverse=True)
    dS=set()
    aAns = [0]*K
    aQ = []
    def fPush(aQ,i,j,k):
        if X <= i :
            i = X-1
        if Y <= j:
            j = Y-1
        if Z <= k:
            k = Z-1
        if (i,j,k) not in dS:
            heapq.heappush(aQ,(-1*(aA[i]+aB[j]+aC[k]),i,j,k))
            dS.add((i,j,k))
    def fPop(aQ):
        iD,i,j,k = heapq.heappop(aQ)
        return (-1*iD,i,j,k)
    fPush(aQ,0,0,0)
    for iU in range(K):
        aAns[iU],i,j,k = fPop(aQ)
        fPush(aQ,i+1,j,k)
        fPush(aQ,i,j+1,k)
        fPush(aQ,i,j,k+1)

    print(*aAns,sep="\n")

解法3優先度付きキュー()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
adjacency_list = [list(map(int, input().split())) for i in range(n)]
egde = []
for u in range(n):
    for v in range(u):
        egde.append([adjacency_list[u][v], u, v])
egde.sort()

ans = 0
for d, u, v in egde:
    for w in range(n):
        d2 = adjacency_list[u][w] + adjacency_list[w][v]
        if d == d2:
            if w == u or w == v:
                continue
            break
        elif d > d2:
            print(-1)
            exit()
    else:
        ans += d

print(ans)

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
n = int(input())
G = np.array([list(map(int, input().split())) for _ in range(n)], dtype=float)
use = np.ones((n,n),dtype=bool)
impossible = np.zeros((n,n),dtype=bool)
for w in range(n):
    D = sum(np.meshgrid(G[w], G[w]))
    D[w] = np.inf
    D[:,w] = np.inf
    use &= ~(G == D)
    impossible |= G > D
if impossible.any():
    print(-1)
else:
    print(int(np.sum(G[use]) / 2))
### BUGGY CODE ###

N, X, Y = map(int, input().split(' '))
dist = [[0 for _ in range(N + 10)] for _ in range(N + 10)]
dist[X][Y] = 1
res = [0 for i in range(N + 10)]
for i in range(1, N):
  for j in range(i + 1, N + 1):
    dist[i][j] = min(j - i, abs(j - X) + 1 + abs(i - Y), abs(j - Y) + 1 + abs(i - X))
    res[dist[i][j]] += 1
for i in range(1, N):
  print(res[i])

### FIXED CODE ###

N, X, Y = map(int, input().split(' '))
dist = [[0 for _ in range(N + 10)] for _ in range(N + 10)]
dist[X][Y] = 1
res = [0 for i in range(N + 10)]
for i in range(1, N):
  for j in range(i + 1, N + 1):
    dist[i][j] = min(j - i, abs(j - X) + 1 + abs(i - Y), abs(j - Y) + 1 + abs(i - X))
    res[dist[i][j]] += 1
for i in range(1, N):
  print(res[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from fractions import Fraction

def main(): 
    N = int(input())
    x = [int(i) for i in input().split()]

    MOD = 10**9+7

    frac = [""] * (N-1)
    for i in range(N-1):
        if i == 0:
            frac[i] = Fraction(1,i+1)
        else:
            frac[i] = (frac[i-1] + Fraction(1,i+1))

    answer = 0
    for i in range(N-1):
        dist = (x[i+1] - x[i]) % MOD
        answer = (answer + dist * frac[i]) % MOD
    for i in range(1,N):
        answer = (answer * i) % MOD

    print(int(answer))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

# 1~nまでの逆元(mod m) O(n)
def mod_inv_list(n:int, m:int):
    # inv_t[i]: iの法mの下での逆元
    inv_t = [0] + [1]
    for i in range(2,n):
        inv_t += [inv_t[m % i] * (m - m//i) % m]
    return inv_t

def main():
    N = int(input())
    x = [int(i) for i in input().split()]
    MOD = 10**9 + 7

    inv_acum = mod_inv_list(N,MOD)
    for i in range(1,N):
        inv_acum[i] = (inv_acum[i] + inv_acum[i-1]) % MOD

    ans = 0
    for i in range(1,N):
        ans += (x[i] - x[i-1]) * inv_acum[i]
        ans %= MOD

    for i in range(1,N):
        ans = (ans * i) % MOD

    print(ans)

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

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

for i in range(n):
  b = a.copy()
  del a[i]
  print(max(a))
  a = b.copy()

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m_num = max(a)
m_index = [i for i, x in enumerate(a) if x == m_num]

if len(m_index) > 1:
  for i in range(n):
    print(m_num)
else:
  if len(a) == 1:
    print(a[0])
  else:
    m2_num = sorted(a)[-2]
    for i in range(n):
      if (i in m_index):
        print(m2_num)
      else:
        print(m_num)
### BUGGY CODE ###

#!/usr/bin/env python3

N, K = map(int, input().split())
A = list(map(int, input().split()))

for i in range(N):
    A[i] -= 1

b = bin(K)
D = {0:list(range(N))} # ダブリングマトリクス
D[1] = [A[D[0][i]] for i in range(N)]

for i in range(1, len(b)-2):
    D[2**i] = [D[2**(i-1)][D[2**(i-1)][j]] for j in range(N)]


n = 2**(len(b[2:])-1)
S = D[n][0] # 初期状態
keta = len(b[2:]) - 2
for j in range(len(b[3:])):
    k = 2**keta
    if b[j+3] == '1':
        S = D[k][S]
    keta -= 1

print(S+1)


### FIXED CODE ###

#!/usr/bin/env python3

N, K = map(int, input().split())
A = list(map(int, input().split()))

for i in range(N):
    A[i] -= 1

tele = [0]
#tele = [0,A[0]-1]
z = 0
s = 0
#B = {0:0,A[0]-1:1}
B = {0:0}
for i in range(N):
    if A[tele[-1]] in B and len(B) != 1:
        s = B[A[tele[-1]]]
        break
    B[A[tele[-1]]] = i+1
    tele.append(A[tele[-1]])
    z = tele[-1]

if K <= s:
    print(tele[K]+1)
else:
    K -= s
    amari = K%(len(tele[s:len(tele)]))
    tele = tele[s:len(tele)]*2
    print(tele[amari]+1)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A_lis = [int(input()) for _ in range(Q)]

for i in range(N):
    if K-Q+A_lis.count(i+1)>0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N, K, Q = map(int, input().split())
A_lis = [int(input()) for _ in range(Q)]
#A_lis.sort()

B_lis = [int(K-Q)]*N
for A in A_lis:
    B_lis[A-1]+=1
for B in B_lis:
    if B>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from queue import Queue

N, M = [int(n) for n in input().split()]
graph = {n: [] for n in range(1, N+1)}
for m in range(M):
    A, B = [int(n) for n in input().split()]
    graph[A].append(B)
    graph[B].append(A)

starts_ = sorted(graph.keys(), key=lambda x: len(graph[x]))
starts = iter([starts_[n:n+3] for n in range(0, len(starts_), 3)])

result_path = []
for start in starts:
    q = Queue()
    #needs_start = graph[start]
    for s in start:
        q.put([s])
    while not q.empty():
        path = q.get()            
        for t in graph[path[-1]]:
            if t in path:
                continue
            if len(set(graph[path[0]] + graph[t]) - set(path + [t])) == 0:
                result_path = path + [t]
                q = Queue()
                break
            else:
                if len(path + [t]) < N:
                    q.put(path+[t])
                
    if len(result_path) > 0:
        break
print(len(result_path))
result = ""
for r in result_path:
    result += " {}".format(r)
print(result[1:])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
def inpl(): return map(int, input().split())

N, M = inpl()
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = inpl()
    G[a].append(b)
    G[b].append(a)

searched = [False] * (N+1)

m = 1
searched[m] = True

ans = []
def dfs(c):
    global ans
    searched[c] = True
    for d in G[c]:
        if not searched[d]:
            ans.append(c)
            dfs(d)
            break 
    else:
        ans.append(c)
    
dfs(1)
ans = ans[:0:-1]
dfs(1)

print(len(ans))
print(*ans)
### BUGGY CODE ###

import numpy as np

def widespread_2():
	n, a, b = map(int, raw_input().split(" "))
	monsters = []
	for i in range(n):
		monsters.append(int(raw_input()))
	# as a>b holds
	dif_a_b = a - b
	monsters = np.array(monsters)
	max_ans = int(max(monsters)/b)+1
	min_ans = int(max(monsters)/a)-1
	# using binary search
	while True:
		current_attepmt = int((max_ans+min_ans)/2)
		# print current_attepmt
		re = _inner_widespread_2(monsters, current_attepmt, a, b)
		# print re
		if re>current_attepmt:
			min_ans = current_attepmt
		elif re<current_attepmt:
			max_ans = current_attepmt
		else:
			print current_attepmt
			return

		if current_attepmt==int((max_ans+min_ans)/2):
			print max_ans
			return


def _inner_widespread_2(monsters, attemps, a, b):
	x = monsters-b*attemps
	dif = a-b
	re = 0
	for e in reversed(sorted(x)):
		if e<=0:
			break
		else:
			if e%dif==0:
				re = re+e/dif
			else:
				re = re + int(e/dif)+1
	return re


if __name__ == "__main__":
	widespread_2()

### FIXED CODE ###

def widespread_2():
	n, a, b = map(int, raw_input().split(" "))
	monsters = []
	for i in range(n):
		monsters.append(int(raw_input()))
	# as a>b holds
	dif_a_b = a - b
	max_ans = int(max(monsters)/b)+1
	min_ans = int(max(monsters)/a)-1
	# using binary search
	while min_ans+1 < max_ans:
		current_attepmt = (max_ans+min_ans)/2
		# print current_attepmt
		re = _inner_widespread_2(monsters, current_attepmt, a, b)
		# print re
		if re>current_attepmt:
			min_ans = current_attepmt
		else:
			max_ans = current_attepmt
	print max_ans


def _inner_widespread_2(monsters, attemps, a, b):
	dif = a-b
	re = 0
	for e in monsters:
		update_e = e-b*attemps
		if update_e>0:
			if update_e%dif==0:
				re = re+update_e/dif
			else:
				re = re + int(update_e/dif)+1
	return re


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

s=input()
q=int(input())

rev=1

sf=[]
sb=[]

for _ in range(0,q):
  n=input().split()
  if n[0]=="1":
    rev*=-1
  else:
    if (n[1]=="1" and rev==1) or (n[1]=="2" and rev==-1):
      sf.insert(0,n[2])
    else:
      sb.append(n[2])

s=''.join(sf)+s+''.join(sb)

if rev==1:
  print(s)
else:
  print(s[::-1])


### FIXED CODE ###

s=input()
q=int(input())

rev=1

sf=""
sb=s

for _ in range(0,q):
  n=input().split()
  if n[0]=="1":
    rev*=-1
  else:
    if (n[1]=="1" and rev==1) or (n[1]=="2" and rev==-1):
      sf+=n[2]
    else:
      sb+=n[2]

s=sf[::-1]+sb

if rev==1:
  print(s)
else:
  print(s[::-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
edges = {}
p = []
done_nodes = set()
def dfs(target_node, keisyo_point):
    global p
    done_nodes.add(target_node)
    p[target_node] += keisyo_point
    next_node = edges[target_node]
    if not next_node:
        return
    else:
        for next in next_node:
            if next in done_nodes:
                pass
            else:
                dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    #edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
    p = [0] * (n + 1)
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1, 0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
edges = {}
p = {}
done_nodes = set()

def dfs(target_node, keisyo_point):
    global p
    done_nodes.add(target_node)
    p[target_node] += keisyo_point
    next_node = edges[target_node]
    if not next_node:
        return
    else:
        for next in next_node:
            #edges[next].pop(edges[next].index(target_node))
            #dfs(next, p[target_node])
            if next in done_nodes:
                pass
            else:
                dfs(next, p[target_node])

def main():
    global edges, p
    n, q = map(int, input().split())
    edges = {e: [] for e in range(1, n+1)}
    for _ in range(n - 1):
        a, b = tuple(map(int, input().split()))
        edges[a].append(b)
        edges[b].append(a)
    p = {e: 0 for e in range(1, n+1)}
    for _ in range(q):
        p1, x1 = map(int, input().split())
        p[p1] += x1

    dfs(1, 0)
    for i1 in range(1, n + 1):
        print(p[i1], end=' ')

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

n = int(input())
s = input()

ans = 0
for i in range(1,n+1):
  for j in range(i, n+1):
    for k in range(j, n+1):
      if s[i-1] != s[j-1] and s[i-1] != s[k-1] and s[j-1] != s[k-1] and j-i != k-j:
        ans += 1

print(ans)



### FIXED CODE ###

n = int(input())
s = input()

ans = s.count('R')*s.count('G')*s.count('B')
for i in range(n):
    for j in range(i,n-1):
        k = 2*j - i
        if k >= n:
            continue
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            ans -= 1


print(ans)
### BUGGY CODE ###

s = list(input())

ans = 0
while True:
    i = 0
    found = False
    while i+2 < len(s):
        if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
            ans += 1
            s[i] = 'B'
            s[i+1] = 'C'
            s[i+2] = 'A'
            i += 2
            found = True
        else:
            i += 1
    if not found:
        break

print(ans)

### FIXED CODE ###

s = input()

s = s.replace('BC', 'D')
ans = 0
a = 0
for c in s:
    if c == 'A':
        a += 1
    elif c == 'D':
        ans += a
    else:
        a = 0

print(ans)
### BUGGY CODE ###

S = list(input())

def search(now, i, S):
    cnt = 1
    while True:
            if now == "L":
                if S[i-cnt] == "R":
                    if cnt %2 == 0:
                        return i-cnt
                    else:
                        return i-cnt+1
                else:
                    cnt += 1
            elif now == "R":
                if S[i+cnt] == "L":
                    if cnt %2 == 0:
                        return i+cnt
                    else:
                        return i+cnt-1
                else:
                    cnt += 1
        
l = len(S)
ans = [0 for _ in range(l)]
for i in range(l):
    now = S[i]
    index = search(now, i, S)
    ans[index] += 1

print(" ".join([str(s) for s in ans]))

### FIXED CODE ###

S = list(input())

def search(now, i, S):
    cnt = 1
    while True:
            if now == "L":
                if S[i-cnt] == "R":
                    if cnt %2 == 0:
                        return i-cnt, i-cnt+1
                    else:
                        return i-cnt+1, i-cnt
                else:
                    cnt += 1
            elif now == "R":
                if S[i+cnt] == "L":
                    if cnt %2 == 0:
                        return i+cnt, i+cnt-1
                    else:
                        return i+cnt-1, i+cnt
                else:
                    cnt += 1
        
l = len(S)
ans = [0 for _ in range(l)]
before = 0
for i in range(l):
    now = S[i]
    if before == now:
        tmp = index
        index = nex
        nex = tmp
    else:
        index, nex = search(now, i, S)
    ans[index] += 1
    before = now

print(" ".join([str(s) for s in ans]))
### BUGGY CODE ###

import heapq

N, M, S = map(int, input().split())
Cost = [[] for _ in range(N)]
Change = [[0]*2 for _ in range(N)]
A_m = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    A_m = max(A_m, a)
    Cost[u-1].append([v-1, a, b])
    Cost[v-1].append([u-1, a, b])
for i in range(N):
    c, d = map(int, input().split())
    Change[i][0] = c
    Change[i][1] = d
if S > A_m*N:
    S = A_m*N

def dijkstra(N, start, Cost, Change):
    Ans = [10**12]*N
    Ans[0] = 0
    minHeap = []
    used = [[10**18]*(A_m*N + 1) for _ in range(N)]
    used[start][S] = 0
    heapq.heappush(minHeap, (0, S, start))
    while minHeap:
        (c, hold, current) = heapq.heappop(minHeap)
        j = 1
        for i in range(N):
            if Ans[i] > c:
                j = 0
                break
        if j == 1:
            break
        for P in Cost[current]:
            road, a, b = P
            if hold >= a:
                if used[road][hold - a] > c + b:
                    used[road][hold - a] = c + b
                    heapq.heappush(minHeap, (c + b, hold - a, road))
                if Ans[road] > c + b:
                    Ans[road] = c + b
        if hold + Change[current][0] <= A_m*N:
            if used[current][hold + Change[current][0]] > c + Change[current][1]:
                heapq.heappush(minHeap, (c + Change[current][1], hold + Change[current][0], current))
    return Ans

T = dijkstra(N, 0, Cost, Change)
for i in T[1:]:
    print(i)

### FIXED CODE ###

import heapq

N, M, S = map(int, input().split())
Cost = [[] for _ in range(N)]
Change = [[0]*2 for _ in range(N)]
A_m = 0
for i in range(M):
    u, v, a, b = map(int, input().split())
    A_m = max(A_m, a)
    Cost[u-1].append([v-1, a, b])
    Cost[v-1].append([u-1, a, b])
for i in range(N):
    c, d = map(int, input().split())
    Change[i][0] = c
    Change[i][1] = d
if S > A_m*N:
    S = A_m*N

def dijkstra(N, start, Cost, Change):
    rich = [[] for _ in range(N+1)]
    Ans = [10**18]*N
    Ans[0] = 0
    minHeap = []
    used = [[10**18]*(A_m*N + 1) for _ in range(N)]
    used[start][S] = 0
    heapq.heappush(minHeap, (0, S, start))
    while minHeap:
        (c, hold, current) = heapq.heappop(minHeap)
        if rich[current] and rich[current][-1] >= hold:
            continue
        rich[current].append(hold)
        j = 1
        for i in range(N):
            if Ans[i] > c:
                j = 0
                break
        if j == 1:
            break
        for P in Cost[current]:
            road, a, b = P
            if hold >= a:
                if used[road][hold - a] > c + b:
                    used[road][hold - a] = c + b
                    heapq.heappush(minHeap, (c + b, hold - a, road))
                if Ans[road] > c + b:
                    Ans[road] = c + b
        if hold + Change[current][0] <= A_m*N:
            if used[current][hold + Change[current][0]] > c + Change[current][1]:
                heapq.heappush(minHeap, (c + Change[current][1], hold + Change[current][0], current))
    return Ans

T = dijkstra(N, 0, Cost, Change)
for i in T[1:]:
    print(i)
### BUGGY CODE ###

h,w = map(int,input().split())
a = []
for i in range(h):
  s = list(map(int,input().split()))
  a.append(s)
b = []
for i in range(h):
  t = list(map(int,input().split()))
  b.append(t)

dp = [[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(abs(a[0][0]-b[0][0]))

for i in range(h):
  for j in range(w):
    for k in dp[i][j]:
        if i < h-1:
          c = abs(a[i+1][j]-b[i+1][j])
          if k+c < 6321:
            dp[i+1][j].add(k+c)
          dp[i+1][j].add(abs(k-c))
        if j < w-1:
          d = abs(a[i][j+1]-b[i][j+1])
          if k+d < 6321:
            dp[i][j+1].add(k+d)
          dp[i][j+1].add(abs(k-d))
      
ans = list(dp[h-1][w-1])
print(min(ans))

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  h,w = map(int,readline().split())
  a = []
  for i in range(h):
    s = list(map(int,readline().split()))
    a.append(s)
  b = []
  for i in range(h):
    t = list(map(int,readline().split()))
    b.append(t)
  C = [[0]*w for _ in range(h)]
  for i in range(h):
      for j in range(w):
          C[i][j] = abs(a[i][j] - b[i][j])

  dp = [[[0]*6321 for i in range(w)] for _ in range(h)]
  dp[0][0][C[0][0]] = 1

  for i in range(h):
    for j in range(w):
      for k in range(6321):
        if dp[i][j][k]:
          if i < h-1:
            c = C[i+1][j]
            if k+c < 6321:
              dp[i+1][j][k+c] = 1
            dp[i+1][j][abs(k-c)] = 1
          if j < w-1:
            d = C[i][j+1]
            if k+d < 6321:
              dp[i][j+1][k+d] = 1
            dp[i][j+1][abs(k-d)] = 1

  for i in range(6321):
    if dp[h-1][w-1][i]:
      print(i)
      break
      
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))


for i in range(k):
    b = [0] * (n+1)
    for j in range(n):
        l = max(0, j-a[j])
        r = min(n, j+a[j]+1)
        b[l] += 1
        b[r] -= 1
    for j in range(n):
        b[j+1] += b[j]
    b.pop()
    if a == b:
        break
    a = b
print(' '.join(map(str, a)))

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))


for i in range(k):
    b = [0] * (n+1)
    for j in range(n):
        l = max(0, j-a[j])
        r = min(n, j+a[j]+1)
        b[l] += 1
        b[r] -= 1
    for j in range(n):
        b[j+1] += b[j]
    b.pop()
    if a == b:
        break
    a = b
print(' '.join(map(str, a)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import numpy as np

N,B = map(int,input().split())
X = np.array(input().split(), dtype=np.int64)

Xcum = X.cumsum()

coef = np.full(N,2,dtype=np.int64)
coef[0] = 5
coef[1] = 0

answer = 10**18
for n in range(1,N+1):
    # 往復回数
    x = Xcum[::-1][::n]
    cost = (x*coef[:len(x)]).sum() + B*(N+n)
    answer = min(answer, cost)

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import itertools

N,B = map(int,input().split())
X = [int(x) for x in input().split()]

Xcum = tuple(itertools.accumulate(X))

coef = [2] * N
coef[0] = 5
coef[1] = 0

answer = min(sum(x*y for x,y in zip(Xcum[::-n], coef[:1+(N-1)//n])) + B*(N+n) for n in range(1,N+1))
print(answer)
### BUGGY CODE ###

from collections import deque
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]
colors = [[-1 for _ in range(n)] for _ in range(n)]
visit = [-1 for _ in range(n)]
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)
visit[0] = 0
q = deque([0])
while q:
    s = q.popleft()
    d = 0
    for i in tree[s]:
        if visit[i]<0:
            d += 1 +((d+1)==visit[s])
            colors[s][i] = visit[i] = d
            q.append(i)
print(max([len(i) for i in tree]))
result = []
for a, b in ab:
    print(colors[a-1][b-1])

### FIXED CODE ###

from collections import deque
def main():
    n = int(input())
    ab = []
    visit = [-1 for _ in range(n+1)]
    tree = [[] for _ in range(n+1)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a, b])
        tree[a].append(b)
        tree[b].append(a)
    visit[1]=0
    q = deque([1])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 + (1+d==visit[s])
                visit[i] = d
                q.append(i)
    print(max(visit))
    for a, b in ab:
        print(visit[b])

if __name__=="__main__":
    main()