Harryxun/stf_run huggingface dataset:
H,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

DP=[10**9]*(H+max(A)-1)#DPの箱をH+max(A)-1個用意する

for Ai in zip(A,B):#すでにあるものを埋める
    DP[Ai-1]=Bi

for dpi in range(H+max(A)-1):
    kouho=[]
    kouho.append(DP[dpi])
    for Ai,Bi in zip(A,B):
        if dpi-Ai>=0:
            kouho.append(DP[dpi-Ai]+Bi)
    DP[dpi]=min(kouho)


print(min(DP[H-1:]))

### FIXED CODE ###

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

max_a = max(a for a, _ in ab)
dp = [0] * (h+max_a)

for i in range(0, h+max_a):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i-a] + b for a,b in ab) 

print(min(dp[h:]))
import fractions
import functools
import sys
sys.setrecursionlimit(100000000)

n=int(input())
a = [int(i) for i in input().split()]
a.sort()

if len(a) == 2:
  print(max(a))
  sys.exit()
  
gcd_a = functools.reduce(fractions.gcd, a)
a=[i//gcd_a for i in a]

cnt = 0
gcd_0 = functools.reduce(fractions.gcd, a[1:])
for i in range(1,len(a)):
  if fractions.gcd(a[0],a[i]) == 1:
    so = i
    cnt+=1
    if cnt == 2:
      print(max(gcd_a,gcd_0*gcd_a))
      sys.exit()
      
if cnt == 0:
  print(gcd_a)
    sys.exit()

a_i = [i for i in a if i != a[so]]
gcd_i = functools.reduce(fractions.gcd, a_i)

print(max(gcd_0,gcd_i)*gcd_a)
   

### FIXED CODE ###

import fractions
import functools
import sys

n=int(input())
a = [int(i) for i in input().split()]
a.sort()

if len(a) == 2:
  print(max(a))
  sys.exit()
  
gcd_a = functools.reduce(fractions.gcd, a)
a=[i//gcd_a for i in a]

so = 0
cnt = 0
gcd_0 = functools.reduce(fractions.gcd, a[1:])
for i in range(1,len(a)):
  if fractions.gcd(a[0],a[i]) == 1:
    so = i
    cnt+=1
    if cnt == 2:
      print(max(gcd_a,gcd_0*gcd_a))
      sys.exit()

a_i = [i for i in a if i != a[so]]
gcd_i = functools.reduce(fractions.gcd, a_i)

print(max(gcd_0,gcd_i)*gcd_a)
a, b, c, d = map( int, input().split() )
while True:
    c = c - b
    if c < = 0:
  		print( "Yes" )
  		break
	a = a - d
  	if a < = 0:
  		print( "No" )
  		break
        

### FIXED CODE ###


a, b, c, d = map( int, input().split() )
#print( a, b, c, d )
 
for i in range( 200 ):
    c = c - b
    if c <= 0:
        print( "Yes" )
        exit()
 
    a = a - d
    if a <= 0:
        print( "No" )
        exit()
n,x = map(int,input().split())
l = list(map(int,input().split()))
c = 1
D = 0
li = []
for i in range(1,n+1):
  D = D + l[i]
  if D <= x:
    c += 1
  else:
    li.append(D)
    
if max(li) > x:
  print(n+1)
else:
  print(c)

### FIXED CODE ###

n,x = map(int,input().split())
l = list(map(int,input().split()))
c = 1
D = 0
li = []
for i in range(1,n+1):
  D = D + l[i-1]
  if D <= x:
    c += 1
print(c)
h1=input()
h = h1*h1*h1
print(h)

### FIXED CODE ###

x = int(input())
print(x*x*x)
dreameraser

### FIXED CODE ###

s=list(input())
n = len(s)

c=0
k=0
while c==0:
    if k ==n:
        c = 1
    else:
        
        if k + 7 <= n-1 and s[k]=='d' and s[k+1] == 'r' and s[k+2] == 'e' and s[k+3] == 'a' and s[k+4] == 'm' and s[k+5] == 'e' and s[k+6] == 'r' and s[k+7] == 'a':
            k += 5
        elif k + 6 <= n-1 and s[k]=='d' and s[k+1] == 'r' and s[k+2] == 'e' and s[k+3] == 'a' and s[k+4] == 'm' and s[k+5] == 'e' and s[k+6] == 'r':
            k += 7
        elif k + 4 <= n-1 and s[k]=='d' and s[k+1] == 'r' and s[k+2] == 'e' and s[k+3] == 'a' and s[k+4] == 'm':
            k += 5
        elif k+6 <= n-1 and s[k] == 'e' and s[k+1] == 'r' and s[k+2] == 'a' and s[k+3] == 's' and s[k+4] == 'e' and  s[k+5] == 'r' and s[k+6] == 'a':
            k+= 5
        elif k+5 <= n-1 and s[k] == 'e' and s[k+1] == 'r' and s[k+2] == 'a' and s[k+3] == 's' and s[k+4] == 'e' and  s[k+5] == 'r':
            k += 6
        elif k+4 <= n-1 and s[k] == 'e' and s[k+1] == 'r' and s[k+2] == 'a' and s[k+3] == 's' and s[k+4] == 'e':
            k += 5
        else:
            c = 1

if k == n:
    print('YES')
else:
    print('NO')
a, b, c = (int(i) for i in input().split())  
    d=(a+b+c)/17
    e=(max(a,b)-2+max(a,c)+max(b,c))/17
     
    if(d==1 and e==1): print("YES")
    else: print("NO")

### FIXED CODE ###

a, b, c = (int(i) for i in input().split())
d=(a+b+c)/17
e=(max(a,b)-2+max(a,c)+max(b,c))/17
     
if(d==1 and e==1): print("YES")
else: print("NO")
import math
A, B = map(int, input().split())

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

ans = lcm(A, B)
print(ans)

### FIXED CODE ###

from fractions import gcd
A, B = map(int, input().split())

def lcm(x, y):
    return (x * y) // gcd(x, y)

ans = lcm(A, B)
print(ans)
n, m = map(int, input().split())

if n = 0:
  pn = 0
  
if m = 0:
  pm = 0

else:
  pn = n*(n-1) // 2
  pm = m*(m-1) // 2

p = pn + pm
print(p)

### FIXED CODE ###

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

p = n * (n - 1) // 2 + m * (m - 1) // 2

print(p)
N, N, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]

abcd.sort()
total = 0

for i in range(2 ** Q):
    now = str(format(i, 'b')).zfill(Q)
    A = [-1] * N
    flag = 0
    tmp = 0
    for j in range(Q):
        if now[j] == '1':
            mi = abcd[j][0] - 1
            ma = abcd[j][1] - 1
            if A[mi] == -1:
                A[mi] = 0
            if A[ma] == -1:
                A[ma] = A[mi] + abcd[j][2]
            elif A[ma] != A[mi] + abcd[j][2]:
                flag = 1
                break
            tmp += abcd[j][3]
    if tmp > total:
        total = tmp
print(total)

### FIXED CODE ###

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]

A = [0] * N
A[0] = 1
result = []


def dfs(d, n, A):
    # 深さがNを超えるか、数字がMを超えたらreturn
    if d > N or n > M:
        return
    # 深さdの数字にnを入力
    A[d - 1] = n

    # 最深まで値が入ったら総和を計算
    if d == N:
        total = 0
        for i in range(Q):
            ai = abcd[i][0]
            bi = abcd[i][1]
            ci = abcd[i][2]
            di = abcd[i][3]
            if A[bi - 1] - A[ai - 1] == ci:
                total += di
        result.append(total)

    dfs(d + 1, n, A)
    dfs(d, n + 1, A)


dfs(2, 1, A)

print(max(result))
from collections import deque

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)

# make a function
def add(lst, p, x):
    if child[p] == []:
        lst[p] += x
    else:
        lst[p] += x
        for v in child[p]:
            add(lst, v, x)

## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    add(count, p, x)
    
print(' '.join(map(str, count)))

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

N, Q = map(int, input().split())
repn = [[] for i in range(N)]

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

count = [0] * N

## analysis of tree structure
parent = [-1] + ['nul'] * (N - 1)
child = [[] for i in range(N)]
child[0] = repn[0]

for v in child[0]:
    parent[v] = 0

deq = deque(repn[0])

while deq:
    v = deq.popleft()
    for w in repn[v]:
        if parent[v] == w:
            pass
        else:
            parent[w] = v
            child[v].append(w)
            deq.append(w)


## soltion
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    count[p] += x
    
deq = deque([0])
while deq:
    v = deq.popleft()
    for w in child[v]:
        count[w] += count[v]
        deq.append(w)



print(' '.join(map(str, count)))
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

d = I()
contest = LI()
mylist = [LI() for i in range(26)]
day = [0] * 26
result = 0
for i in range(d):
    temp = I()
    result += mylist[i][temp-1]
    day = [j+1 for j in day]
    day[temp-1] = 0
    for k in range(26):
        result -= day[k] * contest[k]
    print(result)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

d = I()
contest = LI()
mylist = [LI() for i in range(d)]
day = [0] * 26
result = 0

for i in range(d):
    temp = I()
    result += mylist[i][temp-1]
    day = [j+1 for j in day]
    day[temp-1] = 0
    for k in range(26):
        result -= day[k] * contest[k]
    print(result)
import math

(x1, y1, x2, y2) = [float(i) for i in input().split()]
distance = math.sqrt((x2 - x1) ** 2 + (y2 - u1) ** 2)
print('{0:.5f}'.format(distance))

### FIXED CODE ###

import math

(x1, y1, x2, y2) = [float(i) for i in input().split()]
distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
print('{0:.5f}'.format(distance))
S, T = map(str, input().split())
A, B = map(int, input().split())
U = input()

a = A - 1
b = B - 1

if U == S:
  print({} {}.format(a,B))
else:
  print({} {}.format(A,b))


### FIXED CODE ###

S, T = map(str, input().split())
A, B = map(int, input().split())
U = input()

a = A - 1
b = B - 1

if U == S:
  print('{} {}'.format(a,B))
else:
  print('{} {}'.format(A,b))
while 1:
	try:
		n = input()
		x = 0
		if n < 37:
			for a in range(10):
				for b in range(10):
					for c in range(10):
						for d in range(10):
							if a + b + c + d == n:
								c += 1
			print c
		except EOFError:
			break

### FIXED CODE ###

while 1:
	try:
		n = input()
		x = 0
		if n < 37:
			for a in range(10):
				for b in range(10):
					for c in range(10):
						for d in range(10):
							if a + b + c + d == n:
									x += 1
		print x
	except EOFError:
		break
import sys


def LI():
    return list(map(int, input().split()))


def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y % x, x)


N = LI()
A = LI()
g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    print("not coprime")
    sys.exit()

sosu = [True]*(10**6)
sosu[0] = sosu[1] = False
for i in range(2, 10**6):
    if not sosu[i]:
        continue
    for j in range(i*i, 10**6, i):
        sosu[j] = False

used = [False]*(10**6)
prime = [a for a in A if sosu[a]]
for i in prime:
    used[i] = True
not_prime = [a for a in A if not sosu[a]]
ruto_prime = [a for a in range(1000) if sosu[a]]
for i in not_prime:
    for j in ruto_prime:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
        used[i] = True
print("pairwise coprime")


### FIXED CODE ###

import sys


def LI():
    return list(map(int, input().split()))


def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y % x, x)


input()
A = LI()

g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    print("not coprime")
    sys.exit()

sosudayo = [True] * 1100000
sosudayo[0] = False
sosudayo[1] = False
for i in range(2, 1100000):
    if not sosudayo[i]:
        continue
    for j in range(i*i, 1100000, i):
        sosudayo[j] = False

used = [False] * 1100000
sosu = [a for a in A if sosudayo[a]]
for i in sosu:
    used[i] = True
ruto_sosu = [a for a in range(1100) if sosudayo[a]]
not_sosu = [a for a in A if not sosudayo[a]]

for i in not_sosu:
    for j in ruto_sosu:
        if i == 1:
            break
        if i % j != 0:
            continue
        if used[j]:
            print("setwise coprime")
            sys.exit()
        used[j] = True
        while i % j == 0:
            i //= j
    if i > 1:
        if used[i]:
            print("setwise coprime")
            sys.exit()
        used[i] = True

print("pairwise coprime")
n,m=map(int,input().split())
lists=list(map(int,input().split()))
checklist=[]
count=0

for i in range(m):
    b,c=map(int,input().split())
    checklist.append((c,b))
checklist=sorted(checklist,reverse=True)
lists=sorted(lists)
uselist=[0]*n
count=0
for i in checklist:
    for j in range(i[1]):
        uselist[count]=i[0]
        count+=1
        if count==n:
            break
answer=0
for i in range(n):
    if lists[i]<uselist[i]:
        lists[i]=uselist[i]
    else:
        break
print(sum(lists))

### FIXED CODE ###

n,m=map(int,input().split())
lists=list(map(int,input().split()))
checklist=[]
count=0

for i in range(m):
    b,c=map(int,input().split())
    checklist.append((c,b))
checklist=sorted(checklist,reverse=True)
lists=sorted(lists)
uselist=[]
count=0

for i in checklist:
    for _ in range(i[1]):
        uselist.append(i[0])
    count+=i[1]

    if count>=n:
        break
answer=0
n=min(n,len(uselist))
for i in range(n):
    if lists[i]<uselist[i]:
            lists[i]=uselist[i]
    else:
        break
print(sum(lists))
# 1行目の入力を空白で分割された数値として扱う
N, X, Y = map(int, input().split())

# 最短経路のリスト
min = []
ans = []

# 距離の取得
for i in range(0, N -1):
    d = A[i+1] - A[i]
    ans += d
    if d > max:
        max = d

# 一周した最後
dl = K - A[N - 1]
if dl < max:
    ans = ans - max + dl + A[0]

# 出力
for j in range(0, N -1):
    print(ans[j])


### FIXED CODE ###

# 1行目の入力を空白で分割された数値として扱う
K, N = map(int, input().split())
# 2行目の入力を数値のリストとして扱う
A = list(map(int, input().split()))

# 答えの準備
ans = 0
max = 0

# 距離の取得
for i in range(0, N -1):
    d = A[i+1] - A[i]
    ans += d
    if d > max:
        max = d

# 一周した最後
dl = K - A[N - 1]
if dl + A[0] < max:
    ans = ans - max + dl + A[0]

# 出力
print(ans)
a,b=map(int.input().split())
print(a + b//2)

### FIXED CODE ###

a,b=map(int,input().split())
print(a + b//2)
#!/usr/bin/env python3
 
import functools
 
MOD = 1000000007
fact = []
 
def main():
    h, w, a, b = map(int, input().split())
    init_fact(200000, MOD)
    mp = get_list_middle_points(h, w, a, b)
    res = 0
    for y, x in mp:
        res += count(1, 1, x, y) * count(x, y, w, h)
        res %= MOD
    print(res)
 
def count(x1, y1, x2, y2):
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    count = combi(dx + dy, dx, MOD)
    return count
 
def get_list_middle_points(h, w, a, b):
    li = []
    y = h - a
    x = b + 1
    while (y >= 1 and x <= w):
        li.append((y, x))
        y -= 1
        x += 1
    return li
 
def combi(n, k, mod):
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % mod
    return (numera * inv(denomi, mod)) % mod
 
def init_fact(maxn, mod):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % mod)
 
def inv(n, mod):
    return pow(n, mod - 2, mod)
 
def pow(n, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2, mod)
        return (x * x) % mod
    else:
        x = pow(n, p - 1, mod)
        return (x * n) % mod
 
main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    n, k = map(int, input().split())
    dk = list(map(int, input().split()))
    assert len(dk) == k

    us = set(usable(dk))
    print(form(us, n))

def form(us, n):
    for res in range(n, 10 ** 5):
        fla = True
        for c in str(res):
            if int(c) not in us:
                fla = False
                break
        if fla:
            return res
    raise Exception

def usable(dk):
    res = []
    for i in range(10):
        if i not in dk:
            res.append(i)
    return res

main()
x,y = map(int,input().split())
if y>=2*x && y<=4*y:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

x,y = map(int,input().split())
if y>=2*x and y<=4*x and y%2==0:
  print("Yes")
else:
  print("No")
a,b,c=map(int,input().split())
print(max(0,c-(a-b))

### FIXED CODE ###

a,b,c=map(int,input().split())
print(max(0,c-(a-b)))
import itertools
from pprint import pprint
import sys 
sys.setrecursionlimit(100*10+1024)
#基本的に10*100*len(bonus_masterlist)回ループを回せばよい
#len(bonus_masterlist)は最大で2**10=1024

d,g = map(int,input().split())

plist=[]
clist=[]

bonus_masterlist=[]

for _ in range(d):
    p_temp,c_temp = map(int,input().split())
    plist.append(p_temp)
    clist.append(c_temp)


bonus_masterlist = list(itertools.product(range(2), repeat=5))
#bit全探索をやらなくても、itertoolsを使えば一瞬でできちゃう。(タプルのリスト)
#for i in range(2**d):
#    bonus_templist = [0] * d
#    for j in range(d):
#        if i >> j & 1:
#            bonus_templist[d-1-j] = 1
#    bonus_masterlist.append(bonus_templist)

#point_list = [100,200,300, ... ,d*100]
#max_list: plist = [p[0],p[1],p[2], ... ,p[d]]
#bonuspoint_list: clist = [c[0],c[1],c[2], ... ,c[d]]

count_list = [0] * d

mincount = 100 * 10

def dfs(i):
    global mincount
    if sum([count_list[i] * 100*(i+1) for i in range(d)]) + sum([bonus_list[j] * clist[j] for j in range(d)]) >= g:
        if sum(count_list) < mincount:
            mincount = sum(count_list)
    elif plist[i] == count_list[i]:
        bonus_list[i] = 1
        dfs(i-1)
    elif plist[i] > count_list[i]:
        count_list[i] += 1
        dfs(i)
    return

for bonus_tuple in bonus_masterlist:
    bonus_list = list(bonus_tuple)
    count_list = [x * y for (x, y) in zip(bonus_list, plist)]
    dfs(d-1)

print(mincount)

### FIXED CODE ###

import itertools
from pprint import pprint


d,g = map(int,input().split())

plist=[]
clist=[]

bonus_masterlist=[]

for _ in range(d):
    p_temp,c_temp = map(int,input().split())
    plist.append(p_temp)
    clist.append(c_temp)


bonus_masterlist = list(itertools.product(range(2), repeat=d))
#bit全探索をやらなくても、itertoolsを使えば一瞬でできちゃう。(タプルのリスト)
#for i in range(2**d):
#    bonus_templist = [0] * d
#    for j in range(d):
#        if i >> j & 1:
#            bonus_templist[d-1-j] = 1
#    bonus_masterlist.append(bonus_templist)

#point_list = [100,200,300, ... ,d*100]
#max_list: plist = [p[0],p[1],p[2], ... ,p[d]]
#bonuspoint_list: clist = [c[0],c[1],c[2], ... ,c[d]]

count_list = [0] * d

mincount = 100 * 10

"""
def dfs(i):
    global mincount
    if sum([count_list[i] * 100*(i+1) for i in range(d)]) + sum([bonus_list[j] * clist[j] for j in range(d)]) >= g:
        if sum(count_list) < mincount:
            mincount = sum(count_list)
    elif plist[i] == count_list[i]:
        bonus_list[i] = 1
        dfs(i-1)
    elif plist[i] > count_list[i]:
        count_list[i] += 1
        dfs(i)
    return
"""

for bonus_tuple in bonus_masterlist:
    bonus_list = list(bonus_tuple)
    count_list = [x * y for (x, y) in zip(bonus_list, plist)]
    i = d-1
    while True:
        if sum([count_list[i] * 100*(i+1) for i in range(d)]) + sum([bonus_list[j] * clist[j] for j in range(d)]) >= g:
            if sum(count_list) < mincount:
                mincount = sum(count_list)
            break
        elif plist[i] == count_list[i]:
            bonus_list[i] = 1
            i -= 1
            continue
        elif plist[i] > count_list[i]:
            count_list[i] += 1
            continue


print(mincount)
N, A, B = map(int, input().split(" "))


balls = ''
for i in range(N):
    balls += 'b'*A + 'r'*B
balls = balls[0:N]

# print(bakks)
count = 0
for x in balls:
    if x == 'b':
        count += 1
print(count)

### FIXED CODE ###

def main():
    N, A, B = map(int, input().split(" "))
    if (A + B) == 0:
        print(0)
        return
    amari = N % (A+B)
    kaisuu = N // (A+B)
    print(kaisuu*A+min(amari, A))
main()
S = input()

if (S == "ARC):
    print("ABC")
else:
    print("ARC")

### FIXED CODE ###

S = input()

if (S == "ARC"):
    print("ABC")
else:
    print("ARC")
from heapq import *

a,b,c,K = int(input()),int(input()),int(input()),int(input())
A = sorted([int(x) for x in input().split(' ')], reversed=True)
B = sorted([int(x) for x in input().split(' ')], reversed=True)
C = sorted([int(x) for x in input().split(' ')], reversed=True)

res = []
i, j, k = 0, 0, 0
while len(res) < K:
  res.append(A[i]+B[j]+C[k])
  res.append(A[i+1]+B[j]+C[k])
  res.append(A[i]+B[j+1]+C[k])
  res.append(A[i]+B[j]+C[k+1])
  i,j,k = i+1, j+1, k+1
res = sorted(res, reversed=True)[:K]
for i in res:
  print(i)

### FIXED CODE ###

from heapq import *

X, Y, Z, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A = sorted([int(x) for x in A], reverse=True)
B = sorted([int(x) for x in B], reverse=True)
C = sorted([int(x) for x in C], reverse=True)

res = []
memo = []
ans = []
heappush(res, (-A[0]-B[0]-C[0], 0, 0, 0))
while len(ans) < K:
  e, i, j, k = heappop(res)
  ans.append(-e)
  if i+1 < X and [i+1, j, k] not in memo:
    heappush(res, (-A[i+1]-B[j]-C[k], i+1, j, k))
    memo.append([i+1, j, k])
  if j+1 < Y and [i, j+1, k] not in memo:
    heappush(res, (-A[i]-B[j+1]-C[k], i, j+1, k))
    memo.append([i, j+1, k])
  if k+1 < Z and [i, j, k+1] not in memo:
    heappush(res, (-A[i]-B[j]-C[k+1], i, j, k+1))
    memo.append([i, j, k+1])

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

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

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

main()
I=input;n=int(I());print(max(sum(p[bin(i&f).count('1')]for f,p in zip([int(I()[::2],2)for _ in[0]*n],[list(map(int,I().split()))for _ in[0]*n]))for i in range(1,1024)))

### FIXED CODE ###

I=input;n=int(I());f=[int(I()[::2],2)for _ in[0]*n];p=[list(map(int,I().split()))for _ in[0]*n];print(max(sum(q[bin(i&g).count('1')]for g,q in zip(f,p))for i in range(1,1024)))
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))
SIZE = [0] + [1] * N  # 1-indexed


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    if not is_same(x, y):
        X, Y = find(x), find(y)
        SX, SY = SIZE[X], SIZE[Y]
        if SX > SY:
            m = UF[X] = Y
        else:
            m = UF[Y] = X
        SIZE[m] = SX + SY
        SIZE[X + Y - m] = 0


def is_same(x, y):
    return find(x) == find(y)


def scan_uf():
    for i in range(len(UF)):
        find(i)


ans = [N * (N - 1) // 2]
for a, b in AB[::-1]:
    if not is_same(a, b):
        ans += [ans[-1] - SIZE[find(a)] * SIZE[find(b)]]
        unite(a, b)
    else:
        ans += [ans[-1]]
print(*ans[-2::-1], sep='\n')


### FIXED CODE ###

N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))
SIZE = [1] * (N + 1)


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    m = min(find(x), find(y))
    SIZE[m] = SIZE[find(x)] + SIZE[find(y)]
    UF[find(x)] = m
    UF[find(y)] = m


def is_same(x, y):
    return find(x) == find(y)


ans = [N * (N - 1) // 2]
for a, b in AB[::-1]:
    if not is_same(a, b):
        ans += [ans[-1] - SIZE[find(a)] * SIZE[find(b)]]
        unite(a, b)
    else:
        ans += [ans[-1]]
print(*ans[M - 1::-1], sep='\n')