Harryxun/stf_run huggingface dataset:
def connect(blist, a):
	x = []
	for i in range(len(blist)):
		if blist[i][0]==a:
			x.append(blist[i][1])
		elif blist[i][0]>a:
			break
	for j in range(len(blist)):
		if blist[j][1]==a:
			x.append(blist[j][0])
	return(x)

n,m = (int(i) for i in input().split())
y = [[int(i) for i in input().split()] for i in range(m)]
answer = 0
for j in range(len(y)):
	y2,z = [],set()
	for k in range(1,n+1):
		y2.append(connect(y[:j]+y[min(j+1,len(y)):],k))
	for j2 in y2[y[j][0]-1]:
		z.add(j2)
	num = 0
	while y[j][1] not in z and len(z) != num:
		num,z2 = len(z),list(z)
		for k in z2:
			for k2 in y2[k-1]:
				z.add(k2)
	if y[j][1] not in z:
		answer += 1
print(answer)


### FIXED CODE ###

x = [int(i) for i in input().split()]
x.sort()
if x[0]==x[1]: print(x[2])
else: print(x[0])
print(["No","Yes"][input()==input()[::-1]])

### FIXED CODE ###

N=str(input())
if N==N[::-1]:
    print("Yes")
else:
    print("No")
n,a,b = map(int, input().split())

center = abs(a-b) // 2
# restore
if abs(a-b) % 2 == 0:
    print(center)
else:
    leftside = a - 1
    rightside = n - b
    
    print(min(leftside,rightside) + 1 + (B-A-1)//2)



### FIXED CODE ###

n,a,b = map(int, input().split())

center = abs(a-b) // 2
# restore
if abs(a-b) % 2 == 0:
    print(center)
else:
    leftside = a - 1
    rightside = n - b
    
    print(min(leftside,rightside) + 1 + (b-a-1)//2)
a,b,k = input().strip().split
a,b,k = [int(a), int(b), int(k)]

if k < a:
	a = a-k
elif k >= a+b:
    a = 0
    b = 0
elif a+b > k > a:
    b = b-(k-a)
	a = 0


### FIXED CODE ###

s,t = input().split()
print(t + s)
N = int(input())
s =[int(input()) for _ in range(N)]

if sum(s) % 10 != 0:
  s -= min([for x in s if s % 10 == 0] + [s])

print(s)


### FIXED CODE ###

N = int(input())
ssum = 0
not10min = -1
for si in (int(input()) for _ in range(N)):
  ssum += si
  if si % 10 != 0:
    if not10min < 0:
      not10min = si
    else:
      not10min = min(not10min, si)

if ssum % 10 ==0:  
  if not10min >= 0:
    ssum -= not10min
  else:
    ssum = 0
print(ssum)
N=int(input())
M=list(map(int,input().split))
S1=0
S2=sum(M)
t=0
for i in range(N):
    S1+=M[i]
    S2=S2-M[i]
    if t>=abs(S2-S1):
        t=abs(S2-S1)
print(t)

### FIXED CODE ###

N=int(input())
M=input().split()
for i in range(N):
    M[i]=int(M[i])
S1=0
S2=sum(M)
t=100000
for i in range(N):
    S1+=M[i]
    S2=S2-M[i]
    if t>abs(S2-S1):
        t=abs(S2-S1)
print(t)
A,B,C,D,E,F=map(int,input().split())
w=set()
s=set()
for i in range(31):
    for j in range(16):
        if 100*(A*i+B*j)<=F:
            w.add(100*(A*i+B*j))
for i in range(1501):
    for j in range(751):
        if C*i+D*j<=F/2:
            s.add(C*i+D*j)
w=list(w)
del w[0]
s=list(s)
s.sort()
M=0
for i in w:
    for j in range(len(s)-1,-1,-1):
        t=s[j]/i
        if t*100<=E:
            if t>M and i+s[j]<=F:
                W,S=i,s[j]
                M=t
            break
print(W+S,S)

### FIXED CODE ###

A,B,C,D,E,F=map(int,input().split())
w=set()
s=set()
for i in range(31):
    for j in range(16):
        if 100*(A*i+B*j)<=F:
            w.add(100*(A*i+B*j))
for i in range(1501):
    for j in range(751):
        if C*i+D*j<=F/2:
            s.add(C*i+D*j)
w=list(w)
w.sort()
del w[0]
s=list(s)
s.sort()
M=-1
for i in w:
    for j in range(len(s)-1,-1,-1):
        if s[j]*100<=E*i:
            if s[j]>M*i and i+s[j]<=F:
                W,S=i,s[j]
                M=s[j]/i
print(W+S,S)
from sys import stdin
import queue
import sys

s,t=input().split()
ans=0
for i in range(3):
    if s[i]==t[i]:
        ans+=1
print(ans)


### FIXED CODE ###

from sys import stdin
import queue
import sys

s=input()
t=input()
ans=0
for i in range(3):
    if s[i]==t[i]:
        ans+=1
print(ans)
import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(10)]
for i, a in enumerate(A * 2):
    L[a] += [i]
before_next = [L[a][bisect.bisect(L[a], i)] for i, a in enumerate(A)]
first_cycle = [None] * N
now = 0
idx = 0
cycle = 0
while True:
    if first_cycle[now] is not None:
        break
    first_cycle[now] = cycle
    now = before_next[now] + 1
    dcycle, now = divmod(now, N)
    cycle += dcycle
cycle2 = cycle
cycle1 = first_cycle[now]
#K cycle目=cycle1+(K-cycle1)%(cycle2-cycle1) cycle目
K2 = cycle1 + (K - cycle1) % (cycle2 - cycle1)
for i in range(N - 1, -1, -1):
    if first_cycle[i] == K2:
        break
ans = []
cnt = [0] * 10
for a in A[i:]:
    if cnt[a] > 0:
        while True:
            cnt[ans.pop()] -= 1
            if cnt[a] == 0:
                break
    else:
        ans += [a]
        cnt[a] += 1
print(' '.join(map(str, ans)))


### FIXED CODE ###

import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(2 * 10**5 + 1)]
for i, a in enumerate(A * 2):
    L[a] += [i]
before_next = [L[a][bisect.bisect(L[a], i)] for i, a in enumerate(A)]
first_cycle = [None] * N
now = 0
idx = 0
cycle = 0
while True:
    if first_cycle[now] is not None:
        break
    first_cycle[now] = cycle
    now = before_next[now] + 1
    dcycle, now = divmod(now, N)
    cycle += dcycle
cycle2 = cycle
cycle1 = first_cycle[now]
#K cycle目=cycle1+(K-cycle1)%(cycle2-cycle1) cycle目
K2 = cycle1 + (K - cycle1) % (cycle2 - cycle1)
if K2:
    f1 = f2 = 0
    for i in range(N - 1, -1, -1):
        if first_cycle[i] == K2 - 1:
            f1 = 1
            break
    for j in range(N - 1, -1, -1):
        if first_cycle[j] == K2:
            f2 = 1
            break
    if f2:
        B = A[j:]
    elif f1:
        B = A[i:] + A
else:
    B = A
ans = []
cnt = [0] * (2 * 10**5 + 1)
for a in B:
    if cnt[a] > 0:
        while True:
            cnt[ans.pop()] -= 1
            if cnt[a] == 0:
                break
    else:
        ans += [a]
        cnt[a] += 1
print(' '.join(map(str, ans)))
a, b = map(int, input())
tap_count = 1
a_count = 0
while tap_count <= b:
  tap_count = tap_count + a - 1
  a_count = a_count + 1
print("{}".format(a_count))

### FIXED CODE ###

a, b = map(int, input().split())
tap_count = 1
a_count = 0
while tap_count < b:
  tap_count = tap_count + a - 1
  a_count = a_count + 1
print("{}".format(a_count))
r = int(input())
print(3r^2)


### FIXED CODE ###

r = int(input())
print(3*r*r)
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()

for i in range (m):
  b,c=map(int,input().split())
  d=0
  flag = 0
  while flag == 0 :
    a[d]=c
    d+=1
    b-=1
    if b!=0 or c <= a[d]:
      flag = 1
    a.sort()
print(sum(a))


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
changer=[]
cl=0
flag=0
for i in range(m):
  b=list(map(int,input().split()))
  changer.append(b)
changer.sort(key=lambda x:x[1],reverse=True)
for i in range(m):
  if flag==1:
    break
  for j in range(cl,min(cl+changer[i][0],n)):
    if a[j]<changer[i][1]:
      a[j]=changer[i][1]
    else:
      flag=1
      break
  cl+=changer[i][0]
print(sum(a))
K = int(input())
ans = [1,2,3,4,5,6,7,8]
num = 9
while(len(ans)<K):
    if str(num)[-1]=="9":
        if str(num)[1:].count("9")==len(str(num)[1:]):
            ans.append(num)
    num += 1

for i in range(K):
    print(ans[i])

### FIXED CODE ###

S = input()
ans = 0
for char in S:
    if char == "+":
        ans += 1
    else:
        ans -= 1
print(ans)
# C - Snack
import math
a,b = map(int,input().split())
print(a*b//math.gcd(a,b))

### FIXED CODE ###

# C - Snack
from fractions import gcd
a,b = map(int,input().split())
print(a*b//gcd(a,b))
import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
        return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        print(v.parents,v.dist)
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
        return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()
a=(int)(input().split())
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=a
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
return ans%(10**9+7)

### FIXED CODE ###

n=input()
a=input().split()
sum=0
for i in range(len(a)):
  a[i]=(int)(a[i])
for i in a:
  sum+=i
ans=0
ans+=(sum**2)
for i in a:
  ans-=i*i
print((ans//2)%(10**9+7))
def toId(i, j):
    return id[min(i, j)][max(i, j)]


visited = [False] * MAXV
calculated = [False] * MAXV
dp = [0] * MAXV


def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for nv in to[v]:
        res = dfs(nv)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res + 1)
    calculated[v] = True
    return dp[v]


a = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    for j in range(N-1):
        a[i][j] -= 1
vid = 0
for i in range(N):
    for j in range(N):
        if i < j:
            id[i][j] = vid
            vid += 1

# プレイヤーiの試合の依存関係の情報をグラフ化
for i in range(N):
    for j in range(N-1):
        a[i][j] = toId(i, a[i][j])
    for j in range(N-2):
        to[a[i][j+1]].append(a[i][j])
ans = 0

for i in range(vid):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, res)
print(ans)


### FIXED CODE ###

N = int(input())
MAXN = 1005
MAXV = MAXN*(MAXN-1)//2
to = [[]for _ in range(MAXV)]
id = [[0]*MAXN for _ in range(MAXN)]


def toId(i, j):
    return id[min(i, j)][max(i, j)]


visited = [False] * MAXV
calculated = [False] * MAXV
dp = [0] * MAXV


def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for nv in to[v]:
        res = dfs(nv)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res + 1)
    calculated[v] = True
    return dp[v]


a = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    for j in range(N-1):
        a[i][j] -= 1
vid = 0
for i in range(N):
    for j in range(N):
        if i < j:
            id[i][j] = vid
            vid += 1

# プレイヤーiの試合の依存関係の情報をグラフ化
for i in range(N):
    for j in range(N-1):
        a[i][j] = toId(i, a[i][j])
    for j in range(N-2):
        to[a[i][j+1]].append(a[i][j])
ans = 0

for i in range(vid):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, res)
print(ans)
from scipy.special import comb

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

if N!=1 and M!=1:
    ans = comb(N,2) + comb(M,2)
elif N==1:
    ans = comb(M,2)
elif M==1:
    ans = comb(N,2)
else:
    ans = 0

print(int(ans))

### FIXED CODE ###

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

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

if N >= 2 and M >= 2:
    ans = cmb(N,2) + cmb(M,2)
elif N <= 1 and M >=2:
    ans = cmb(M,2)
elif M <= 1 and N >=2:
    ans = cmb(N,2)
else:
    ans = 0


print(int(ans))
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
    while a[-1] >= a[-2]:
        a[-1] //= 2
    a.sort()
print(sum(a))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a)

for i in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a, -1 * ((-x) // 2))
print(-sum(a))
n,Y = map(int,input().split())
Y = int(Y / 1000)
ans = [-1,-1,-1]
for x in range(n+1):
    for y in range(n+1):
        if 10*x + 5*y + (n-x-y) == Y and n-x-y => 0:
            ans = [x,y,n-x-y]
print(*ans)

### FIXED CODE ###

n,Y = map(int,input().split())
Y = int(Y / 1000)
ans = [-1,-1,-1]
for x in range(n+1):
    for y in range(n+1):
        if 10*x + 5*y + (n-x-y) == Y and n-x-y >= 0:
            ans = [x,y,n-x-y]
print(*ans)
import math

N, X = [int(n) for n in input().split()]
x = sorted([abs(int(n) - X) for n in input().split()])

if len(x) > 1:
  gcd = math.gcd(x[0], x[1])

  for i in x:
    gcd = math.gcd(gcd, i)
else:
  gcd = x[0]

print(gcd)

### FIXED CODE ###

import fractions

N, X = [int(n) for n in input().split()]
x = sorted([abs(int(n) - X) for n in input().split()])

if len(x) > 1:
  gcd = fractions.gcd(x[0], x[1])
  for i in x:
    gcd = fractions.gcd(gcd, i)
else:
  gcd = x[0]
print(gcd)
n=int(input())
a=list(map(int,input().split()))
ans=1
now=a[0]
start=1
while now==a[start]:
    start+=1
if a[0]<a[start]:#増加
    jugh=1
else:#現象
    jugh=2
#print(start,jugh)
i=start
while i<n:
    if jugh==0:
        while now==a[start]:
            start+=1
        if now<a[start]:#増加
            jugh=1
        else:#現象
            jugh=2
    if jugh==1:
        if a[i-1]>a[i]:
            jugh=0
            ans+=1
            now=a[i]
            start=i+1
            #print(a[i-1],a[i])
                
    else:
        if a[i-1]<a[i]:
            jugh=0
            ans+=1
            now=a[i]
            start=i+1
            #print(a[i-1],a[i])
            
    i+=1   

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=1
now=a[0]
start=1

if n==1:
    print(1)
    exit()

while now==a[start]:
    start+=1
if a[0]<a[start]:#増加
    jugh=1
else:#現象
    jugh=2
#print(start,jugh)
i=start
while i<n:
    if jugh==0:
        while now==a[start]:
            start+=1
        if now<a[start]:#増加
            jugh=1
        else:#現象
            jugh=2
    if jugh==1:
        if a[i-1]>a[i]:
            jugh=0
            ans+=1
            now=a[i]
            start=i+1
            #print(a[i-1],a[i])
                
    else:
        if a[i-1]<a[i]:
            jugh=0
            ans+=1
            now=a[i]
            start=i+1
            #print(a[i-1],a[i])
            
    i+=1   

print(ans)
h,w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
b = [list(map(int, input().split())) for _ in range(h)]
g = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    g[i][j] = abs(a[i][j] - b[i][j])
a = b = 0
m = max(max(x) for x in g)*(h+w)
dp = [[[False]*m for _ in range(w+1)] for _ in range(h+1)]
dp[0][1][0] = True
dp[1][0][0] = True
for i in range(1,h+1):
  for j in range(1,w+1):
    for x in range(m):
      if dp[i-1][j][x] or dp[i][j-1][x]:
        dp[i][j][abs(x-g[i-1][j-1])] |= True
        if x + g[i-1][j-1] < 3000:
            dp[i][j][x+g[i-1][j-1]] |= True
for x in range(m):
  if dp[h][w][x]:
    print(x)
    break


### FIXED CODE ###

def fold(x,m):
    y = 0
    for _ in range(m):
        y |= x&1
        y <<= 1
        x >>= 1
    return x|y

lmi = lambda: list(map(int, input().split()))

h,w = lmi()
a = [lmi() for _ in range(2*h)]
g = [[abs(a[i][j] - a[i+h][j]) for j in range(w)] for i in range(h)]

mask = (1<<12801) - 1

dp = [[0]*(w+1) for _ in range(h+1)]
dp[0][0] = 1
for i in range(h):
  for j in range(w):
    cur,par = g[i][j],dp[i][j]
    pos = (par<<cur)|fold(par,cur)
    pos &= mask
    dp[i+1][j] |= pos
    dp[i][j+1] |= pos
for i in range(12801):
  if dp[-1][-2]&(1<<i):
    print(i)
    break
n = int(raw_input())
a = map(int, raw_input().split())

for i in range(n):
  print "%d" %(a[n-i])

### FIXED CODE ###

n = int(raw_input())
a = map(int, raw_input().split())

for i in range(n):
  print a[n-i-1],
n, k = [int(x) for x in input().split()]
a = [int(x)-1 for x in input().split()]
assert len(a) == n
current = 0
visited = [-1] * n
visited[0] = 0
for i in range(1, k):
  current = a[current]
  if visited[current] == -1:
    visited[current] = i
  else:
    pre = visited[current]
    count = (k - pre) % (i - pre) + pre
    print(visited.index(count)+1)
else:
  print(a[current]+1)


### FIXED CODE ###

n, k = [int(x) for x in input().split()]
a = [int(x)-1 for x in input().split()]
assert len(a) == n
current = 0
visited = [-1] * n
visited[0] = 0
for i in range(1, k):
  current = a[current]
  if visited[current] == -1:
    visited[current] = i
  else:
    pre = visited[current]
    count = (k - pre) % (i - pre) + pre
    print(visited.index(count)+1)
    break
else:
  print(a[current]+1)
N=int(input())
P=list(map(int,input().split()))
s=1
for i in range(1,N):
  if P[i]==min(P[0:i+1])
    s+=1
print(s)

### FIXED CODE ###

N=int(input())
P=list(map(int,input().split()))
s=1
m=P[0]
for i in range(1,N):
  if P[i]<=m:
    m=P[i]
    s+=1
print(s)
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int):
    if N < 10:
        print(n)
        exit()

    n = len(list(str(N)))
    t = sum(map(int, str(N)[0]+'9'*(n-1)))

    al = [t]
    for i in range(max(0, N-10), N+1):
        x = sum(map(int, list(str(i))))
        # print(i, x)
        al.append(x)

    print(max(al)-1)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int):
    sn = str(N)
    if sn[1:] == '9'*(len(sn)-1):
        print(int(sn[0])+9*(len(sn)-1))
    else:
        print(int(sn[0])+9*(len(sn)-1)-1)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()
N = int(input())
cnt = 0
ans = False
for i in range(N):
    a, b = input().split()
    print(a, b)
    if a == b:
        cnt += 1
    else:
        cnt = 0
    if cnt == 3:
        ans True
        break
    print(cnt)
print('Yes' if ans else 'No')



### FIXED CODE ###

N = int(input())
cnt = 0
ans = False
for i in range(N):
    a, b = input().split()
    if a == b:
        cnt += 1
    else:
        cnt = 0
    if cnt == 3:
        ans = True
        break
print('Yes' if ans else 'No')
from collections import deque

H, W = map(int, input().split())
# A = [[2000 for _ in range(W)] for _ in range(H)]
B = deque()
check = [[False for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("#") > 0:
        for w, e in enumerate(a):
            if e == "#":
                B.append((h, w))
                check[h][w] = 0
                # A[h][w] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] == False:
                lx, ly = nx, ny
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(check[lx][ly])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
B = deque()
check = [[H*W for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("#") > 0:
        b = [(h, w) for w, e in enumerate(a) if e == "#"]
        B += b
        for bx, bw in b:
            check[bx][bw] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] > check[x][y] + 1:
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(max(max(c) for c in check))
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

def solve():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    if len(a) > 1:
        for i in range(m-1):
            if a[i+1]-a[i] <= 1:
                return 0
    
    a = a + [n]
    l = [a[0]]
    for i in range(1, m):
        l.append(a[i]-a[i-1]-1)
    l = l + [a[-1]-a[-2]]
    ans = 1
    for i in l:
        ans *= Fib(i+1)

    return ans%1000000007


print(solve())



### FIXED CODE ###

def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

def solve():
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    if m > 1:
        for i in range(m-1):
            if a[i+1]-a[i] <= 1:
                return 0
    elif m == 0:
        return Fib(n+2)%1000000007

    
    a = a + [n]
    l = [a[0]]
    for i in range(1, m):
        l.append(a[i]-a[i-1]-1)
    l = l + [a[-1]-a[-2]]
    ans = 1
    for i in l:
        ans *= Fib(i+1)

    return ans%1000000007


print(solve())
N=int(input())
K=0
for i in N:
    l,r = map(int,input().split())
    K=(r-l+1)+K
print(K)
    

### FIXED CODE ###

N=int(input())
K=0
for i in range(N):
    l,r = map(int,input().split())
    K=(r-l+1)+K
print(K)
import sys
S = list(input())
s = list(set(S))
s.sort()
alfa = list('abcdefghijklmnopqrstuvwxyg')
ans = 0
if(len(s)==len(alfa)):
  print('None')
  sys.exit()
else:
  for i in range(len(s)):
    if(s[i]!=alfa[i]):
      print(alfa[i])
      sys.exit()
  print(alfa[len(s)+1])

### FIXED CODE ###

import sys
S = list(input())
s = list(set(S))
s.sort()
alfa = list('abcdefghijklmnopqrstuvwxyz')
ans = 0
if(len(s)==len(alfa)):
  print('None')
  sys.exit()
else:
  for i in range(len(s)):
    if(s[i]!=alfa[i]):
      print(alfa[i])
      sys.exit()
  print(alfa[len(s)])
A, B, K = map(int, input().split())
cnt = 0
ans = 0
for i in range(1, 101): # 1から100まで
	if(A % i == 0 and B % i == 0):
 		cnt = cnt + 1
 	if(cnt == k):
 		ans = i
print(ans)

### FIXED CODE ###

a,b,c = map(int, input().split())
num = []
for i in range(1, 101):
  if(a % i == 0 and b % i == 0):
    num.append(i)
num.reverse()
print(num[c-1])
n = int(input())
sp = []
for i in range(n):
    sp.append(input().split())
    sp[i].append(i)
    sp[i][1] = int(sp[i][1])
sp = sorted(sp, key = lambda x : x[1], reverse = True)
sp = sorted(sp, key = lambda x : x[0])
fo ri in range(n):
    print(sp[i][2]+1)

### FIXED CODE ###

n = int(input())
sp = []
for i in range(n):
    sp.append(input().split())
    sp[i].append(i)
    sp[i][1] = int(sp[i][1])
sp = sorted(sp, key = lambda x : x[1], reverse = True)
sp = sorted(sp, key = lambda x : x[0])
for i in range(n):
    print(sp[i][2]+1)