Harryxun/stf_run huggingface dataset:
#! /usr/bin/env python3

# from math import gcd
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

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

goal = 1
rets = []
road = {i:[] for i in range(1, N+1)}

for A, B in AB:
    road[A] += [B]
    road[B] += [A]

if not road[1]:
    print("No")
    exit()

retdict = {i:0 for i in range(1, N+1)}
retdict_dis = {i:1000000 for i in range(1, N+1)}

def dfs(bef, mark, ind, dis):

    global retdict, retdict_dis
    if mark[ind] == 1:
        return

    mark[ind] = 1
    if retdict_dis[ind] > dis:
        retdict[ind] = bef
        retdict_dis[ind] = dis

    bef = ind
    dis += 1

    for i in road[ind]:
        dfs(bef, dict.copy(mark), i, dis)

dfs(0, {i:0 for i in range(1, N+1)}, 1, 0)

print("Yes")
for i in range(2, N+1):
    print(retdict[i])


### FIXED CODE ###

#! /usr/bin/env python3

# from math import gcd
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
import copy

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

graph = [[] for i in range(N)]

for A, B in AB:
    graph[A-1] += [B]
    graph[B-1] += [A]

D = deque([0])
visited = [0] * N
visited[0] = 1

ret = [0 for i in range(N)]

while D:
    v = D.popleft()
    for i in graph[v]:
        i -= 1
        if visited[i]: continue
        visited[i] = 1
        ret[i] = v + 1
        D.append(i)

if any(ret[1:]):
    print("Yes")
    for i in ret[1:]:
        print(i)
else:
    print("No")
s=input()
ans=0
for i in range(1 << len(s)-1):
    l=[]
    for j in range(len(s)-1):
        if (i>>j)&1==1:
            l.append(s[j])
            l.append("+")
        else:
            l.append(s[j])
    l.append(s[len(s)-1])
    sum+=eval(''.join(l))
print(sum)

### FIXED CODE ###

s=input()
ans=0
for i in range(1 << len(s)-1):
    l=[]
    for j in range(len(s)-1):
        if (i>>j)&1==1:
            l.append(s[j])
            l.append("+")
        else:
            l.append(s[j])
    l.append(s[len(s)-1])
    ans+=eval(''.join(l))
print(ans)
import sys
import numpy as np
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

cnt = 0
for i in range(n):
  for j in range(i):
    a = sum((li[i] - li[j]) ** 2)**0.5
    if a - a//1 == 0:
      cnt += 1
print(cnt)


### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n, _ = rm()
li = np.array([np.array(rl()) for _ in range(n)])
cnt = 0
for i in range(n):
  for j in range(i):
    a = sum((li[i] - li[j]) ** 2)**0.5
    if a - a//1 == 0:
      cnt += 1
print(cnt)
a, b = [int(i) for input().split()]
c = (a * 3 + b) // 2
print(c)

### FIXED CODE ###

a, b = [int(i) for i in input().split()]
c =(a * 3 + b) // 2
print(c)
s = input().rstrip().split(' ')
counta = 0
countb = 0
for i in range(len(s)):
	if int(s[i]) == 7:
    	counta += 1
    elif int(s[i]) == 5:
		countb += 1
if counta == 1 and countb == 2:
	print('YES')
else:
	print('NO')

### FIXED CODE ###

s = input().rstrip().split(' ')
counta = 0
countb = 0
for i in range(int(len(s))):
	if int(s[i]) == 7:
		counta += 1
	elif int(s[i]) == 5:
		countb += 1
if counta == 1 and countb == 2:
	print('YES')
else:
	print('NO')
X = {1,2,3}
a = int(input())
b = int(input())
print(list(X-set(a)-set(b))[0])

### FIXED CODE ###

X = {1,2,3}
a = {int(input())}
b = {int(input())}
print(list(X-a-b)[0])
s=input()
k=int(input())
a=[]
a = [s[i:j] for i in range(0,len(s)) for j in range(1,len(s)+1) if i != j]
b=[]
for i in a:
    if i not in b:
        b.append(i)
b.remove("")
b=sorted(b)
print(b[k-1])


### FIXED CODE ###

s=input()
k=int(input())
a=[s[i:i+j+1] for i in range(len(s)) for j in range(k+1)]
a=set(a)
a=sorted(a)
print(a[k-1])
import math
input_list = list(map(int, input().split()))
a = input_list[0]
b = input_list[1]
x = input_list[2]

a_check = math.floor(x / a)
b_check = math.floor(pow(x / b, 10))

if (a_check < 1) | (b_check < 1):
    print(0)
    exit()
elif a_check <= b_check:
    n = a_check
elif b_check <= a_check:
    n = b_check

if n > 1000000000:
    n = 1000000000

def n_check(n_):
    if a * n_ + b * len(str(n_)) <= x:
        return True

while n_check(n) != True:
    n -= 1
    n_check(n)
print(n)


### FIXED CODE ###

# ABC 146 A
s = input()
if s == "SUN":
    print(7)
elif s == "MON":
    print(6)
elif s == "TUE":
    print(5)
elif s == "WED":
    print(4)
elif s == "THU":
    print(3)
elif s == "FRI":
    print(2)
elif s == "SAT":
    print(1)
from math import ceil
time_list = [int(input()) for i in range(5)]
sum_list = []
time_list_0 = []
for i in range(5):
    time_list_0[i] = ceil(time_list[i] / 10) * 10
for j in range(5):
    if time_list[j] == 0:
        sum_list[j] = sum(time_list_0)
    else:
        sum_list[j] = sum(time_list_0) - 10 + time_list[j] % 10
print(min(sum_list))


### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
if e - a > k:
  	print(':(')
else:
  	print('Yay!')
N =int(input())
X = map(int,input().split())
c = 100000000
for i in range(1,101):
  t=0
  for j in X:
    t += (j-i)**2

  if t=<c:
    t=c
print(c)


### FIXED CODE ###

N=int(input())
X= list(map(int,input().split()))
cnt = 1000000
for j in range(100):
    t = 0
    for i in X:
        t += (i-(j+1))**2
    if t <= cnt:
        cnt = t
print(cnt)
n=int(input())
a=[i*30000+1 for i in range(n)]
b=[30000**2-i for i in a]
p=list(map(int,input().split()))
for i in range(n):
  a[p[i]-1]+=i
  b[p[i]-1]+=i
print(*a)
print(*b)


### FIXED CODE ###

h,w=map(int,input().split())
r=0
for _ in range(h):r+=input().count('#')
print('Possible'if r==h+w-1else'Impossible')
N = int(input())
a = [0]*N
for i in range(N):
    a[i] = int(input())
b = set(a)
m = max(b)
b.remove(m)
n = max(b)
for i in range(N):
    if a[i] == m:
        print(n)
    else:
        print(m)

### FIXED CODE ###

N = int(input())
a = [0]*N
b = [0]*N
for i in range(N):
    a[i] = int(input())
    b[i] = a[i]
m = max(b)
b.remove(m)
n = max(b)

for i in range(N):
    if a[i] == m:
        print(n)
    else:
        print(m)
if N % 2 == 0:
    print(N)
else:
    print(N)

### FIXED CODE ###

N = int(input())
if N % 2 == 0:
    print(N)
else:
    print(2 *N)
N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))

for n, i in enumerate(a):
    if n > 0:
        if (a[n] - a[n-1]) == 1:
            print(0)
            exit()

def search(i, n):
    if i in a:
        return 0
    if i == n:
        return 1
    if i > n:
        return 0
    return search(i+1, n) + search(i+2, n)

ans = 1
start = 0
a.append(N+1)
for num in a:
    ans *= search(start, num-1)
    for i in range(1, N):
        start = num + i
        if start not in a:
            break

print(ans%1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
a = []
for i in range(M):
    a.append(int(input()))

for n, i in enumerate(a):
    if n > 0:
        if (a[n] - a[n-1]) == 1:
            print(0)
            exit()

dp = [-1] * (N+2)

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

for i in range(N)[::-1]:
    if dp[i] == 0:
        continue
    dp[i] = dp[i+1] + dp[i+2]


print(dp[0]%1000000007)
n, m = map(int, input().split())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
l = [0] * m
for i in range(n):
    for j in range(m):
        if j + 1 in a[i][1:]:
            l[i] += 1
count = 0
for i in range(n):
    if l[i] == n:
        count += 1
print(count)

### FIXED CODE ###

n, m = map(int, input().split())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
l = [0] * m
for i in range(n):
    for j in range(m):
        if j + 1 in a[i][1:]:
            l[j] += 1
count = 0
for i in range(m):
    if l[i] == n:
        count += 1
print(count)
import math
a, b = map(int, input().split())
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
print(lcm(a, b))

### FIXED CODE ###

A, B = map(int, input().split())
def gcd(a,b):
    x = max(a, b)
    y = min(a, b)
    if x%y == 0:
        return y
    else:
        while x%y !=0:
            z =x%y
            x =y
            y =z
        else:
            return z

def lcm(a, b):
    return int((a * b) // gcd(a, b))

ans = lcm(A, B)
print(ans)
= int(input())
v = list(map(int, input().strip().split(' ')))
c = list(map(int, input().strip().split(' ')))
l = [0] * n
for i in range(n):
  l[i]=v[i]-c[i]
l.sort(reverse=True)
s = 0
for i in range(n):
  if s < sum(l[0:i+1]):
    s = sum(l[0:i+1])
print(s)

### FIXED CODE ###

n = int(input())
v = list(map(int, input().strip().split(' ')))
c = list(map(int, input().strip().split(' ')))
l = [0] * n
for i in range(n):
  l[i]=v[i]-c[i]
l.sort(reverse=True)
s = 0
for i in range(n):
  if s < sum(l[0:i+1]):
    s = sum(l[0:i+1])
print(s)
import math

# D - Maximum Average Sets
# 問題URL:http://abc057.contest.atcoder.jp/tasks/abc057_d

# N:商品の数　A個以上B個以下の範囲で選ぶ
N, A, B = map(int, input().split())
# C：最大価値組み合わせ総数
C = 0

# 商品価値をリストに入れる
V = [int(value) for value in input().split()]
# 商品価値が高い順に並び替え
V.sort(reverse=True)

# 商品価値が高いものから出来るだけ少なく（＝A個）選ぶのが最も平均価値が高くなる
S = V[0:A]
ave = sum(S) / A
print(S)
print(ave)

Vs = V.count(min(S))
Ss = S.count(min(S))
if min(S) != max(S):
    C = math.factorial(Vs) // (math.factorial(Vs -Ss) * math.factorial(Ss))
    print(C)
else:
    i = A
    C = 0
    while i <= B and V[-i] == min(S):
        c = math.factorial(Vs) // (math.factorial(Vs -i) * math.factorial(i))
        C = C + c
        i = i + 1
    print(C)


### FIXED CODE ###

# 元ソースコード：http://abc057.contest.atcoder.jp/submissions/1183710
# 初心者の実験用です

import math
N,A,B = map(int,input().split())
V = list(map(int,input().split()))
V.sort()
S = V[-A:]
avgmax = sum(S) / A
print(avgmax)
 
Vs = V.count(min(S))
Ss = S.count(min(S))
if min(S) != max(S):
	C = math.factorial(Vs) // (math.factorial(Vs -Ss) * math.factorial(Ss))
	print(C)
else:
	i = A
	C = 0
	while i <= B and V[-i] == min(S):
		c = math.factorial(Vs) // (math.factorial(Vs -i) * math.factorial(i))
		C = C + c
		i = i + 1
	print(C)
n, k = map(int, input().split())
s = input()
t = ''

if s[0] == '0':
  t += '0'
c = 1
for i in range(1, n):
  if s[i-1] == '0' and s[i] == '0':
    c += 1
  if s[i-1] == '1' and s[i] == '0':
    t += str(c)
    c = 1
  if s[i-1] == '0' and s[i] == '1':
    t += str(c)
    c = 1
  if s[i-1] == '1' and s[i] == '1':
    c += 1
t += str(c)
t = list(map(int, t))
print(t)

# 範囲
r = 2 * k + 1
gs = []
for i in range(0,n,2):
  if i + r < n:
    gs.append(sum(t[i:i+r]))
print(max(gs))


### FIXED CODE ###

n, k = map(int, input().split())
s = input()

from itertools import groupby, accumulate

def gen(s):
  if s[:1] == '0':
  	yield 0
  for ke, g in groupby(s):
    yield len(list(g))
  if s[-1:] == '0':
    yield 0


mc = 0
acc = list(accumulate(gen(s)))
r = 2 * k + 1
if len(acc) < r:
  mc = n
else:
  for i in range(0, len(acc)-r+1, 2):
    if i == 0:
      mc = max(mc, acc[i+r-1])
    else:
      mc = max(mc, acc[i+r-1] - acc[i-1])
print(mc)
n = input()
list = []

for i in range(n):
    print("str: ")
    s,p = input().split()
    
    #s, p = sp[0], int(sp[1])
    list.append([i+1, s, p])
"""
list.append([1, "test2", 3])
list.append([2, "test3", 1])
list.append([3, "test1", 5])
list.append([4, "test1", 4])
"""

list.sort(key=lambda x:(x[1],x[2]))
for l in list:
    print(l[0])


### FIXED CODE ###


n = int(input())
list = []

for i in range(n):
    sp = input().split()
    s = str(sp[0])
    p = int(sp[1])
    list.append([i+1, s, p])

list.sort(key=lambda x:(x[1],-x[2]))
for l in list:
    print(l[0])
count = 0

a = int(input())
a, b, c, d, e = map(int, input(). split())
list1 = [a ,b, c, d, e]

for i in range(len(list1)):
  for n in range(len(list1) - i - 1):
    if(list1[n] > list1[n + 1]):
      tmp = list1[n]
      list1[n] = list1[n + 1]
      list1[n + 1] = tmp
      count += 1

for i in range(len(list1)):
  print(list1[i], end = " ")
print("\n%d" % (count))

### FIXED CODE ###

count = 0
list1 = []

a = int(input())
list1  = list(map(int, input(). split()))

for i in range(len(list1)):
  for n in range(len(list1) - i - 1):
    if(list1[n] > list1[n + 1]):
      tmp = list1[n]
      list1[n] = list1[n + 1]
      list1[n + 1] = tmp
      count += 1

print(" ".join(str(x) for x in list1))
print(count)
h, n = (int(x) for x in input().split())
A = list(map(int, input().split()))

if n == len(A):
    if sum(A) >= h:
        print('yes')
    else:
        print('No')

### FIXED CODE ###

a,b=(int(x) for x in input().split())

print(-(-a//b))
data = [input() in range(5)]
K = input()
print(":(" if data[4]-data[0]>K else "Yay!" )

### FIXED CODE ###

data = [int(input()) for i in range(5)]
K = int(input())
print(":(" if data[4]-data[0]>K else "Yay!" )
n, m = map(int, input())
ans = ""
if n == m:
  ans = "Yes"
else:
  ans = "No"
print(ans)

### FIXED CODE ###

input_numbers = list(map(int,input().split()))
n = input_numbers[0]
m = input_numbers[1]
if n == m:
  print("Yes")
else:
  print("No")
from scipy.sparse.csgraph import floyd_warshall
N,M,L=map(int,input().split())
inf=10**9+1

distance=[[inf for n in range(N)] for n in range(N)]
for n in range(N):
    distance[n][n]=0
for m in range(M):
    a,b,c=map(int,input().split())
    distance[a-1][b-1]=c
    distance[b-1][a-1]=c
distance=floyd_warshall

distance2=[[inf for n in range(N)] for n in range(N)]
for i in range(N):
    for j in range(N):
        if distance[i][j]<=L:
            distance2[i][j]=1
for n in range(N):
    distance2[n][n]=0
distance2=floyd_warshall(distance2)

Q=int(input())
for q in range(Q):
    s,t=map(int,input().split())
    if distance2[s-1][t-1]==inf:
        print(-1)
    else:
        print(distance2[s-1][t-1]-1)

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
N,M,L=map(int,input().split())
inf=10**9+1

distance=[[inf for n in range(N)] for n in range(N)]
for n in range(N):
    distance[n][n]=0
for m in range(M):
    a,b,c=map(int,input().split())
    distance[a-1][b-1]=c
    distance[b-1][a-1]=c
distance=floyd_warshall(distance)

distance2=[[inf for n in range(N)] for n in range(N)]
for i in range(N):
    for j in range(N):
        if distance[i][j]<=L:
            distance2[i][j]=1
for n in range(N):
    distance2[n][n]=0
distance2=floyd_warshall(distance2)

Q=int(input())
for q in range(Q):
    s,t=map(int,input().split())
    if distance2[s-1][t-1]==inf:
        print(-1)
    else:
        print(int(distance2[s-1][t-1]-1))
N = int(input())
H = list(map(int, input().split()))
max_lst = []
min_lst = []
max_h = H[0]
min_h = H[0]
s = 0
for i in range(1, N):
    if H[i-1] <= H[i]:
        if H[0] not in max_lst and H[0] not in min_lst:
            min_lst.append(H[0])
        if max_h == 0:
            min_lst.append(min_h)
        if i == N-1:
            max_lst.append(H[i])
        max_h = H[i]
        min_h = 0
    elif H[i-1] >= H[i]:
        if H[0] not in max_lst and H[0] not in min_lst:
            max_lst.append(H[0])
            s = 1
        if min_h == 0:
            max_lst.append(max_h)
        if i == N-1:
            min_lst.append(H[i])
        min_h = H[i]
        max_h = 0
cnt = 0
if s == 0:
    for i in range(len(min_lst)-1):
        cnt += max_lst[i] - min(min_lst[i], min_lst[i+1])
    cnt += max_lst[-1] - min_lst[-1]
else:
    for i in range(1, len(max_lst)):
        cnt += max_lst[i] - min(min_lst[i-1], min_lst[i])
    cnt += max_lst[0] - min_lst[0]
print(cnt)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
ans = 0
H.append(0)
for i in range(max(H)):
    cnt = 0
    for k in range(N):
        if H[k] != 0 and H[k+1] == 0:
            cnt += 1
    ans += cnt
    H = list(map(lambda x:(x-1, 0)[x == 0], H))
print(ans)
import sys
def input(): return sys.stdin.readline().strip()
import math
def resolve():
    a,b=map(int, input().split())
    print(a*b//math.gcd(a,b))
resolve()

### FIXED CODE ###

import sys


def input(): return sys.stdin.readline().strip()


import fractions


def resolve():
    a, b = map(int, input().split())
    print((a * b) // fractions.gcd(a, b))
resolve()
N = int(input())
d={}
for i in range(N):
    x, u = map(int, input().split())
    d[u]=x
print(sum(d["JPY"])+sum(d["BTC"])*380000)

### FIXED CODE ###

N = int(input())
sum=0
for i in range(N):
    x, u = list(map(str, input().split()))
    if u == "JPY":
        sum+=int(x)
    else:
        sum+=float(x)*380000
print(sum)
answer = raw_input()
if len(answer) == 2:
    print(answer)
else:
    print(answer[2] + answer[1] + answer[0])

### FIXED CODE ###

answer = input().strip()
if len(answer) == 2:
    print(answer)
else:
    print(answer[2] + answer[1] + answer[0])
D, N = (int(i) for i in input().split())
if D == 0:
    print(int(1*N)
elif D == 1:
    print(int(100*N)
elif D == 2:
    print(int(10000 * N)

### FIXED CODE ###

D, N = (int(i) for i in input().split())
# D = 2
# N = 100

if N != 100:
    if D == 0:
        print(int(1*N))
    elif D == 1:
        print(int(100*N))
    elif D == 2:
        print(int(10000 * N))

else:
    if D == 0:
        print(101)
    elif D == 1:
        print(10100)
    elif D == 2:
        print(1010000)
for i in range(int(input())):
	t,x,y=map(int,input().split())
	if(t+x+y)%2+(t<x+y):
      print("No")
      exit()
print("Yes")

### FIXED CODE ###

for i in range(int(input())):
  t,x,y=map(int,input().split())
  if(t+x+y)%2+(t<x+y):
    print("No")
    exit()
print("Yes")
import math
a, b,c = map(int, input().split())
if (c - a - b > 0) and (4*a*b < int(math.pow((c - a - b)), 2)):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

a, b,c = map(int, input().split())
if (0 < c - a - b) and (4*a*b < (c - a - b)*(c - a - b)):
    print("Yes")
else:
    print("No")
N=int(input())
if N[-1] == 7:
     print("Yes")
elif N[-2] == 7:
    prnt("Yes")
elif N[-3] == 7:
    print("Yes")
else :
    print("No")

### FIXED CODE ###

N=input()
if N[-1] == '7':
     print("Yes")
elif N[-2] == '7':
    print("Yes")
elif N[-3] == '7':
    print("Yes")
else :
    print("No")
l = map(int,raw_input().split())
L = sorted(l,key=int)
print "L[0]","L[1]","L[2]"

### FIXED CODE ###

l=list(map(int,input().split()))
L=sorted(l)
print(L[0],L[1],L[2])
N = int(input()) - 1
T,A = map(int,input().split())
tmp = 0
X = 0
List = list(map(int,input().split()))
List2 = []
for i in range(N):
  tmp =abs(A - (T - List.pop(i) * 0.001))
  List2.append(tmp)
X = min(List2)
print(str(List2.index(X) + 1))

### FIXED CODE ###

N = int(input())
T,A = map(int,input().split())
List = list(map(int,input().split()))
List = [abs(A - (T - x * 0.006)) for x in List]
x = min(List)
print(str(List.index(x) + 1))
def check(s,t,n):
    if s.find(t) != -1:
        print(n)
    else:
        n += 1
        t = t[:-1]
        check(s,t,n)
s = input()
t = input()
n = 0
check(s,t,n)

### FIXED CODE ###

main = input()
word = input()
temp = main
resultArray = []
final = len(word)
for j in range(len(main) - (len(word) - 1)):
    result = ''
    for i in range(len(word)):
        if main[j + i] == word[i]:
            result += '1'
        else:
            result += '0'
    resultArray.append(result)
for i in resultArray:
    if i.count('0') < final:
        final = i.count('0')
print(final)
a=int(input())
b=int(input())
if a > b:
  print("a > b")
elif a < b:
   print("a < b")
else:
    print("a == b")  


### FIXED CODE ###

n=input().split()
a=int(n[0])
b=int(n[1])
if a > b:
    print("a > b")
elif a < b:
    print("a < b")
else:
    print("a == b")
x = import()
 ans = int(x)**3
 print ans

### FIXED CODE ###

x = input()
ans = x**3
print ans
W,E,R = map(int,input().split())
if W + E + R >= 22:
    ans("bust")
else :
    ans("win")
print(ans)

### FIXED CODE ###

W,E,R = map(int,input().split())
if W + E + R >= 22:
    ans="bust"
else :
    ans="win"
print(ans)
s = list(set(input()))
s.sort()
flag = False
for i in range(26):
    if s[i] != chr(ord('a') + i):
        flag = True
        print(chr(ord('a') + i))
        break
if flag == False:
    print('None')

### FIXED CODE ###

s = sorted(list(set(input())))
lst = 'abcdefghijklmnopqrstuvwxyz'
flag = False
for i in lst:
    if i not in s:
        flag = True
        print(i)
        break
if flag == False:
    print('None')
import heapq
n,m=map(int,input().split())
c=[[] for i in range(m+1)]
for i in range(n):
    a,b=map(int,input().split())
    c[a].append(-b)
d=[]
heapq.heapify(d)
ans=0
for i in range(1,m+1):
    for j in range(len(c[i])):
        heapq.heappush(d,c[i][j])
    if d!=[]:
        ans+=heapq.heappop(d) 
print(-ans)

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
c=[[] for i in range(m+1)]
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        c[a].append(-b)
d=[]
heapq.heapify(d)
ans=0
for i in range(1,m+1):
    for j in range(len(c[i])):
        heapq.heappush(d,c[i][j])
    if d!=[]:
        ans+=heapq.heappop(d) 
print(-ans)
from math import sqrt
x1, y1, x2, y2 = map(int, input().split())
r = sqrt((x2 - x1)**2 + (y2 - x2)**2)
print(r)

### FIXED CODE ###

import math
x1, y1, x2, y2 = map(float, input().split())
print(math.sqrt((x2 - x1)**2 + (y2 -y1)**2))
import numpy as np
import pandas as pd

n, c = list(map(int, input().split(' ')))
x, v = [], []

for i in range(n):
  x_, v_ = list(map(int, input().split(' ')))
  x.append(x_)
  v.append(v_)
x = np.array(x)
v = np.array(v)
sum_v = np.cumsum(v)
inv_x = c - x[::-1]
inv_v = v[::-1]
sum_inv_v = np.cumsum(inv_v)

cal = sum_v - x
inv_cal = sum_inv_v - inv_x

cal_cummax = pd.Series(cal).cummax().as_matrix()
inv_cal_cummax = pd.Series(inv_cal).cummax().as_matrix()

fr_double_cal = sum_v - 2 * x + \
    np.insert(inv_cal_cummax[:-1], 0, 0)[::-1]
fl_double_cal = sum_inv_v - 2 * inv_x + \
    np.insert(cal_cummax[:-1], 0, 0)[::-1]

print(np.max(
    [0, cal.max(), inv_cal.max(), fr_double_cal.max(), fl_double_cal.max()]))


### FIXED CODE ###

import numpy as np

n, c = list(map(int, input().split(' ')))
x, v = [], []

for i in range(n):
  x_, v_ = list(map(int, input().split(' ')))
  x.append(x_)
  v.append(v_)
x = np.array(x)
v = np.array(v)
sum_v = np.cumsum(v)
inv_x = c - x[::-1]
inv_v = v[::-1]
sum_inv_v = np.cumsum(inv_v)

cal = sum_v - x
inv_cal = sum_inv_v - inv_x

cal_cummax = np.maximum.accumulate(cal)
inv_cal_cummax = np.maximum.accumulate(inv_cal)

fr_double_cal = sum_v - 2 * x + \
    np.insert(inv_cal_cummax[:-1], 0, 0)[::-1]
fl_double_cal = sum_inv_v - 2 * inv_x + \
    np.insert(cal_cummax[:-1], 0, 0)[::-1]

print(np.max(
    [0, cal.max(), inv_cal.max(), fr_double_cal.max(), fl_double_cal.max()]))