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

def func(ans, dic, keylst):
    if keylst == []:
        return ans
    else:
        array = []
        for i in range(2, N + 1):
            if not(i in ans.keys()):
                for j in keylst:
                    if j in dic[i]:
                        ans[i] = j
                        array.append(i)
                        break
        func(ans, dic, array)


N, M = map(int, input().split())
dic = {}
for i in range(N):
    dic[i + 1] = []

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

ans = {}
keylst = [1]
func(ans, dic, keylst)

flg=True
for i in range(2,N + 1):
    if not(i in ans.keys()):
        flg=False
        break

if flg:
    print('Yes')
    for i in range(2,N + 1):
        print(ans[i])
else:
    print('No')


### FIXED CODE ###

from collections import deque

n,m=map(int,input().split())
graph=[[] for _ in range(n+1)]

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

ans=[-1]*(n+1)
ans[0]=0
ans[1]=0

d=deque()
d.append(1)

while d:
    v=d.popleft()
    for i in graph[v]:
        if ans[i]!=-1:
            continue
        ans[i]=v
        d.append(i)

ans=ans[2:]
print("Yes")
print(*ans,sep="\n")
### BUGGY CODE ###

r,c,k=map(int,input().split())

fuck=[list(map(int,input().split())) for _ in range(k)]

rck=[[0]*c for _ in range(r)]

for [rr,cc,kk] in fuck:
    rck[rr-1][cc-1]=kk

#dp[y][x][cnt]

dp=[[[0]*4 for _ in range(c)] for _ in range(r)]
#print(dp)
for y in range(r):
    for x in range(c):
        #1行目
        if y == 0:
            if x==0:
                dp[y][x][1]=rck[y][x]
            if x>=1:
                dp[y][x][1]=max(dp[y][x-1][1],rck[y][x])
                dp[y][x][2]=max(dp[y][x-1][2],dp[y][x-1][1]+rck[y][x])
            if x>=2:
                dp[y][x][3]=max(dp[y][x-1][3],dp[y][x-1][2]+rck[y][x])
        else:
            #1は、上0+1 or 左0+1 or 上1 or 左1
            #count1ケース
            for i in range(1,4):
                if i==1:
                    uemax=max([max(dp[y-1][x][1],dp[y-1][x][2],dp[y-1][x][3])])
                    dp[y][x][i]=uemax+rck[y][x]
                    if x>0:
                        dp[y][x][i]=max(dp[y][x][i],dp[y][x-1][i])
                elif i>=2:
                    if x>=1:
                        dp[y][x][i]=max(dp[y][x-1][i],dp[y][x-1][i-1]+rck[y][x])

print(max(dp[-1][-1]))
             
             

### FIXED CODE ###

def pri(x):
    for item in x:
        print(item)

r,c,k=map(int,input().split())

fuck=[list(map(int,input().split())) for _ in range(k)]

rck=[[0]*(c+1) for _ in range(r+1)]

for [rr,cc,kk] in fuck:
    rck[rr][cc]=kk
#pri(rck)
#dp[y][x][cnt]

dp=[[0]*4 for _ in range(c+1)]
#print(dp)
for y in range(1,r+1):
    for x in range(1,c+1):
        
        dp[x][0]=max(dp[x-1][0],dp[x][0],dp[x][1],dp[x][2],dp[x][3])
        dp[x][1]=max(dp[x][0]+rck[y][x],dp[x][1],dp[x-1][1])
        dp[x][2]=max(dp[x-1][1]+rck[y][x],dp[x][2],dp[x-1][2],dp[x][1])
        dp[x][3]=max(dp[x-1][2]+rck[y][x],dp[x][3],dp[x-1][3],dp[x][2])
        #print(y,x,dp)

print(max(dp[-1]))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans = 1
for i in range(N):
    ans *= A[i]
    if ans >> 10**18:
        break
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans = 1
flg = True
for i in range(N):
    ans *= A[i]
    if A[-1] != 0:
        if ans > 10**18:
            flg = False
            break
    if A[-1] == 0:
        ans = 0
        break
if flg == False:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

s = input()
ans = 0
l = len(s)

for i in range(l - 3):
    if int(s[i:i+2]) % 2 != 0:
        continue
    else:
        for j in range(i + 4, l + 1):
            sub_s = int(s[i:j])
            if sub_s % 2019 == 0: ans += 1
print(ans)

### FIXED CODE ###

s = input()[::-1]

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2
print(ans)
### BUGGY CODE ###

N=int(input())
S=input()
SS=[a for a in S]
SS.insert(0,0)
answer=0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        for k in range(j+1,N+1):
            if i+k==j*2:
                continue
            else:
                if SS[i]!=SS[j] and SS[j]!=SS[k] and SS[k]!=SS[i]:
                    answer+=1
print(answer)


### FIXED CODE ###

N=int(input())
S=input()
SS=[a for a in S]
SS.insert(0,0)
nr=S.count("R")
ng=S.count("G")
nb=S.count("B")
n=0
for i in range(1,N-1):
    for j in range(i+1,N):
        k=j*2-i
        if k<=N :
            if SS[i]!=SS[j] and SS[j]!=SS[k] and SS[k]!=SS[i]:
                n+=1
answer=nr*ng*nb-n
print(answer)
### BUGGY CODE ###

MOD = 10**9 + 7


def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a - (a // b) * b

    return a


def lcm(iterable):
    a = iterable[0]

    for b in iterable:
        a = a * b // gcd(a, b)

    return a


def inv_mod(x: int):
    return pow(x, MOD - 2)


def pow(x: int, n: int) -> int:
    res = 1
    while n > 0:
        if n & 1 == 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1

    return res


def main():
    N = int(input())
    an = list(map(int, input().split()))

    lcm_an = lcm(an)

    ans = 0
    for a in an:
        ans = (ans + lcm_an * inv_mod(a)) % MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import functools

MOD = 10**9 + 7


def lcm(a, b) -> int:
    c, d = a, b
    while d != 0:
        c, d = d, c % d
    return a // c * b


def inv_mod(x):
    return pow(x, MOD - 2)


def pow(x: int, n: int) -> int:
    res = 1
    while n > 0:
        if n & 1 == 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1

    return res


def main():
    N = int(input())
    an = list(map(int, input().split()))

    lcm_an = functools.reduce(lcm, an)
    lcm_an %= MOD

    ans = 0
    for a in an:
        ans = (ans + lcm_an * inv_mod(a)) % MOD

    print(ans)


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

X = input()
rep = X.replace("ST", "")
while X != rep:
    X = rep
    rep = X.replace("ST", "")
print(len(X))

### FIXED CODE ###

X = input()
stack = []
for s in X:
    if s == "S":
        stack.append(s)
    elif s == "T":
        if len(stack) == 0 or stack[-1] == "T":
            stack.append(s)
        else:
            stack.pop(-1)
print(len(stack))
### BUGGY CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
a.append(x)
b=[]
m=10**9

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
if n==1:
  print(abs(x-a[0]))
else:
  for i in range(n):
    for j in range(i+1,n+1):
      b.append(abs(a[i]-a[j]))
  for i in range(len(b)-1):
    for j in range(i+1,len(b)):
      m=min(m,gcd(b[i],b[j]))
  print(m)


### FIXED CODE ###

n,x=map(int,input().split())
A=[]*n
A[:]=map(int,input().split())
for i in range(n):
  A[i]=abs(A[i]-x)
if len(A)==1:
  print(A[0])
else:
  def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
      
  left=[0]*n
  right=[0]*n
  for i in range(1,n):
    left[i]=gcd(left[i-1],A[i-1])
    right[n-1-i]=gcd(right[n-i],A[n-i])
 
  ans=10**9
  for i,j in zip(left,right):
    ans=min(ans,gcd(i,j))
  print(ans)
### BUGGY CODE ###

# ContestName
# URL
import sys
import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, C = i2nn()
    D = np.array(ii2nnn(C))
    c = np.array(ii2nnn(N))
    E = np.array([[0] * C for _ in range(3)])
    for i in range(N):
        for j in range(N):
            before = c[i,j]
            e = (i+j) % 3
            E[e,:] += D[before-1,:]
    iwakan = N * N * 1000
    for c1 in range(C):
        for c2 in range(C):
            for c3 in range(C):
                if c1 == c2 or c2 == c3 or c3 == c1:
                    continue
                n = E[0,c1] + E[1,c2] + E[2,c3]
                if n < iwakan:
                    iwakan = n
    print(iwakan)

main()


### FIXED CODE ###

# ContestName
# URL
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, C = i2nn()
    D = ii2nnn(C)
    c = ii2nnn(N)
    E = [[0] * C for _ in range(3)]
    for i in range(N):
        for j in range(N):
            before = c[i][j]
            e = (i+j) % 3
            for after in range(1, C+1):
                E[e][after-1] += D[before-1][after-1]
    iwakan = N * N * 1000
    for c1 in range(C):
        for c2 in range(C):
            for c3 in range(C):
                if c1 == c2 or c2 == c3 or c3 == c1:
                    continue
                n = E[0][c1] + E[1][c2] + E[2][c3]
                if n < iwakan:
                    iwakan = n
    print(iwakan)

main()
### BUGGY CODE ###

#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
#color_vertex ={i:set() for i in range(1,N+1)} #頂点に接続している辺に使った色
color_vertex ={i:[] for i in range(1,N+1)} #頂点に接続している辺に使った色
color_side =[0]*(N-1)
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    color =0
    while True:
        q,color =divmod(color,color_max)    #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a] and color not in color_vertex[v_b]:  #使った色リストに入っているか？
            color_side[i] =color+1          #辺の色を出力用に決める（2行上の＋１）
            #color_vertex[v_a].add(color)    #前の頂点に使った色として追加
            #color_vertex[v_b].add(color)    #先の頂点に使った色として追加
            color_vertex[v_a].append(color)    #前の頂点に使った色として追加
            color_vertex[v_b].append(color)    #先の頂点に使った色として追加
            break
        else:
            color +=1

    
#出力
print(color_max)
#for i in color_side:
 #   print(i)
print(*color_side, sep="\n")

### FIXED CODE ###

"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')
### BUGGY CODE ###

H, W, M = map(int, input().split())
hList = {i+1: 0 for i in range(H)}
wList = {i+1: 0 for i in range(W)}
pList = set()
#print(hList, wList, pList)
for _ in range(M):
  h, w = list(map(int, input().split()))
  #print(h, w)
  hList[h] += 1
  wList[w] += 1
  pList.add((h, w))
#print(hList, wList, pList)

maxCount = 0
for h, count in hList.items():
  if maxCount<count:
    maxCount = count
maxHList = [h for h, count in hList.items() if count==maxCount]


maxCount = 0
for w, count in wList.items():
  if maxCount<count:
    maxCount = count
maxWList = [w for w, count in wList.items() if count==maxCount]

counterList = []
for maxH in maxHList:
  for maxW in maxWList:
    counter = 0
    for h, w in pList:
      #print(h, maxH, w, maxW)
      if h==maxH or w==maxW:
        counter += 1
    counterList.append(counter)
print(max(counterList))


### FIXED CODE ###

import sys
H, W, M = map(int, input().split())
hList = {i+1: 0 for i in range(H)}
wList = {i+1: 0 for i in range(W)}
pList = set()
#print(hList, wList, pList)
for _ in range(M):
  h, w = list(map(int, input().split()))
  #print(h, w)
  hList[h] += 1
  wList[w] += 1
  pList.add((h, w))
#print(hList, wList, pList)

maxHCount = max(hList.values())
maxHList = [h for h, count in hList.items() if count==maxHCount]


maxWCount = max(wList.values())
maxWList = [w for w, count in wList.items() if count==maxWCount]

#counterList = []
#for maxH in maxHList:
#  for maxW in maxWList:
#    counterList.append(hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0))
#print(max(counterList))
#print(max(((hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0)) for maxH in maxHList for maxW in maxWList)))
#print(max(((hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0)) for maxH in maxHList for maxW in maxWList)))

#if M < len(maxHList)*len(maxWList):
#	print(maxHCount + maxWCount)
#	sys.exit(0)

for maxH in maxHList:
  for maxW in maxWList:
    if (maxH, maxW) not in pList:
      print(maxHCount + maxWCount)
      sys.exit(0)

print(maxHCount + maxWCount - 1)
### BUGGY CODE ###

string = input()

flg = True
while len(string) > 0:
  if string.endswith('dream'):
    string = string[:-5]
  elif string.endswith('dreamer'):
    string = string[:-7]
  elif string.endswith('erase'):
    string = string[:-6]
  elif string.endswith('eraser'):
    string = string[:-6]
  else:
    print('NO')
    flg = False
if flg:
  print('YES')

### FIXED CODE ###

string = input()
 
flg = True
while len(string) > 0:
  if string.endswith('dream'):
    string = string[:-5]
  elif string.endswith('dreamer'):
    string = string[:-7]
  elif string.endswith('erase'):
    string = string[:-5]
  elif string.endswith('eraser'):
    string = string[:-6]
  else:
    print('NO')
    flg = False
    break
if flg:
  print('YES')
### BUGGY CODE ###

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

scores = []

s = 0
score = 1
for i in range(k):
    score *= a[i]

scores.append(score)
for i in range(k,n):
    score = score // a[s] * a[i]
    s += 1
    scores.append(score)

#print(scores)
for i in range(len(scores)-1):
    if scores[i+1] > scores[i]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

f = 0
for _ in range(n-k):
    if a[f] < a[f+k]:
        print('Yes')
    else:
        print('No')
    f += 1
### BUGGY CODE ###

n = int(input())
l = [input().split() for _ in range(n)]
ans = [0,0]
for i in range(n):
    ref_1 = int(l[i][0])
    ref_2 = int(l[i][1])
    for j in range(2,10**18-1):
        if (ans[0]>ref_1) or (ans[1]>ref_2):
            ref_1 = int(l[i][0])
            ref_2 = int(l[i][1])
            ref_1 *= j
            ref_2 *= j
        else:
            break

    ans[0], ans[1] = ref_1, ref_2
print(sum(ans))

### FIXED CODE ###

n = int(input())
A, B = 0, 0
for i in range(n):
    x, y = map(int,input().split())
    dx, dy = 1, 1
    if A > x:
        dx = A // x
        if A % x != 0:
            dx += 1
    
    if B > y:
        dy = B // y
        if B % y != 0:
            dy += 1

    a = max(dx, dy)
    A, B = a * x, a * y
print(A + B)
### BUGGY CODE ###

n,m=[int(i) for i in input().split()]
c={}
for _ in range(n):
  a,b=[int(i) for i in input().split()]
  if a in c:
    c[a].append(b)
  else:
    c[a]=[b]
k=0
l=[]
for i in range(m+1):
  if i in c:
    j=list(reversed(sorted(c[i])))
    if l:
      if j[0]>l[0]:
        k+=j[0]
        if len(j)>1:
          l=list(reversed(sorted(l+j[1:])))
      else:
        k+=l[0]
        l=list(reversed(sorted(l[1:]+j)))
    else:
      k+=j[0]
      l=j[1:]
  else:
    if l:
      k+=l[0]
      l=l[1:]
  if len(l)>m:
    l=l[:m]
print(k)

### FIXED CODE ###

import heapq
n, m = [int(i) for i in input().split()]
ab = []
for _ in range(n):
    a, b = [int(i) for i in input().split()]
    ab.append([a, -b])
ab.sort()
j = 0
ans=0
h = []
for i in range(1, m + 1):
    while j<n and ab[j][0] <= i:
        heapq.heappush(h, ab[j][1])
        j += 1
    if h:
        ans += heapq.heappop(h)
print(-ans)
### BUGGY CODE ###

while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	unit = min(book)
	max_shelf = max(sum(book)/m,max(book))
	while 1:
		i = 0
		cur_shelf,num = 0,1
		while i < n:
			if num > m: break
			if cur_shelf + book[i] > max_shelf:
				num += 1
				cur_shelf = 0
			else:
				cur_shelf += book[i]
				i += 1
		else:
			break
		max_shelf += unit
	print max_shelf

### FIXED CODE ###

def isStorage(max_shelf):
	i,cur_shelf,num = 0,0,1
	while i < n:
		if num > m:
			return False
		if cur_shelf + book[i] > max_shelf:
			num += 1
			cur_shelf = 0
		else:
			cur_shelf += book[i]
			i += 1
	else:
		return True
			
while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	max_shelf = len = sum(book)/2
	while len:
		len /= 2
		max_shelf -= len if isStorage(max_shelf) else -len
	max_shelf += 6
	while isStorage(max_shelf-1):
		max_shelf -= 1
	print max_shelf
### BUGGY CODE ###

def insertion_sort(a, n):
    for i in range(1, n):
        v = a[i]
        j = i - 1
        while ((j >=0) & (a[j] > v)):
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v
    return a

store_num, drink_num = [int(i) for i in input().split(" ")]
a_list = []
for i in range(store_num):
    a, b = [int(i) for i in input().split(" ")]
    for j in range(b):
        a_list.append(a)
b_list = insertion_sort(a_list, len(a_list))
ans = 0
for i_ in range(drink_num):
    ans += b_list[i_]
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = []
for i in range(n):
    i,j = (map(int, input().split()))
    a += [[i,j]]
a = sorted(a)
count = 0
value = 0
for (i,j) in a:
    if count + j >= m:
        value += (m - count) * i
        break
    else:
        value += i * j
        count += j
print(value)
### BUGGY CODE ###

import sys
from subprocess import Popen, PIPE
from itertools import groupby
from collections import Counter

def main():
    N, *S = sys.stdin.read().split()
    T = []
    inv_dict = {}
    for s in S:
        factors = list(map(int, Popen(["factor", s], stdout=PIPE).communicate()[0].split()[1:]))
        t = 1
        t_inv = 1
        for f, group in groupby(factors):
            n = len(list(group)) % 3
            if n == 1:
                t *= f
                t_inv *= f * f
            elif n == 2:
                t *= f * f
                t_inv *= f
        T.append(t)
        inv_dict[t] = t_inv

    counter_T = Counter(T)
    ans = 0
    for t, t_cnt in counter_T.items():
        if t == 1:
            ans += 1
            continue
        t_inv = inv_dict[t]
        t_inv_cnt = counter_T[t_inv]
        if t_cnt > t_inv_cnt or (t_cnt == t_inv_cnt and t > t_inv):
            ans += t_cnt
    print(ans)

main()


### FIXED CODE ###

import sys
from collections import Counter

def make_prime_checker(n):
    # nまでの自然数が素数かどうかを表すリストを返す  O(nloglogn)
    is_prime = [False, True, False, False, False, True] * (n//6+1)
    del is_prime[n+1:]
    is_prime[1:4] = False, True, True
    for i in range(5, int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*i::i] = [False] * (n//i-i+1)
    return is_prime

def main():
    Primes = [p for p, is_p in enumerate(make_prime_checker(2200)) if is_p]
    def decomp(n):
        res1 = res2 = 1
        for p in Primes:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            cnt %= 3
            if cnt == 1:
                res1 *= p
            elif cnt == 2:
                res2 *= p
        if int(n**0.5)**2 == n:
            res2 *= int(n**0.5)
        else:
            res1 *= n
        return res1 * res2 * res2, res1 * res1 * res2

    N, *S = map(int, sys.stdin.buffer.read().split())
    T = []
    inv_dict = {}
    for s in S:
        t, t_inv = decomp(s)
        T.append(t)
        inv_dict[t] = t_inv

    counter_T = Counter(T)
    ans = 0
    for t, t_cnt in counter_T.items():
        if t == 1:
            ans += 1
            continue
        t_inv = inv_dict[t]
        t_inv_cnt = counter_T[t_inv]
        if t_cnt > t_inv_cnt or (t_cnt == t_inv_cnt and t > t_inv):
            ans += t_cnt
    print(ans)

main()
### BUGGY CODE ###

s = str(input())
l = []
n = len(s)
for i in range(n):
    for j in range(i,n):
        l.append(s[i:j+1])
l = list(set(l))
l.sort()
#print(l)
print(l[int(input())-1])

### FIXED CODE ###

s = list(input())
n = len(s)
k = int(input())
if k > n:
    K = n
else:
    K = k
anset = set()
for lenght in range(1,K+1):
    for i in range(n - lenght + 1):
        anset.add("".join(s[i:i+lenght]))
anset = list(anset)
anset.sort()
print(anset[k-1])
### BUGGY CODE ###

h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

# print(h,w,m)
# print(HW)

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]

for i in range(m):
    # print(h,w)
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

# print('---')
# print(sum_h)
# print(sum_w)
# print('---')
sum_h.sort(reverse=True)
sum_w.sort(reverse=True)
# print(sum_h)
# print(sum_w)

max_bombs = 0
for h_bombs, h_index in sum_h:
    # print(h_bombs, h_index)
    for w_bombs, w_index in sum_w:
        bombs = h_bombs + w_bombs
        if [h_index, w_index] in HW:
            bombs -= 1
        if max_bombs < bombs:
            max_bombs = bombs

print(max_bombs)


### FIXED CODE ###

h, w, m = map(int, input().split())
HW = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]

sum_h = [[0,0] for _ in range(h)] # [sum, index]
sum_w = [[0,0] for _ in range(w)]
for i in range(m):
    h,w = HW[i]
    sum_h[h][0] += 1
    sum_w[w][0] += 1
    sum_h[h][1] = h
    sum_w[w][1] = w

h_num_ix = {}
for num,ix in sum_h:
    if not num in h_num_ix:
        h_num_ix[num] = set()
    h_num_ix[num].add(ix)

w_num_ix = {}
for num,ix in sum_w:
    if not num in w_num_ix:
        w_num_ix[num] = set()
    w_num_ix[num].add(ix)

max_h_num = max(h_num_ix)
max_w_num = max(w_num_ix)

# print(sorted(HW))
# print('---')
# print(h_num_ix)
# print(w_num_ix)
# print(max_h_num)
# print(max_w_num)
# print('====')

SHW = set()
for h,w in HW:
    SHW.add((h,w))
# print(SHW)

max_num = max_h_num + max_w_num - 1
for h_ix in h_num_ix[max_h_num]:
    for w_ix in w_num_ix[max_w_num]:
        num = max_h_num + max_w_num
        # if [h_ix, w_ix] in HW: continue
        if (h_ix, w_ix) in SHW: continue
        max_num += 1
        print(max_num)
        exit()
print(max_num)