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

import heapq
import sys


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


H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [list(input()) for i in range(H)]


def trans(h, w):
    return W*(h) + w


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

G = [[] for i in range(H*W)]
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            for dx, dy in P:
                if 0 <= dx+i < H and 0 <= dy+j < W and S[dx+i][dy+j] == ".":
                    u, v = trans(i, j), trans(dx+i, dy+j)
                    G[u].append((v, 0))
                    G[v].append((u, 0))
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    if S[i][j] == "." and 0 <= dx+i < H and 0 <= dy+j < W and S[dx+i][dy+j] == ".":
                        u, v = trans(i, j), trans(dx+i, dy+j)
                        G[u].append((v, 1))
                        G[v].append((u, 1))

D = [10**10 for i in range(H*W)]
D[trans(ch-1, cw-1)] = 0
que = []
heapq.heapify(que)
heapq.heappush(que, (0, trans(ch-1, cw-1)))

while que:
    cost, v = heapq.heappop(que)
    if D[v] < cost:
        continue
    for node, cost in G[v]:
        if D[node] > D[v] + cost:
            D[node] = D[v] + cost
            heapq.heappush(que, (D[node], node))

ans = D[trans(dh-1, dw-1)]

if ans == 10**10:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import heapq
import sys


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


H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
data = [[0]*W for i in range(H)]

for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == ".":
            data[i][j] = 1
        else:
            data[i][j] = 0


def trans(h, w):
    return W*(h) + w


P = [(0, -1), (0, 1), (1, 0), (-1, 0)]
DXY = []
for i in range(0, 3):
    for j in range(-2, 3):
        if i==0 and j==0:
            pass
        else:
            DXY.append((i,j))
            
G = [[] for i in range(H*W)]
H_L = [i for i in range(H)]
W_L = [i for i in range(W)]
for i in H_L:
    for j in W_L:
        if data[i][j] == 1:
            for dx, dy in P:
                if 0 <= dx+i < H and 0 <= dy+j < W and data[dx+i][dy+j] == 1:
                        u, v = trans(i, j), trans(dx+i, dy+j)
                        G[u].append((v, 0))
                        G[v].append((u, 0))
            for dx, dy in DXY:
                if 0 <= dx+i < H and 0 <= dy+j < W and data[dx+i][dy+j] == 1:
                        u, v = trans(i, j), trans(dx+i, dy+j)
                        G[u].append((v, 1))
                        G[v].append((u, 1))


D = [10**6+100 for i in range(H*W)]
D[trans(ch-1, cw-1)] = 0
que = []
heapq.heapify(que)
heapq.heappush(que, (0, trans(ch-1, cw-1)))

while que:
    cost, v = heapq.heappop(que)
    if D[v] < cost:
        continue
    for node, cost in G[v]:
        if D[node] > D[v] + cost:
            D[node] = D[v] + cost
            heapq.heappush(que, (D[node], node))

ans = D[trans(dh-1, dw-1)]

if ans == 10**6+100:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

input()
s = input()
i = s.find('ABC')
n = 0
while i != -1:
  i = s.find('ABC'[i+3:])
print(n)


### FIXED CODE ###

input()
s = input()
n = 0
i = 0
while i != -1:
  i = s.find('ABC')
  s = s[i+3:]
  n += 1
print(n-1)
### BUGGY CODE ###

loop = input()
a = map(int, input().split())
cnt = 0
 
while(1):
  flg = 0
  for i in a:
    if(i%2 == 1):
      flg = 1
      
  if(flg == 0):
    a = map(lambda x:x/2, a)
    cnt += 1
  else:
    break
 
print(cnt)

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

N, K = list(map(int, input().split()))
ab = []


ki = []

for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []

for i in range(N-1):
    a, b = (list(map(int, input().split())))
    ki[a - 1]["eda"].append([b - 1])
    ki[b - 1]["eda"].append([a - 1])

def P(m ,n):
    if m <= 0 or n <= 0:
        return 0
    else:
        num = 1
        for i in range(n):
            num *= m-i
        return num

def saiki(i, base, ki):
    num = 1
    eda_num = len(ki[i]["eda"])-1
    if eda_num == 0:
        return num
    num *= P(K-2, eda_num)

    for edge in ki[i]["eda"]:
        if edge[0] != base:
            num *= saiki(edge[0], i, ki)

    num = num % 1000000007
    return num

total_num = K
if len(ki[0]["eda"]) != 0:
    total_num *= P(K-1, len(ki[0]["eda"]))
    for edge in ki[0]["eda"]:
        total_num *= saiki(edge[0], 0, ki)
        total_num = total_num % 1000000007
        if total_num == 0:
            break

print(total_num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

S = input().strip()
l = len(S)
dic = {0:[-1]}
dp = [[0 for _ in range(2019)] for i in range(l)]
ans = 0
mod = 0
for i in range(0, l):
    s = int(S[i:])
    mod = s % 2019
    if mod in dic:
        dic[mod].append(i)
    else:
        dic[mod] = [i]

for key, val in dic.items():
    v_len = len(val)
    ans += (v_len * (v_len -1))// 2

print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

S = input().strip()
l = len(S)
dic = {0:[-1]}
ans = 0
base = 1
mod = 0
for i in range(0, l):
    base = (10 * base) % 2019
    s = base * int(S[l-1-i]) + mod
    mod = s % 2019
    if mod in dic:
        dic[mod].append(i)
    else:
        dic[mod] = [i]

for key, val in dic.items():
    v_len = len(val)
    ans += (v_len * (v_len -1))// 2

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

N, C, K = map(int, input().split())
T = [0 for _ in range(N)]
for i in range(N):
    T[i] = int(input())
T = sorted(T)

ans = 0
while T != []:
    cnt = 0
    for i in range(len(T)):
        cnt += 1
        if T[i] - T[0] > K or cnt > C:
            T = T[i:]
            ans += 1
            break
        if i == len(T)-1:
            ans += 1
            T = []
print(ans)


### FIXED CODE ###

N, C, K = map(int, input().split())
T = [0 for _ in range(N)]
for i in range(N):
    T[i] = int(input())
T = sorted(T)

flag = 0
cnt = 0
ans = 0
for i in range(len(T)):
    time = T[i] - T[flag]
    cnt += 1
    if time > K or cnt > C:
        flag = i
        cnt = 1
        ans += 1
print(ans + 1)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
from collections import Counter
def resolve():
    n=int(input())
    l=[input() for i in range(n)]
    l.sort()
    setl = list(set(l))
    setl.sort()
    cntl=[]
    prev=l[0]
    cnt=0
    for j in range(len(l)):
        if l[j]!=prev:
            cntl.append(cnt)
            prev=l[j]
            cnt=1
            if j==n-1:
                cntl.append(cnt)
        else:
            cnt+=1
            if j==n-1:
                cntl.append(cnt)
    for i in range(len(setl)):
        if cntl[i]==max(cntl):
            print(setl[i])
resolve()

### FIXED CODE ###

from collections import Counter
def resolve():
    n=int(input())
    l=[input() for i in range(n)]
    c=Counter(l)
    maxl=[]
    cntmax=max(c.values())
    for name,kazu in c.items():
        if kazu==cntmax:
            maxl.append(name)
    maxl.sort()
    for i in maxl:
        print(i)
resolve()
### BUGGY CODE ###

H,W=map(int, input().split())
S=[input() for _ in range(H)]

U=[[-1]*W for _ in range(H)]
D=[[-1]*W for _ in range(H)]
L=[[-1]*W for _ in range(H)]
R=[[-1]*W for _ in range(H)]

def u(i,j):
    if S[i][j]=='#':
        U[i][j]==-2
    elif i==0:
        U[i][j]=0
    elif U[i-1][j]==-1:
        a=0
        for k in range(i-1,-1,-1):
            if S[k][j]=='#': break
            else: a+=1
        U[i][j]=a
    elif U[i-1][j]==-2:
        U[i][j]=0
    else:
        U[i][j]=U[i-1][j]+1

def d(i,j):
    if S[i][j]=='#':
        D[i][j]==-2
    elif i==H-1:
        D[i][j]=0
    elif D[i+1][j]==-1:
        a=0
        for k in range(i+1,H):
            if S[k][j]=='#': break
            else: a+=1
        D[i][j]=a
    elif D[i+1][j]==-2:
        D[i][j]=0
    else:
        D[i][j]=D[i+1][j]+1

def l(i,j):
    if S[i][j]=='#':
        L[i][j]==-2
    elif j==0:
        L[i][j]=0
    elif L[i][j-1]==-1:
        a=0
        for k in range(j-1,-1,-1):
            if S[i][k]=='#': break
            else: a+=1
        L[i][j]=a
    elif L[i][j-1]==-2:
        L[i][j]=0
    else:
        L[i][j]=L[i][j-1]+1

def r(i,j):
    if S[i][j]=='#':
        R[i][j]==-2
    elif j==W-1:
        R[i][j]=0
    elif R[i][j+1]==-1:
        a=0
        for k in range(j+1,W):
            if S[i][k]=='#': break
            else: a+=1
        R[i][j]=a
    elif R[i][j+1]==-2:
        R[i][j]=0
    else:
        R[i][j]=R[i][j+1]+1

def udlr(i,j):
    if S[i][j]=='#':
        U[i][j]=D[i][j]=L[i][j]=R[i][j]=-2
        return 0
    else:
        if U[i][j]==-1:
            u(i,j)
        if D[i][j]==-1:
            d(i,j)
        if L[i][j]==-1:
            l(i,j)
        if R[i][j]==-1:
            r(i,j)
        return U[i][j]+D[i][j]+L[i][j]+R[i][j]+1

x=0
for i in range(H):
    for j in range(W):
        x=max(x,max(x,udlr(i,j)))
print(x)



### FIXED CODE ###

H,W = map(int,input().split())
G=[input() for _ in range(H)]
A_u=[[0 for _ in range(W)] for _ in range(H)]
A_d=[[0 for _ in range(W)] for _ in range(H)]
A_r=[[0 for _ in range(W)] for _ in range(H)]
A_l=[[0 for _ in range(W)] for _ in range(H)]
for h in range(H):
  for w in range(1,W):
    if G[h][w-1] == '.':
      A_r[h][w] = A_r[h][w-1]+1
  for w in range(W-2,-1,-1):
    if G[h][w+1] == '.':
      A_l[h][w] = A_l[h][w+1]+1
for w in range(W):
  for h in range(1,H):
    if G[h-1][w] == '.':
      A_d[h][w] = A_d[h-1][w]+1
  for h in range(H-2,-1,-1):
    if G[h+1][w] == '.':
      A_u[h][w] = A_u[h+1][w]+1
ans=0
for h in range(H):
  for w in range(W):
    if G[h][w] == '.':
      ans = max(ans,A_r[h][w]+A_l[h][w]+A_d[h][w]+A_u[h][w]+1)
print(ans)
### BUGGY CODE ###

def Main(S, Q, queries):
    ans = list(S)
    flipped = False
    T1 = 0
    for q in queries:
        if int(q[0]) == 1:
            if not flipped:
                flipped = True
            else:
                flipped = False
            continue
        else:
            if int(q[1]) == 1:
                if flipped:
                    ans.append(q[2])
                else:
                    ans.insert(0, q[2])
            else:
                if flipped:
                    ans.insert(0, q[2])
                else:
                    ans.append(q[2])
    if flipped:
        ans.reverse()
    return "".join(ans)
        

def main():
    S = str(input())
    Q = int(input())
    queries = []
    for i in range(Q):
        queries.append(list(map(str, input().split())))
    print(Main(S, Q, queries))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def Main(S, Q, queries):
    right = S
    left = ""
    flipped = False
    T1 = 0
    for q in queries:
        if int(q[0]) == 1:
            if not flipped:
                flipped = True
            else:
                flipped = False
            continue
        else:
            if int(q[1]) == 1:
                if flipped:
                    right += q[2]
                else:
                    left += q[2]
            else:
                if not flipped:
                    right += q[2]
                else:
                    left += q[2]
    le = list(left)
    le.reverse()
    left = "".join(le)
    ans = left + right
    if flipped:
        l = list(ans)
        l.reverse()
        ans = "".join(l)
    return ans
        

def main():
    S = str(input())
    Q = int(input())
    queries = []
    for i in range(Q):
        queries.append(list(map(str, input().split())))
    print(Main(S, Q, queries))

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

H,W,M = map(int, input().split())

squares = []
for i in range(H):
    arr = []
    for j in range(W):
        arr.append(0)
    squares.append(arr)

for i in range(M):
    hi, wi = map(int, input().split())
    squares[hi-1][wi-1] = 1

row_sums = []
for i in range(H):
    row_sums.append(sum(squares[i]))

col_sums = []
for j in range(W):
    sum = 0
    for i in range(H):
        sum += squares[i][j]
    col_sums.append(sum)

row_max = max(row_sums)
col_max = max(col_sums)

row_indexes = []
for i in range(H):
    if row_sums[i] == row_max:
        row_indexes.append(i)

col_indexes = []
for j in range(W):
    if col_sums[j] == col_max:
        col_indexes.append(j)

for i in row_indexes:
    for j in col_indexes:
        if squares[i][j] == 0:
            print(row_max + col_max)
            exit()

print(row_max + col_max - 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H,W,M=map(int,input().split())
nh=[0]*H
nw=[0]*W
boms=set()
for _ in range(M):
    h,w=map(int,input().split())
    nh[h-1] += 1
    nw[w-1] += 1
    boms.add((h-1, w-1))

maxh = max(nh)
maxw = max(nw)

i_indexes=[]
for i in range(H):
    if nh[i] == maxh:
        i_indexes.append(i)
j_indexes=[]
for j in range(W):
    if nw[j] == maxw:
        j_indexes.append(j)

for i in i_indexes:
    for j in j_indexes:
        if (i,j) in boms:
            continue
        print(maxh + maxw)
        exit()
print(maxh + maxw - 1)
### BUGGY CODE ###

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

for i in range(1,n+1):
  print(a.index(i)+1,end=" "),


### FIXED CODE ###

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

for i,name in enumerate(a):
  ans[name-1]=i+1

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

import sys
input = sys.stdin.readline

mod=10**9+7
n,k=map(int,input().split())
N=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  N[a-1]+=[b-1]
  N[b-1]+=[a-1]
Chk=[False]*n
S=[0]
Chk[0]=True
ans=k
while S:
  ss=S.pop()
  for sss in N[ss]:
    if Chk[sss]==True:
      continue
    else:
      ct=1
      for ssss in N[ss]:
        if Chk[ssss]==True:
          ct+=1
      ans=(ans*max(k-ct,0))%mod
      Chk[sss]=True
      S.append(sss)
print(ans%mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline

mod=10**9+7
n,k=map(int,input().split())
N=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  N[a-1]+=[b-1]
  N[b-1]+=[a-1]
Chk=[0]*n
S=[0]
Chk[0]=1
ans=k
while S:
  ss=S.pop()
  for sss in N[ss]:
    if Chk[sss]>0:
      continue
    else:
      ans=(ans*max(k-Chk[ss],0))%mod
      Chk[ss]+=1
      Chk[sss]=2
      S.append(sss)
print(ans%mod)
### BUGGY CODE ###

N = int(input())

memo={}
for h in range(1, 3501):
    for n in range(1, 3501):
        if (h,n) not in memo:
            memo[n,h] = True
            a = 4 * h * n - h * N - n * N
            if a == 0:
                break
            w = int((h * n * N) / a)
            if w > 0 and 4 / N == 1 / h + 1 / n + 1 / w:
                print(h, n, w)
                exit()
        else:
            continue

### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        a = 4 * h * n - h * N - n * N
        if a == 0:
            break
        w = int((h * n * N) / a)
        if w > 0 and 4 / N == 1 / h + 1 / n + 1 / w:
            print(h, n, w)
            exit()
### BUGGY CODE ###

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
from fractions import gcd
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	AB = []
	D = defaultdict(int)
	DJ = defaultdict(int)
	d0x = 0
	dx0 = 0
	d00 = 0
	for i in range(N):
		A, B = getlist()
		if A == 0 and B == 0:
			d00 += 1
		elif A == 0:
			dx0 += 1
		elif B == 0:
			d0x += 1
		else:
			GCD = gcd(A, B)
			a = int(A // GCD)
			b = int(B // GCD)
			if a < 0:
				a = -a
				b = -b
			AB.append([a, b])
			D[a * (10 ** 19) + b] += 1
			DJ[a * (10 ** 19) + b] = 1


	ans = 1

	for a, b in AB:
		a2 = b; b2 = -a
		if a2 < 0:
			a2 = -a2; b2 = -b2
		if DJ[a * (10 ** 19) + b] >= 0 and DJ[a2 * (10 ** 19) + b2] >= 0:
			DJ[a * (10 ** 19) + b] = -1
			DJ[a2 * (10 ** 19) + b2] = -1
			X = D[a * (10 ** 19) + b]
			Y = D[a2 * (10 ** 19) + b2]
			ans *= pow(2, X, con) + pow(2, Y, con) - 1
			ans %= con

	ans *= (pow(2, d0x, con) + pow(2, dx0, con)) - 1
	ans += d00
	ans %= con

	if ans == 0:
		print(10 ** 9  + 6)
	else:
		print(ans - 1)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
from fractions import gcd
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	AB = []
	D = defaultdict(int)
	DJ = defaultdict(int)
	d0x = 0
	dx0 = 0
	d00 = 0
	for i in range(N):
		A, B = getlist()
		if A == 0 and B == 0:
			d00 += 1
		elif A == 0:
			dx0 += 1
		elif B == 0:
			d0x += 1
		else:
			GCD = gcd(A, B)
			a = int(A // GCD)
			b = int(B // GCD)
			if a < 0:
				a = -a
				b = -b
			AB.append([a, b])
			D[a * (10 ** 19) + b] += 1
			DJ[a * (10 ** 19) + b] = 1

	ans = 1

	for a, b in AB:
		a2 = b; b2 = -a
		if a2 < 0:
			a2 = -a2; b2 = -b2
		if DJ[a * (10 ** 19) + b] >= 0 and DJ[a2 * (10 ** 19) + b2] >= 0:
			DJ[a * (10 ** 19) + b] = -1
			DJ[a2 * (10 ** 19) + b2] = -1
			X = D[a * (10 ** 19) + b]
			Y = D[a2 * (10 ** 19) + b2]
			ans *= pow(2, X, con) + pow(2, Y, con) - 1
			ans %= con

	ans *= (pow(2, d0x, con) + pow(2, dx0, con)) - 1
	ans += d00
	ans %= con

	if ans == 0:
		print(10 ** 9  + 6)
	else:
		print(ans - 1)

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

from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))
anstable = [0] * (10 ** 6 + 1)
d = defaultdict(int)
for i in a:
    d[i] += 1

u = []
for i, v in d.items():
    if v == 1:
        u.append(i)

for i in a:
    for j in range(i * 2, 10 ** 6 + 1, i):
        anstable[j] += 1

cnt = 0
for i in u:
    if anstable[i] == 0:
        cnt += 1

print(cnt)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))
anstable = [0] * (10 ** 6 + 1)
d = defaultdict(int)
for i in a:
    d[i] += 1

u = []
for i, v in d.items():
    if v == 1:
        u.append(i)
a = set(a)
for i in a:
    for j in range(i * 2, 10 ** 6 + 1, i):
        anstable[j] += 1

cnt = 0
for i in u:
    if anstable[i] == 0:
        cnt += 1

print(cnt)
### BUGGY CODE ###

N=int(input())
a=[]
for i in range(1,N+1):
    if N%i==0:
        x=i+N//i
        a.append(x)
b=min(a)
print(b-2)

### FIXED CODE ###

N=int(input())
a=[]
for i in range(1,int(N**(1/2)+1)):
    if N%i==0:
        x=i+N//i
        a.append(x)
b=min(a)
print(b-2)
### BUGGY CODE ###

H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

dp = [[0 for _ in range(N+1)] for _ in range(H+1)]

for h in range(1,H+1):
    dp[h][0] = 10**9

for n in range(1,N+1):
    for h in range(H+1):
        if h >= AB[n-1][0]:
            dp[h][n] = min(dp[h-AB[n-1][0]][n]+AB[n-1][1] , dp[h][n-1])
        else:
            dp[h][n] = dp[h][n-1]

# for i in range(H+1):
#     print(*dp[i])
        
ans = dp[H][N]
for n in range(N):
    for h in range(H):
        if (H-AB[n][0])<=h:
            ans = min(ans,dp[h][N]+AB[n][1])

print(ans)

### FIXED CODE ###

H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

dp = [[0 for _ in range(N+1)] for _ in range(H+1)]

for h in range(1,H+1):
    dp[h][0] = 10**9

for n in range(1,N+1):
    for h in range(H+1):
        if h >= AB[n-1][0]:
            dp[h][n] = min(dp[h-AB[n-1][0]][n]+AB[n-1][1] , dp[h][n-1])
        else:
            dp[h][n] = dp[h][n-1]

# for i in range(H+1):
#     print(*dp[i])
        
ans = dp[H][N]
for n in range(N):
    for h in range(H):
        if (H-AB[n][0])<=h:
            ans = min(ans,dp[h][N]+AB[n][1])

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

import numpy as np
n = int(input())
d = [int(i) for i in input().split(" ")]
uni = np.unique(d)
co = [d.count(i) for i in uni]
tm = 0
for i in range(n):
    tm += co[i]
    if tm == n//2:
        print(uni[i+1]-uni[i])
        break
    if tm > n//2:
        print(0)
        break


### FIXED CODE ###

import numpy as np
n = int(input())
d = [int(i) for i in input().split(" ")]
d = sorted(d)

if d[n//2] == d[n//2-1]:
    print(0)
else:
    print(d[n//2] - d[n//2-1])
### BUGGY CODE ###

import sys
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
maxmatch=n*(n-1)
day=0

match=[0]*(n+1)

while True:
  day+=1
  check=[True]*n
  for i in range(n):
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        match[n]+=2
        check[i]=False
        check[vs]=False
      
    if i==n-1:
      if not False in check:
        print(-1)
        sys.exit()
  if match[n]==maxmatch:
    break
        
print(day)


### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)