Harryxun/stf_run huggingface dataset:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 累積和、dp、しゃくとり
MOD = 998244353
N, S = lr()
A = lr()
# dp[k][j] kから始めた合計の個数
dp = np.array([[0] * 3000 for _ in range(N)])
dp[:, 0] = 1
answer = 0
cur = [0] * (N)
#print(dp)
for i, a in enumerate(A):
    # iが現在地
    for j in range(i+1):
        prev = dp[j].copy()
        dp[j][a:] += prev[:-a]
        temp = dp[j][S] - cur[j]
        answer += temp * (N-i)
        z = int(dp[j][S])
        cur[j] = z
        #print(i, j, answer, temp, dp[j][S])
    answer %= MOD

print(answer % MOD)


### FIXED CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = [0] * (S+1)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    for i in range(S-a+1):
        dp[i+a] += prev[i]
    answer += dp[-1] # その位置Rとした時

print(answer % MOD)
# 26
a, b = map(int, raw_input().split())
if a%2 == 0 or b%2 == 0:
    print('no')
else:
    print('yes')

### FIXED CODE ###

a, b = map(int, input().split())
if a % 2 == 0 or b % 2 == 0:
    print('No')
else:
    print('Yes')
def solve():
    N, M = map(int, input().split())
    A = []
    if M != 0:
        A = [int(input()) for _ in range(M)]
    A.sort(reverse=True)
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  # 0段目に行くパターンは1とする
    tag = -1
    if len(A) != 0:
        tag = A.pop()
    # 1段目のパターンを設定
    if tag == 1:
        dp[1] = 0
        tag = A.pop()
    else:
        dp[1] = 1
    for i in range(2, N + 1):
        if i == tag:
            if len(A) == 0:
                tag = -1
            else:
                tag = A.pop()
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mm
    print(dp[N])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N, M = map(int, input().split())
    A = []
    if M != 0:
        A = [int(input()) for _ in range(M)]
    A.sort(reverse=True)
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  # 0段目に行くパターンは1とする
    tag = -1
    if len(A) != 0:
        tag = A.pop()
    # 1段目のパターンを設定
    if tag == 1:
        dp[1] = 0
        if len(A) == 0:
            tag = -1
        else:
            tag = A.pop()
    else:
        dp[1] = 1
    for i in range(2, N + 1):
        if i == tag:
            if len(A) == 0:
                tag = -1
            else:
                tag = A.pop()
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mm
    print(dp[N])


if __name__ == '__main__':
    solve()
N = int(input())
L = map(int, input().split())
ans = 0
for c in range(N):
    for cc in range(c + 1, N):
        for ccc in range(cc + 1, N):
            ab = L[c]
            bb = L[cc]
            cb = L[ccc]
            if ab < (bb + cb) and bb < (ab + cb) and cb < (ab + bb):
                ans += 1
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for a in range(N):
    for b in range(a):
        ab = L[a] + L[b]
        r = bisect.bisect_left(L, ab)
        l = a + 1
        ans += max(r - l, 0)
print(ans)
n=int(input())
a=list(input().split(' '))
total=0
S_i=0
for i in range(n-1):
    S_i+=a[n-1-i]
    S_i=S_i%(7+10**9)
    total+=S_i*a[n-2-i]
    total=total%(7+10**9)
print(total)

### FIXED CODE ###

n=int(input())
a=list(input().split(' '))
total=0
S_i=0
for i in range(n-1):
    S_i+=int(a[n-1-i])
    S_i=S_i%(7+10**9)
    total+=S_i*int(a[n-2-i])
    total=total%(7+10**9)
print(total)
K, S = list(map(int, input().split()))

ans = 0
for x in range(K+1):
    xyz = x
    if S > xyz:
        continue
    for y in range(K+1):
        xyz += y
        if S > xyz:
            continue:
        for z in range(K+1):
            xyz += z
            if xyz == S:
                ans += 1

print(ans)

### FIXED CODE ###

K, S = list(map(int, input().split()))

ans = 0
for x in range(K+1):
    n = 0
    if S < x:
        break
    for y in range(K+1):
        n = S - (x + y)
        if 0 <= n <= K:
            ans += 1

print(ans)
n = input()
m = list(n)
print(m)

if int(n) % sum(m) == 0:
    print('Yes')
else:
    print('No')
    

### FIXED CODE ###

n = input()
m = list(n)

m = list(map(int,m))
if int(n) % sum(m) == 0:
    print('Yes')
else:
    print('No')
n=int(input())
a=map(int,input().split())
i=1
for k in a:
  if k==i: i+=1
1-=1
print(N-i if i>0 else -1)

### FIXED CODE ###

N=int(input())
A=map(int,input().split())
i=1
for a in A:
  if a==i: i+=1
i-=1
print(N-i if i>0 else -1)
import fraction

n, x = [int(_) for _ in input().split()]
x_list = [int(_) - x for _ in input().split()]
print(x_list)

x_sorted = sorted(x_list)

x_gaps = [x_sorted[i+1] - x_sorted[i] for i in range(0, n-1)]

result = x_sorted[0]
for i in range(0, n-2):
    if i == 0:
        result = fraction.gcd(x_gaps[0], x_gaps[1])
    else:
        result = fraction.gcd(result, x_gaps[i+1])

print(result)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


n, x = [int(_) for _ in input().split()]
x_list = [int(_) - x for _ in input().split()]

x_sorted = sorted(x_list)

x_gaps = [x_sorted[i+1] - x_sorted[i] for i in range(0, n-1)]

if len(x_gaps) == 0:
    print(abs(x_sorted[0]))
elif len(x_gaps) == 1:
    print(gcd(abs(x_list[0]), abs(x_list[1])))
else:
    result = x_sorted[0]
    for i in range(0, n-2):
        if i == 0:
            result = gcd(x_gaps[0], x_gaps[1])
        else:
            result = gcd(result, x_gaps[i+1])
    print(result)
r=input()
g=input()
print(2*g-r)

### FIXED CODE ###

r=int(input())
g=int(input())
print(2*g-r)
a = string(input())
n = int(0)
if a[0]=='1':
  n = n+1
if a[1]=='1':
  n = n+1
if a[2]=='1':
  n = n+1
print(n)


### FIXED CODE ###

a = str(input())
n = int(0)
if a[0]=='1':
  n = n+1
if a[1]=='1':
  n = n+1
if a[2]=='1':
  n = n+1
print(n)
from math import factorial

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

for i in range(1, K+1):
  print(int(factorial(N-K+1)*factorial(K-1)/factorial(N-K+1-i)/factorial(i)/factorial(i-1)/factorial(K-i) % (10**9+7)))

### FIXED CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

for i in range(1, r+1):
  if n-r+1 < i:
    print(0)
  else:
    print(cmb(n-r+1,i)*cmb(r-1,i-1)%(10**9+7))
[print(s) for s in map(lambda x:x[0]+x[1]==x[2]　and 'YES' or 'NO', [sorted(int(x)**2 for x in input().split(' ') for i in range(int(input()))])]

### FIXED CODE ###

print "\n".join(s for s in map(lambda x:x[0]+x[1]==x[2] and 'YES' or 'NO', [sorted(int(x)**2 for x in raw_input().split(' ')) for i in range(int(raw_input()))]))
n,x=map(int,input().split())
m=2*n-1
if x==1 or x==m:
    print("No")
    exit()
ll=list(range(1,2*n))
if x!=2:
    l=[x-1,x,x+1,x-2]
    ll.remove(x-1)
    ll.remove(x)
    ll.remove(x+1)
    ll.remove(x-2)
else:
    l=[x+1,x,x-1,x+2]
    ll.remove(x-1)
    ll.remove(x)
    ll.remove(x+1)
    ll.remove(x+2)

ans=[]
for i in range(len(ll)):
    if i==n-2:
        ans+=l
    ans.append(ll[i])

print("Yes")
for i in ans:
    print(i)



### FIXED CODE ###

n,x=map(int,input().split())
m=2*n-1
if x==1 or x==m:
    print("No")
    exit()
if n==2:
    print("Yes")
    for i in [1,2,3]:
        print(i)
    exit()
ll=list(range(1,2*n))
if x!=2:
    l=[x-1,x,x+1,x-2]
    ll.remove(x-1)
    ll.remove(x)
    ll.remove(x+1)
    ll.remove(x-2)
else:
    l=[x+1,x,x-1,x+2]
    ll.remove(x-1)
    ll.remove(x)
    ll.remove(x+1)
    ll.remove(x+2)

ans=[]
for i in range(len(ll)):
    if i==n-2:
        ans+=l
    ans.append(ll[i])
if len(ll)==n-2:
    ans+=l
print("Yes")
for i in ans:
    print(i)
N,M = map(int,input().split())
A = [[] for i in range(N+1)]
B = []
d = {}
for i in range(M):
    p,y = map(int,input().split())
    B.append((p,y))
    A[p].append(y)
for i in range(N+1):
    A[i].sorted
    n = len(A[i])
    for j in range(n):
        d[A[i][j]] = j+1
for i in range(M):
    p,y = B[i]
    q = d[y]
    m = 6 - len(str(p))
    n = 6 - len(str(q))
    ans = "0"*m + str(p) + "0"*m + str(q)
    print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = [[] for i in range(N+1)]
B = []
d = {}
for i in range(M):
    p,y = map(int,input().split())
    B.append((p,y))
    A[p].append(y)
for i in range(N+1):
    A[i].sort()
    n = len(A[i])
    for j in range(n):
        d[A[i][j]] = j+1
for i in range(M):
    p,y = B[i]
    q = d[y]
    m = 6 - len(str(p))
    n = 6 - len(str(q))
    ans = "0"*m + str(p) + "0"*n + str(q)
    print(ans)
h, w=map(int, input().split())
a=[]
need_visited=[[h+w for i in range(w)] for j in range(h)]
stack=[]
for i in range(h):
    a.append(list(input()))

for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            stack.append([i, j])
            need_visited[i][j]=0



dx=[1, -1, 0, 0]
dy=[0, 0, 1, -1]


while len(stack)!=0:
    now_point=stack.pop(0)
    now_y=now_point[0]
    now_x=now_point[1]
    for i in range(4):
        if 0<=now_x+dx[i]<=w-1 and 0<=now_y+dy[i]<=h-1:
            if a[now_x+dx[i]][now_y+dy[i]]==".":
                if need_visited[now_x+dx[i]][now_y+dy[i]]>need_visited[now_x][now_y]+1:
                    need_visited[now_x+dx[i]][now_y+dy[i]]=need_visited[now_x][now_y]+1
                    stack.append([now_x+dx[i], now_y+dy[i]])
max_list=[]
for i in range(h):
    max_list.append(max(need_visited[i]))
print(max(max_list))


### FIXED CODE ###

from collections import deque

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh < H and 0 <= nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d

print(ans)
from collections import deque
import sys
sys.setrecursionlimit(4000)
N, M = map(int, input().split())
graph = [[] for j in range(M)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node
if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
graph = [[] for j in range(N)]
q = deque([])
depth_array = [-1 for i in range(N)]

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

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node

if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)
n = int(input())
s = '.'+input()
ans = []

def div(i, s):
  l = s[:i.start()+1]
  r = s[i.end()-1:]
  lb = l.count('#')
  rw = r.count('.')
  return l, lb, r, rw
  
for i in re.finditer(r'#\.', s):
  l, lb, r, rw = div(i, s)
  print(l, lb, r, rw)
  ans.append(lb+rw)
print()
for i in re.finditer(r'\.#', s):
  l, lb, r, rw = div(i, s)
  print(l, lb, r, rw)
  ans.append(lb+rw)
print('\n',ans)
if len(ans) > 0:
  print(min(ans))
else:
  print(0)

### FIXED CODE ###

n = int(input())
s = '.'+input()
lb, rw = 0, s.count('.')-1
ans = lb+rw
for i in range(1,n+1):
  if s[i] == '#':
    lb += 1
  elif s[i] == '.':
    rw -= 1
  if lb+rw < ans:
    ans = lb+rw
print(ans)
x=int(input())

x-=1
for i in range(x+1):
    if i**5==x:
        a=i
        break

print(a,-1)

### FIXED CODE ###

x=int(input())

for i in range(-1*(10**3),10**3):
    for j in range(-1*(10**3),10**3):
        if i**5-j**5==x:
            print(i,j)
            exit()
A = input()
B = input()
C = input()
 
count5 = 0
count7 = 0
 
if A == 5:
    count5 = count5 + 1
if A == 7:
    count7 = count7 + 1
if B == 5:
    count5 = count5 + 1
if B == 7:
    count7 = count7 + 1
if C == 5:
    count5 = count5 + 1
if C == 7:
    count7 = count7 + 1
    
if count5 == 2 and count7 == 1:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

s = input().split()

count5 = 0
count7 = 0
 
if s[0] == "5":
    count5 = count5 + 1
if s[0] == "7":
    count7 = count7 + 1
if s[1] == "5":
    count5 = count5 + 1
if s[1] == "7":
    count7 = count7 + 1
if s[2] == "5":
    count5 = count5 + 1
if s[2] == "7":
    count7 = count7 + 1
    
if count5 == 2 and count7 == 1:
    print("YES")
else:
    print("NO")
#N = int(input())
A = input().split()
#B = input().split()
for i in range(N+1):
    A[i] = int(A[i])
#for i in range(N):
#    B[i] = int(B[i])

ue = A[0]*(A[1]-A[2])
shita = A[0]*A[2]
migi = A[1]*(A[0]-A[3])
hidari = A[1]*A[3]
chinpo = True

if ue > shita:
    if migi > hidari:
        if migi == ue:
            print(str(ue) + " " + "1")
        else:
            print(str(ue) + " " + "0")
    else:
        if migi == hidari:
            print(str(migi) + " " + "1")
            chinpo = False 
        if hidari == ue & chinpo:
            print(str(ue) + " " + "1")
        else:
            print(str(ue) + " " + "0")
else:
    if ue == shita:
        print(str(ue) + " " + "1")
        chinpo = False
    if migi > hidari & chinpo:
        if migi == ue:
            print(str(ue) + " " + "1")
        else:
            print(str(ue) + " " + "0")
    else:
        if migi == hidari:
            print(str(migi) + " " + "1")
            chinpo = False
        if hidari == ue & chinpo:
            print(str(ue) + " " + "1")
        else:
            print(str(ue) + " " + "0")


### FIXED CODE ###


L = list(map(int, input().split()))
if L[2] == L[0]/2 and L[3] == L[1]/2:
    print(L[0]*L[1]/2,1)
else:
    print(L[0]*L[1]/2, 0)
a=input()
t=100
sum=0
while(t<a):
	t=t*101/100
    sum=sum+1
print(sum)

### FIXED CODE ###

import math
a=int(input())
t=100
sum=0
while(t<a):
	t=math.floor(t*101/100)
	sum=sum+1
print(sum)
nk = input().split()
n , k = int(nk[0]), int(nk[1])
a = [int(i) for i in input().split()]

t = 1
tl = [1]
ts = {1}

flg = False
for i in range(len(a)):
    # flg = t > a[t-1]
    t  = a[t-1]
    # stl = sorted(tl)
    if t in ts:
        break
    else:
        tl.append(t)
        ts.add(t)

tl2 = tl[tl.index(t):len(tl)]
         
# print(tl)
# print(tl2)

ans = 0

if k <= len(tl):
    ans = tl[k]
else:
    k = k - len(tl)
    j = k % len(tl2)
    ans = tl2[j]

print(ans)

### FIXED CODE ###

nk = input().split()
n , k = int(nk[0]), int(nk[1])
a = [int(i) for i in input().split()]

t = 1
tl = [1]
ts = {1}


for i in range(len(a)):
    
    t = a[t-1]
    if t in ts:
        break
    else:
        tl.append(t)
        ts.add(t)

tl2 = tl[tl.index(t):len(tl)]
         
# print(tl)
# print(tl2)

ans = 0

if k < len(tl):
    ans = tl[k]
else:
    k = k - len(tl)
    j = k % len(tl2)
    ans = tl2[j]

print(ans)
a, b, c, d, e = [int(input()) for i in range(5)]
list = [a, b, c, d, e]
nlist = [a%10, b%10, c%10, d%10, e%10]
nlist.remove('0')

#mod10で並べた数字のうち最小のものを削除
nlist.sort() 
nlist.remove(0)
mlist = map(10 - nlist)
Sum = sum(list) + sum(mlist)
print (Sum)

### FIXED CODE ###

l = list(int(input()) for i in range(5))
nlist = []
Sum = 0

for i in range(5):
    if l[i]%10 == 0:
        nlist.append(0)
    else:
        nlist.append(10 - (l[i]%10))
        
if nlist[0] == nlist[1] == nlist[2] == nlist[3] == nlist[4] == 0:
    print(l[0]+l[1]+l[2]+l[3]+l[4])
else:
    #リストlにリストnlistをそれぞれ加える
    for i in range(5):
        Sum += l[i] + nlist[i]
    print(Sum - max(nlist))
a,b,c = map(int,input().split('/'))
print(a*b/2)

### FIXED CODE ###

a,b,c = map(int,input().split())
print(a*b//2)
for i in range(1,10):
    for j in range(1, 10):
        print i + "x" + j "=" + i*j

### FIXED CODE ###

for i in range(1, 10):
     for j in range(1,10):
         print str(i) + "x" + str(j) + "=" + str(i*j)
import math

A,B,C,D = map(int, input().split())

E = (C*D)//math.gcd(C,D)

B_count = B-((B//C)+(B//D)-(B//E))
A_count = (A-1)-(((A-1)//C)+((A-1)//D)-((A-1)//E))

print(B_count-A_count)

### FIXED CODE ###

import fractions

A,B,C,D = map(int, input().split())

E = (C*D)//fractions.gcd(C,D)

B_count = B-((B//C)+(B//D)-(B//E))
A_count = (A-1)-(((A-1)//C)+((A-1)//D)-((A-1)//E))

print(B_count-A_count)
deta = input().split()
n = deta[0]
r = deta[1]
if n>=10:
    print(r)
else:
    rate = 100*(10-int(n))
    print(rate)

### FIXED CODE ###

deta = input().split()
n = deta[0]
r = deta[1]
if int(n)>=10:
    print(r)
else:
    rate = 100*(10-int(n))+int(r)
    print(rate)
list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 
        2, 2, 5, 4, 1, 4, 1, 51]

index = input()
print(list[index])

### FIXED CODE ###

list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 
        2, 2, 5, 4, 1, 4, 1, 51]

index = input()
index = int(index)
print(list[index-1])
import sys
sys.setrecursionlimit(100000)
def search(i, visited, ns) :
    #print(":", i+1)
    visited[i] = True
    for next, weight in ns[i]:
        if visited[next] == False:
            search(next, visited, ns)


def dfs(ns):
    visited = [False] * len(ns)
    ans = 0
    for i in range(len(ns)):
        if not visited[i]:
            #print(i+1)
            ans += 1
            search(i, visited, ns)
    return ans

def main():
    n,m = map(int,input().split())
    ns = [[] for _ in range(n)]
    for _ in range(m):
        (st,end,weight) = map(int,input().split())
        ns[st-1].append((end - 1,weight))
        ns[end-1].append((st-1,weight))
    ans = dfs(ns)
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(150000)
def search(i, visited, ns) :
    #print(":", i+1)
    visited[i] = True
    for next, weight in ns[i]:
        if visited[next] == False:
            search(next, visited, ns)


def dfs(ns):
    visited = [False] * len(ns)
    ans = 0
    for i in range(len(ns)):
        if not visited[i]:
            #print(i+1)
            ans += 1
            search(i, visited, ns)
    return ans

def main():
    n,m = map(int,input().split())
    ns = [[] for _ in range(n)]
    for _ in range(m):
        (st,end,weight) = map(int,input().split())
        ns[st-1].append((end - 1,weight))
        ns[end-1].append((st-1,weight))
    ans = dfs(ns)
    print(ans)
if __name__ == '__main__':
    main()
N = int(input())

print(sum(list(range(1, N))))

### FIXED CODE ###

N = int(input())

print((N-1)*N//2)
from heapq import heappush, heappop

def solve():
    N, M = map(int , input().split())
    arbeit_A_B = list(list(map(int , input().split())) for _ in range(N))
    arbeit_A_B = sorted(arbeit_A_B, key=lambda x: (x[0], -x[1]))
    # print(arbeit_A_B)
    day = 1
    result = 0
    index_arbeit = 0
    heap_q = []
    while day <= M:
        while index_arbeit < N:
            A,B = arbeit_A_B[index_arbeit]
            if A <= day:
                heappush(heap_q, (-1)*B)
            else: break
            index_arbeit += 1
            
        result -= heappop(heap_q)
        day += 1
            
    print(result)
    
solve()

### FIXED CODE ###

from heapq import heappush, heappop

def solve():
    N, M = map(int , input().split())
    arbeit_A_B = list(list(map(int , input().split())) for _ in range(N))
    arbeit_A_B = sorted(arbeit_A_B, key=lambda x: (x[0], -x[1]))
    # print(arbeit_A_B)
    day = 1
    result = 0
    index_arbeit = 0
    heap_q = []
    while day <= M:
        while index_arbeit < N:
            A,B = arbeit_A_B[index_arbeit]
            if A <= day:
                heappush(heap_q, (-1)*B)
            else: break
            index_arbeit += 1
            
        if heap_q:
            result -= heappop(heap_q)
        day += 1
            
    print(result)
    
solve()
N = int(input())

lastnum = N[-1]

if lastnum in [0,1,6,8]
print("pon")

elif lastnum in [3]
print("bon")

else:
print("hon")


### FIXED CODE ###

def solve(n):
    p = n % 10
    if p in [2,4,5,7,9]:
        return "hon"
    elif p in [0,1,6,8]:
        return "pon"
    else:
        return "bon"

n = int(input())
print(solve(n))
def dfs(G,v,p,color):
    cnt=1
    for nv in G[v]:
        if(nv==p):
            continue
        if cnt in liset[v]:
            while(cnt in liset[v]):
                cnt+=1
        liset[v].add(cnt)
        liset[nv].add(cnt)
        dfs(G,nv,v,cnt)
N=int(input())
G=[[] for i in range(N)]
e=[]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    e.append([a,b])
l=0
for i in range(N):
    l=max(l,len(G[i]))
liset=[set() for i in range(N)]
dfs(G,0,-1,0)
print(l)
for i in range(N-1):
    print(list(liset[e[i][0]]&liset[e[i][1]])[-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
def dfs(G,v,p,color):
    cnt=1
    for nv in G[v]:
        if(nv==p):
            continue
        if cnt in liset[v]:
            while(cnt in liset[v]):
                cnt+=1
        liset[v].add(cnt)
        liset[nv].add(cnt)
        dic[str(v)+'t'+str(nv)]=cnt
        dfs(G,nv,v,cnt)
N=int(input())
G=[[] for i in range(N)]
e=[]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
    e.append([a,b])
l=0
for i in range(N):
    l=max(l,len(G[i]))
liset=[set() for i in range(N)]
dic={}
dfs(G,0,-1,0)
print(l)
for i in range(N-1):
    if str(e[i][0])+'t'+str(e[i][1]) in dic:
        print(dic[str(e[i][0])+'t'+str(e[i][1])])
    else:
        print(dic[str(e[i][1])+'t'+str(e[i][0])])