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

def resolve():
    '''
    code here
    '''
    import sys
    from functools import lru_cache
    sys.setrecursionlimit(10**3)
    K = int(input())

    @lru_cache(maxsize=10**3)
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a%b)


    def gcd3(a, b, c):
        temp = gcd(a,b)
        return gcd(temp, c)
    
    res = 0
    for k in range(1,K+1):
        for j in range(1,K+1):
            for i in range(1, K+1):
                res += gcd3(k, j, i)

    print(res)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''

    K = int(input())

    import math
    
    temp_list = []
    for k in range(1,K+1):
        for j in range(1,K+1):
            temp_list.append(math.gcd(k,j))

    res = 0
    for item in temp_list:
        for i in range(1,K+1):
            res += math.gcd(item, i)

    print(res)


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

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

mem_left_len = [len([x for x in s[:i] if x == 'W']) for i in range(n)]
mem_right_len = [len([x for x in s[i+1:] if x == 'E']) for i in range(n)]
  
numpeople = 3 * 10 ** 5 + 1
for leader in range(n):
  numpeople = min(numpeople, mem_left_len[leader] + mem_right_len[leader])

print(numpeople)

### FIXED CODE ###

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

turn_east = [0 for x in range(n)]
turn_west = [0 for x in range(n)]
total = [0 for x in range(n)]

for i in range(n):
  if i > 0:
    if s[i-1] == 'W':
      turn_east[i] = turn_east[i-1]+1
    else:
      turn_east[i] = turn_east[i-1]

    if s[n-i] == 'E':
      turn_west[n-1-i] = turn_west[n-i]+1
    else:
      turn_west[n-1-i] = turn_west[n-i]

for j in range(n):
  total[j] = turn_east[j] + turn_west[j]

print(min(total))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


class Solver(object):
    def __init__(self):
        pass

    def solve(self, n, arr):
        sum = 0
        bitcount = [0]*100
        for num in arr:
            b = reversed(bin(num)[2:])
            for i, s in enumerate(b):
                if i != "0":
                    bitcount[i] += int(s)
        for i, b in enumerate(bitcount):
            sum += b * (n-b) * 2**i
        return sum % (10**9 + 7)


def main():
    N = int(input())
    A_l = [int(i) for i in input().split()]
    solver = Solver()
    print(solver.solve(N, A_l))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def solve(n, arr):
    sum = 0
    bitcount = [0]*100
    for num in arr:
        b = reversed(bin(num)[2:])
        for i, s in enumerate(b):
            if i != "0":
                bitcount[i] += int(s)
    for i, b in enumerate(bitcount):
        sum += b * (n-b) * 2**i
    return sum % (10**9 + 7)


def main():
    N = int(input())
    A_l = [int(i) for i in input().split()]
    print(solve(N, A_l))


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

N = int(input())
l = list(map(int, input().split()))
l_2 = []
gusu_kisu = N % 2
end_F = 0
for i in range(N):
    if gusu_kisu == 1:
        An = l[i]
        if An % 2 == 1:
            end_F = 1
            break
        elif An == 0 and l_2.count(0) == 1:
            end_F = 1
            break
        elif l_2.count(An) == 2:
            end_F = 1
            break
        else:
            l_2.append(An)
    else:
        An = l[i]
        if An % 2 == 0:
            end_F = 1
            break
        elif l_2.count(An) == 2:
            end_F = 1
            break
        else:
            l_2.append(An)
#     print(An)
# print(end_F)
if end_F == 0:
    print((2 ** (N // 2)) % ((10 ** 9) + 7))
else:
    print(0)

### FIXED CODE ###

from collections import Counter

ans_0 = False
N = int(input())
l = list(map(int, input().split()))
l_Counter = Counter(l)
if N % 2 == 1:
    if l_Counter[0] != 1:
        ans_0 = True
    else:
        l_Counter[0] = 2
        for i in l_Counter.items():
            # print(i)
            if i[1] != 2 or i[0] % 2 == 1:
                ans_0 = True
                break
else:
    for i in l_Counter.items():
        # print(i)
        if i[1] != 2 or i[0] == 0 or i[0] % 2 == 0:
            ans_0 = True
            break
#     print(An)
# print(end_0)
if ans_0:
    print(0)
else:
    print((2 ** (N // 2)) % 1000000007)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
result = 1
checker =False
for j in a:
  if j > 1000000000000000000:
    result = -1
    checker =True
if 0 in a:
  result = 0
  checker=True
while checker==False:
  import functools
  import operator
  result = functools.reduce(operator.mul, a)
  checker = True
    

if result <= 1000000000000000000:
  print(result)
else:
  print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
result = 1
for i in range(len(a)):
  result = result*a[i]
  if result == 0:
    break
  elif result > 1000000000000000000:
    break

if result <= 1000000000000000000:
  print(result)
else:
  print(-1)
### BUGGY CODE ###

n=int(input())
x=3500
a=1
for k in range(1,x):
    for j in range(1,x):
        a=(4*j*k - n*k - n*j)
        if a<=0: continue
        i = n*j*k / a
        if i==int(i) :
            print(int(i),j,k)
            break
    else:
        continue
    break

### FIXED CODE ###

n=int(input())
for k in range(1,3501):
    for j in range(1,k+2):
        a=(4*j*k - n*k- n*j)
        if a<=0 : continue
        i = n*j*k / a
        i2= n*j*k // a
        if i==i2 :
            print(i2,j,k)
            break
    else:
        continue
    break
### BUGGY CODE ###

import math
n, k = map(int, input().split())
# a = [int(x) for x in input().split()]
# f = [int(x) for x in input().split()]
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)
lx = 0
rx = a[-1] * f[0]
for i in range(1000):
    if lx == rx:
        break
    cx = (lx + rx) // 2
    kk = 0
    for j in range(n):
        ta = a[j]
        y = (ta*f[j] - cx + f[j] -1) // f[j]
        kk += max(0, y)
    if kk <= k:
        rx = cx
    else:
        lx = cx
print(rx)

### FIXED CODE ###

n, k = map(int, input().split())
# a = [int(x) for x in input().split()]
# f = [int(x) for x in input().split()]
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)
lx = -1
rx = a[-1] * f[0]
while rx-lx>1 :
    cx = (lx + rx) // 2
    kk = 0
    for j in range(n):
        kk += max(0, a[j] - cx//f[j])
    if kk <= k:
        rx = cx
    else:
        lx = cx
print(rx)
### BUGGY CODE ###

def main():
  s=input()
  q=int(input())
  rev=0
  for _ in range(q):
    query=input().split()
    if(query[0]=='1'):
      rev=1-rev
    elif((int(query[1])+rev)%2==1):
      s=query[2]+s
    else:
      s=s+query[2]
  if rev==1:
    return s[::-1]
  return s
print(main())


### FIXED CODE ###

import array
def main():
  n=2*10**5
  s=input()
  q=int(input())
  rev=0
  l=n-1
  r=n+len(s)
  s=array.array('b',[0]*n+[ord(c) for c in s]+[0]*n)
  for _ in range(q):
    query=input().split()
    if(query[0]=='1'):
      rev=1-rev
    elif((int(query[1])+rev)%2==1):
      s[l]=ord(query[2])
      l-=1
    else:
      s[r]=ord(query[2])
      r+=1
  s=[chr(c) for c in s if c!=0]
  if rev==1:
    return ''.join(s[::-1])
  return ''.join(s)
print(main())
### BUGGY CODE ###

H, N = map(int, input().split())
mahou = []
a_max = 0
for _ in range(N):
    a, b = map(int, input().split())
    mahou.append([a, b])
    a_max = max(a_max, a)

dp = [[10 ** 9 for _ in range(H + a_max)] for _ in range(N + 1)]

for i in range(N + 1):
    dp[i][0] = 0

for i in range(1, N + 1):
    for j in range(H + a_max):
        if j >= mahou[i - 1][0]:
            dp[i][j] = min(dp[i][j - mahou[i - 1][0]] + mahou[i - 1][1], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(min(dp[N][H:]))


### FIXED CODE ###

H, N = map(int, input().split())
mahou = []
a_max = 0
for _ in range(N):
    a, b = map(int, input().split())
    mahou.append([a, b])
    a_max = max(a_max, a)

dp = [[10 ** 9 for _ in range(H + a_max)] for _ in range(N + 1)]

for i in range(N + 1):
    dp[i][0] = 0

for i in range(1, N + 1):
    for j in range(H + a_max):
        if j >= mahou[i - 1][0]:
            dp[i][j] = min(dp[i][j - mahou[i - 1][0]] + mahou[i - 1][1], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(min(dp[N][H:]))
### BUGGY CODE ###

N = int(input())
 
mes_dict = {}
for i in range(N):
  m = input()
  try:
    mes_dict[m] += 1
  except:
    mes_dict[m] = 1

answer = sorted([k for k, v in mes_dict.items() if v == max(mes_dict.values())])
for ans in answer:
  print(ans)

### FIXED CODE ###

N = int(input())
 
mes_dict = {}
for i in range(N):
  m = input()
  try:
    mes_dict[m] += 1
  except:
    mes_dict[m] = 1

ma =max(mes_dict.values())
answer = sorted([k for k, v in mes_dict.items() if v == ma])
for ans in answer:
  print(ans)
### BUGGY CODE ###

"""
3*10**5
O(NlogN)まで
"""

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

count = []
for i in range(N):
    count.append(S[0:i].count("W") + S[i+1:].count("E"))

print(min(count))

### FIXED CODE ###

"""
3*10**5
単純に両側の差を全探索だと間に合わないO(N*2)

情報を先に保存しておきそれを使う
"""

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

E_list = [0] * N 
W_list = [0] * N

n = 0
for i in range(1,N):
    if S[i-1] == "W":
        n += 1
        W_list[i] = n
    else:
        W_list[i] = n

n = 0
for i in reversed(range(N-1)):
    if S[i+1] == "E":
        n += 1
        E_list[i] = n
    else:
        E_list[i] = n

print(min([e+w for e,w in zip(E_list, W_list)]))
### BUGGY CODE ###

import math


class DFS:
    def __init__(self, average, numbers):
        self.average = average
        self.numbers = sorted([n for n in numbers if n != average], reverse=True)
        self.length = len(self.numbers)
        self.sum = average * self.length
        self.pre_patterns = int(math.pow(2, numbers.count(self.average))) - 1

    def _dfs(self, index, sum, picked):
        patterns = 0
        sum_if_added = sum + self.numbers[index]
        sum_if_not_added = sum
        picked_if_added = picked + 1
        picked_if_not_added = picked
        if index == self.length - 1:
            if self.average == sum_if_added / picked_if_added:
                patterns += 1
            if picked_if_not_added != 0 and self.average == sum_if_not_added / picked_if_not_added:
                patterns += 1
            return patterns
        else:
            if sum_if_added <= self.sum:
                patterns += self._dfs(index=index + 1, sum=sum_if_added, picked=picked_if_added)
            patterns += self._dfs(index=index + 1, sum=sum_if_not_added, picked=picked_if_not_added)
            return patterns

    def calc_patterns(self):
        if self.length > 0:
            dfs = self._dfs(index=0, sum=0, picked=0)
        else:
            dfs = 0
        patterns_by_dfs = (self.pre_patterns + 1) * dfs
        return self.pre_patterns + patterns_by_dfs


def main(n, a, x):
    dfs = DFS(average=a, numbers=x)
    result = dfs.calc_patterns()
    return result


if __name__ == '__main__':
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    print(main(N, A, X))

### FIXED CODE ###

import numpy as np


def main(n, a, x):
    SUM_MAX = max(a, max(x)) * n + 1
    dp = np.zeros(shape=(n + 1, n + 1, SUM_MAX), dtype=int)

    dp[0][0][0] = 1
    for j in range(1, n + 1):
        for k in range(j + 1):
            dp[j][k][0:x[j - 1]] = dp[j - 1][k][0:x[j - 1]]
            if k >= 1:
                dp[j][k][x[j - 1]:] = dp[j - 1][k][x[j - 1]:] + dp[j - 1][k - 1][:SUM_MAX - x[j - 1]]

    patterns = 0
    for k in range(1, n + 1):
        ka = k * a
        patterns += dp[n][k][ka]
    return patterns


if __name__ == '__main__':
    N, A = map(int, input().split())
    X = list(map(int, input().split()))
    print(main(N, A, X))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)] 
for i in range(N):
    B = A[i]
    A[i] = 0
    print(max(A))
    A[i] = B


### FIXED CODE ###

import sys
N = int(input())
A = [int(input()) for _ in range(N)] 
A_max1 = max(A)
if A.count(A_max1) >= 2:
    for i in range(N):
        print(A_max1)
    sys.exit()    
elif  A.count(A_max1) == 1:
    A[A.index(A_max1)] = 0
    A_max2 = max(A)
    A[A.index(0)] = A_max1
    for i in range(N):
        if A[i] == A_max1:
            print(A_max2)
        else:
            print(A_max1)
### BUGGY CODE ###

n=int(input())
ans =0
L =[0]*n

for i in range(1,n+1):
    for j in range(1,int(n**0.5//6)+2):
        for k in range(j,int(n**0.5//6)+3):
            for l in range(k,int(n**0.5//6)+4):
                if j**2 + k **2 + l**2 + j*k + k*l + l*j == i:
                    if j == k == l:
                        L[i-1] += 1
                        break
                    if j != k and j!=l and k!=l:
                        L[i-1] += 6
                        break
                    else:
                        L[i-1] += 3
for m in range(n):
    print(L[m])

### FIXED CODE ###

N=int(input())
r=[0]*10000
for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
            v = i*i + j*j + k*k + i*j + i*k + k*j
            if v <= 10000:
                r[v-1] += 1
for i in range(N):
    print(r[i])
### BUGGY CODE ###

import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1
dp = [[0] * N for __ in range(N)]

def ans(left, right):
    if dp[left][right] > 0:
        return dp[left][right]
    elif left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        return A[left][right]
    else:
        x = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        dp[left][right] = x
        return x

for q in range(Q):
    pi, qi = queries[q]
    print(ans(pi - 1, qi - 1))


### FIXED CODE ###

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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N-1):
    for j in range(i+1,N):
        ans+=A[i]^A[j]
print(ans%(10**9+7))

### FIXED CODE ###

#ABC147_D
#N個の数字から2個選ぶの全組み合わせのXORを足してmodする問題

import numpy as np

N = int(input())
arr = np.array([int(i) for i in input().split()])
ans = 0
mod=10**9+7


for i  in range(60):
    c1=np.count_nonzero(arr&1)#arrの最下位bitの論理和。arrの最下位bitが1の数をカウント
    c0=N-c1#arrの最下位bitが0の数
    ans+=2**i*c1*c0#c1個の中から1つ選ぶ組み合わせとc0個の中から1つ選ぶ組み合わせの掛け算が、該当bitがXOR＝１となる組み合わせの数
    arr>>=1#最下位bitを変更
print(ans%mod)
### BUGGY CODE ###

class Process(object):
    def __init__(self, name, s):
        self.name = name
        self.s = s

    def exec(self, q):
        t = 0
        for _ in range(q):
            t += 1
            q -= 1
            self.s -= 1
            if self.s == 0 or q == 0:
                return t

def execute(processes, q):
    time = 0
    completed = []
    while len(processes) != len(completed):
        for i, p in enumerate(processes):
            if not p.s == 0:
                time += p.exec(q)
                if p.s == 0:
                    completed.append((p, time))
    return completed

def run():
    n, q = list(map(int, input().split()))
    processes = []
    for _ in range(n):
        name, time = input().split()
        processes.append(Process(name, int(time)))
    completed = execute(processes, q)
    for c in completed:
        print(c[0].name, c[1])

if __name__ == '__main__':
    run()




### FIXED CODE ###

class Process(object):
    def __init__(self, name, s):
        self.name = name
        self.s = s

    def exec(self, q):
        if self.s <= q:
            time = self.s
            self.s = 0
            return time
        else:
            time = q
            self.s = self.s - q
            return time

def execute(processes, q):
    time = 0
    completed = []
    while processes:
        p = processes.pop()
        time += p.exec(q)
        if p.s == 0:
            completed.append((p, time))
        else:
            processes.insert(0, p)
    return completed

def run():
    n, q = list(map(int, input().split()))
    processes = []
    for _ in range(n):
        name, time = input().split()
        processes.append(Process(name, int(time)))
    processes.reverse()
    completed = execute(processes, q)
    for c in completed:
        print(c[0].name, c[1])

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

N = int(input())
#put a_i into list
list_a_i = list(sorted(map(int, input().split())))
remove = 0
while len(list_a_i) >=1:
    #count number of list_a_i[1]
    x = list_a_i.count(list_a_i[0])
    if x > list_a_i[0]:
        remove += x - list_a_i[0]
    elif x < list_a_i[0]:
        remove += x
    for i in range(x):
        list_a_i.remove(int(list_a_i[0]))
print(remove)


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
dic = {}
for elem in a:
    if elem not in dic:
        dic[elem] = 1
    else:
        dic[elem] += 1

ans = 0
for k in dic.keys():
    if dic[k] > k:
        ans += dic[k] - k
    elif dic[k] < k:
        ans += dic[k]

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

N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = 0
for i in range(N):
    s = 0
    for j in range(i, K+i):
        if j == N:
            break
        s += P[j] + 1
    if s > ans:
        ans = s
print(ans/2)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = 0
for i in range(K):
    ans += P[i] + 1
s = ans
for i in range(K, N):
    s -= P[i-K] + 1
    s += P[i] + 1
    if s > ans:
        ans = s
print(ans/2)
### BUGGY CODE ###

N,Q =map(int,input().split())
S = input()

pos = []
for i in range(N-1):
    if S[i:i+2] == "AC":
        pos.append(i)
def count(l,r):
    return len([x for x in pos if l-1 <= x  <= r-2])

for i in range(Q):
    l,r = map(int,input().split())
    print(count(l,r))

### FIXED CODE ###

N,Q =map(int,input().split())
S = input()

t = [0]
for i in range(N):
    t.append(t[-1]+1 if S[i:i+2] == "AC" else t[-1])
for i in range(Q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
counter = set([])
for i in range(n - 1):
    a_np = np.roll(np.array(a), i + 1)
    index = np.where(a % a_np == 0)
    counter = counter | set(index[0])
print(n - len(counter))

### FIXED CODE ###

import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0 for _ in range(a[-1] + 1)]

for x in a:
    for j in range(x, a[-1] + 1, x):
        dp[j] += 1
ans = 0
for x in set(a):
    #print(x)
    if dp[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
s=[[]for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
t=[1]*(n+1)
p=2
k=[a,b]
t[a],t[b]=0,0
while p!=n:
    c=0
    for i in s[k[-1]]:
        if t[i]:
            t[i]=0
            k.append(i)
            p+=1
            break
    else:
        c+=1
    for i in s[k[0]]:
        if t[i]:
            t[i]=0
            k=[i]+k
            p+=1
            break
    else:
        c+=1
        if c==2:
            break
print(p)
print(*k)

### FIXED CODE ###

n,m=map(int,input().split())
s=[[]for i in range(n+1)]
t=[1]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
a,b=[],[]
p=1
t[1]=0
while 1:
    for i in s[p]:
        if t[i]:
            t[i]=0
            p=i
            a.append(i)
            break
    else:
        break
p=1
while 1:
    for i in s[p]:
        if t[i]:
            t[i]=0
            p=i
            b.append(i)
            break
    else:
        break
print(1+len(a)+len(b))
t=a[::-1]+[1]+b
print(*t)
### BUGGY CODE ###

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

for _ in range(Q):
    B,C=map(int,input().split())
    A=[C if i==B else i for i in A]
    print((sum(A)))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
 
ans = sum(A)
d = Counter(A) #Counterで要素をまとめる
 
for i in range(Q):
    b, c = map(int,input().split())
    tmp = d[b] #bの総数を記憶
    d[b] = 0 #bの総数を0にする
    d[c] += tmp #cの総数にbの総数を足す
    ans += (c-b)*tmp #合計の補正
    print(ans)
### BUGGY CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7
import heapq

N,M = I()
L = [l() for _ in range(N)]
A = []
B = []
L.sort()
ans = 0
for a,b in L:
    A.append(a)
    B.append(b)
q = []
heapq.heapify(q)
for i in range(1,M+1):
    for j in range(len(A)):
        if A[0] > i:
            break
        else:
            A.pop(0)
            heapq.heappush(q,B.pop(0)*-1)
    if q:
        ans += heapq.heappop(q)*-1
print(ans)

### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7
import heapq

N,M = I()
L = [l() for _ in range(N)]
A = deque([])
B = deque([])
L.sort()
ans = 0
for a,b in L:
    A.append(a)
    B.append(b)
q = []
heapq.heapify(q)
for i in range(1,M+1):
    for j in range(len(A)):
        if A[0] > i:
            break
        else:
            A.popleft()
            heapq.heappush(q,B.popleft()*-1)
    if q:
        ans += heapq.heappop(q)*-1
print(ans)
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
ans=0
c=[0]*1001
for i in L:c[i]+=1
for i in range(1000):c[i+1]=c[i]+c[i+1]
for i in range(N-1):
    for j in range(i+1,N):
        l,r=abs(L[i]-L[j]),min(L[i]+L[j]-1,1000)
        s=c[r]-c[l]
        if l<L[i] and L[i]<=r:s-=1
        if l<L[j] and L[j]<=r:s-=1
        ans+=max(s,0)
print(ans//3)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
ans=0
c=[0]*1001
for i in L:c[i]+=1
for i in range(1000):c[i+1]=c[i]+c[i+1]
for i in range(N-1):
    for j in range(i+1,N):
        l,r=abs(L[i]-L[j]),min(L[i]+L[j]-1,1000)
        ans+=c[r]-c[l]
        if l<L[i] and L[i]<=r:ans-=1
        if l<L[j] and L[j]<=r:ans-=1
print(ans//3)
### BUGGY CODE ###

n, m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
d = {1: 0}
q = [1]
for i in q:
    s = set(g[i]) - set(d)
    d.update(dict.fromkeys(s, i))
    q.extend(s)
print('Yes')
for i in range(2, n+1):
    print(d[i])

### FIXED CODE ###

n, m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
d = {1:0}
q = [1]
for i in q:
    for j in g[i]:
        if j not in d:
            d[j] = i
            q.append(j)
print('Yes')
for i in range(2, n+1):
    print(d[i])