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

#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
md = pow(10,9) + 7

cnt_memo = [0]*(K+1)
cnt_R_memo = [0]*(K+1)

def main():
    ret = 0
    for k in range(1,K+1):
        cnt_R_memo[k]=pow(K//k,N)%md
    for k in range(K,0,-1):
        cnt_memo[k]=(cnt_R_memo[k] - sum(cnt_memo[2*k::k]))%md
        ret += (cnt_memo[k]*k)%md
    print(ret%md)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
md = pow(10,9) + 7

cnt_memo = [0]*(K+1)
cnt_R_memo = [0]*(K+1)

def main():
    ret = 0
    for k in range(1,K+1):
        cnt_R_memo[k]=pow(K//k,N,md)
    for k in range(K,0,-1):
        cnt_memo[k]=(cnt_R_memo[k] - sum(cnt_memo[2*k::k]))%md
        ret += (cnt_memo[k]*k)%md
    print(ret%md)

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

# あらかじめ全ての区間における答えを求めておく
# 累積和が使える。
# p,qの値に関しての2次元座標系で考えると、値が存在するマスは限られてる

n, m, q = map(int, input().split())
ll = [[0, 0] for i in range(m)]
p = [[0, 0] for i in range(q)]
for i in range(m):
    ll[i][0], ll[i][1] = map(int, input().split())
for i in range(q):
    p[i][0], p[i][1] = map(int, input().split())

sum = [[0 for i in range(n)] for i in range(n)]
for j in range(m):
    y = ll[j][0]-1
    x = ll[j][1]-1
    sum[y][x] += 1

for i in range(q):
    ans = 0
    for j in range(p[i][0]-1, p[i][1]):
        for k in range(p[i][0]-1, p[i][1]):
            ans += sum[k][j]
    print(ans)


### FIXED CODE ###

# あらかじめ全ての区間における答えを求めておく
# 累積和が使える。
# 2次元累積和に関しては、下記のサイトを参照。
# https://paiza.hatenablog.com/entry/2014/05/28/もし女子大生プログラマに『アルゴリズム』を図
# p,qの値に関しての2次元座標系で考えると、値が存在するマスは限られてる
#
#
n, m, q = map(int, input().split())
ll = [[0, 0] for i in range(m)]
p = [[0, 0] for i in range(q)]
for i in range(m):
    ll[i][0], ll[i][1] = map(int, input().split())
for i in range(q):
    p[i][0], p[i][1] = map(int, input().split())
# for i in range(m):
#     print(ll[i])
# for i in range(q):
#     print(p[i])
sum = [[0 for i in range(n)] for i in range(n)]
# sum上でlをy成分＝行、rをx成分=列とする。
# 各区間の値を取り込み
for j in range(m):
    x = ll[j][0]-1
    y = ll[j][1]-1
    sum[y][x] += 1
# 2次元累積和の計算
# for j in range(n):
#     print(sum[j])
# print('-'*30)
for i in range(n):
    for j in range(1, n):
        sum[i][j] += sum[i][j-1]
for i in range(n):
    for j in range(1, n):
        sum[j][i] += sum[j-1][i]
# ans = [[0 for i in range(n)] for i in range(n)]
# for i in range(n):
#    for j in range(i, n):
#        for i2 in range(i, j+1):
#            for j2 in range(i, j+1):
#                ans[i][j] += sum[j2][i2]
# for j in range(n):
#     print(sum[j])


for i in range(q):
    x = p[i][0]-1
    y = p[i][1]-1
    if x != 0:
        print(sum[y][y] - sum[y][x-1] - sum[x-1][y]+sum[x-1][x-1])
    else:
        print(sum[y][y])
### BUGGY CODE ###

N = int(input())
line = list(map(int,input().split()))
a = 0
p = []
for i in range(N):
    p.append(line[i])
    if  min(p) >= line[i]:
       a += 1

print(a)

### FIXED CODE ###

N = int(input())
line = list(map(int,input().split()))
a = 1
m = line[0]
for i in range(N-1):
    if m >= line[i]:
        m = line[i]

    if m >= line[i+1]:
       a += 1

print(a)
### BUGGY CODE ###

input()
ns = [n for n in input()]
 
scores = 0
first = []
second = []
third = []
third_nums = None
 
for i in range(len(ns) - 2):
  if i in first:
    continue
  else:
    first.append(i)
  for j in range(i+1, len(ns) - 1):
    if ''.join([ns[i], ns[j]]) in second:
      continue
    else:
      second.append(''.join([ns[i], ns[j]]))
      third_nums = set(ns[j+1:])
      scores += len(third_nums)
      
print(scores)

### FIXED CODE ###

input()
ns = [n for n in input()]
 
scores = 0
first = []
second = []
third = []
third_nums = None
 
for i in range(len(ns) - 2):
  if ns[i] in first:
    continue
  else:
    first.append(ns[i])
  for j in range(i+1, len(ns) - 1):
    if ''.join([ns[i], ns[j]]) in second:
      continue
    else:
      second.append(''.join([ns[i], ns[j]]))
      third_nums = set(ns[j+1:])
      scores += len(third_nums)
      
print(scores)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc = sorted(bc, key=lambda x:x[1], reverse=True)
for [b,c] in bc:
    if c < a[0]:
        break
    for i in range(b):
        if c < a[i]:
            break
        a[i] = c
    a = a[b:] + a[0:b]
print(sum(a))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
### BUGGY CODE ###

S = input()
Q = int(input())
T = [0] * Q
F = [0] * Q
C = [0] * Q
for i in range(Q):
  inp = input()
  if len(inp) == 1:
    S = S[::-1]
  else:
    T[i], F[i], C[i] = inp.split()
    if int(F[i]) == 1:
      S = C[i] + S
    else:
      S = S + C[i]

print(S)

### FIXED CODE ###

S = input()
Q = int(input())
num_rev = 0
S_front = [""] * Q
S_back = [""] * Q
 
for i in range(Q):
  inp = input()
  if len(inp) == 1:
    num_rev += 1
  else:
    T, F, C = inp.split()
    if ((num_rev % 2 == 0) and int(F) == 1) or ((num_rev % 2 == 1) and int(F) == 2):
      S_front[i] = C
    else:
      S_back[i] = C

S = "".join(S_front)[::-1] + S + "".join(S_back)
if num_rev % 2 == 0:
  print(S)
else:
  print(S[::-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
dic = {}
cnt = 0

for i in range(N):
	s = str(sorted(input()))
	if (s in dic):
		cnt += dic[s]
		dic[s] += 1
	else:
		dic[s] = 1

print(cnt)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
dic = {}
cnt = 0

for i in range(N):
	s = str(sorted(input()))
	if (s in dic):
		cnt += dic[s]
		dic[s] += 1
	else:
		dic[s] = 1

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

from heapq import heappop,heappush

N=int(input())
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append([x,i])
    Y.append([y,i])
inf=float("inf")

X.sort()
Y.sort()
data=[[] for i in range(N)]
for i in range(1,N):
    x1,num1=X[i-1]
    x2,num2=X[i]
    data[num1].append([num2,x2-x1])
    data[num2].append([num1,x2-x1])
    y1,num1=Y[i-1]
    y2,num2=Y[i]
    data[num1].append([num2,y2-y1])
    data[num2].append([num1,y2-y1])

que=[[0,0]]
flag=[inf]*N
ans=0

while que:
    l,u=heappop(que)
    if flag[u]!=inf:
        continue
    else:
        flag[u]=l
        ans+=l
        for v,y in data[u]:
            if flag[v]!=inf:
                continue
            else:
                heappush(que,[y,v])
print(ans)

### FIXED CODE ###

from heapq import heappush,heappop
n=int(input())
xy=[]
yx=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=[[0,0] for i in range(n)]
for i in range(n):
    x,y,a=xy[i]
    data[a][0]=i
    y,x,a=yx[i]
    data[a][1]=i
ans=0
que=[[0,0]]
flag=[0]*n
count=0
while count<=n:
    l,a=heappop(que)
    if flag[a]==1:
        continue
    ans+=l
    flag[a]=1
    count+=1
    if count==n:
        break
    b,c=data[a]
    xb=xy[b][0]
    yc=yx[c][0]
    if 1<=b<=n-2:
        xd,yd,d=xy[b-1]
        xe,ye,e=xy[b+1]
        if flag[d]==0:
            heappush(que,[abs(xd-xb),d])
        if flag[e]==0:
            heappush(que,[abs(xe-xb),e])
    elif b==0:
        xe,ye,e=xy[1]
        if flag[e]==0:
            heappush(que,[abs(xb-xe),e])
    else:
        xd,yd,d=xy[n-2]
        if flag[d]==0:
            heappush(que,[abs(xb-xd),d])
    if 1<=c<=n-2:
        yg,xg,g=yx[c+1]
        yf,xf,f=yx[c-1]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    elif c==0:
        yg,xg,g=yx[1]
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    else:
        yf,xf,f=yx[n-2]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
print(ans)
### BUGGY CODE ###

import numpy as np

N, W = map(int, input().split())
dp = np.full((N + 1, W + 1), -np.inf, dtype=np.int64)
dp[0][0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W + 1):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if j + w <= W:
            dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v)
print(max(dp[-1]))


### FIXED CODE ###

import numpy as np


n, capacity = map(int, input().split())
dp = np.zeros(capacity + 1, dtype=np.int64)
for _ in range(n):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp[-1])
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
  b = int(input())
  if b in a:
    del a[a.index(b)]
  else:
    a.append(b)
print(len(a))

### FIXED CODE ###

N = int(input())
a =set([])
for i in range(N):
  b = int(input())
  if b in a:
    a.remove(b)
  else:
    a.add(b)
print(len(a))
### BUGGY CODE ###

l1=[]
l2=[]
n,k=map(int,input().split())
for i in range(n):
  l1.append(input().split())
for j in range(n):
  for l in range(int(l1[j][1])):
    l2.append(int(l1[j][0]))
l2.sort()
print(l2[k-1])

### FIXED CODE ###

l1=[]
ret=0
c=0
n,k=map(int,input().split())
for i in range(n):
  l1.append(input().split())
num=[0]*(10**5)

for j in range(n):
  num[int(l1[j][0])-1]+=int(l1[j][1])
#print(num)
for l in range(10**5):
  if num[l]>=k:
    print(l+1)
    break
  k-=num[l]
### BUGGY CODE ###

(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
t=[-1]*n
def r(x):
 while t[x]>=0:x=t[x]
 return x
def u(L):
 x,y=map(r,L)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
d={}
for l in q:u(l)
i=c=0;b=[];k=(n+~m)*2
for v in a:R=r(i);d[R]=d.get(R,[])+[v];i+=1
print(k<1and'0'or k>n and'Impossible'or exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

### FIXED CODE ###

#!/usr/bin/env python3
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

(n, m), a, *q = [[*map(int,o.split())] for o in open(0)]
UF = UnionFind(n)
k = (n - m - 1) * 2
if k > n:
    exit(print("Impossible"))
if not k:
    exit(print(0))

for c, f in q:
    UF.union(c, f)

from collections import*
d = defaultdict(list)
for e, i in enumerate(a):
    d[UF.find(e)] += i,

ans, b = 0, []
for r, p in d.items():
    p.sort()
    ans += p.pop(0)
    b += p
    k -= 1
b.sort()
print(ans + sum(b[:k]))
### BUGGY CODE ###

n, m = map(int, input().split())
x = []
y = []
ac = 0
wa = 0
for i in range(m):
   p, s = map(str, input().split())
   p = int(p)
   if (s == 'AC' and [p, s] not in y):
      y.append([p, s])
      x.append(s)
   elif (s == 'WA' and [p, 'AC'] not in y):
      y.append([p, s])
      x.append(s)
print(x.count('AC'), x.count('WA'))


### FIXED CODE ###

N, M = map(int, input().split())

ac = [False] * N
wa = [0] * N
for _ in range(M):
   p, S = input().split()
   p = int(p) - 1
   if (S == 'AC'):
      ac[p] = True
   else:
      if not ac[p]:
         wa[p] += 1

a = 0
b = 0
for i in range(N):
   if ac[i]:
      a += 1
      b += wa[i]
print(*[a, b])
### BUGGY CODE ###

n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  #print(a,b)
  if a != b:
    if la < lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = []
cnt = [0 for _ in range(n)]
for i in range(n):
  I = int(i)
  while I != pre[I]:
    I = pre[I]
  root.append(I)
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))

### FIXED CODE ###

n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  #print(a,b)
  if a != b:
    if la > lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = [10**6 for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if root[i] < 10**6:
    cnt[root[i]] += 1
    continue
  I = int(i)
  J = [I]
  while I != pre[I]:
    I = pre[I]
    J.append(I)
  for x in J:
    root[x] = I
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,MOD = [int(i) for i in readline().split()]

SIZE=3001; #MOD=10**9+7 #998244353 #ここを変更する

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0


"""
make the table of Sterling numbers of the second kind
Sterling[ball][box]
"""
SIZE = n
Sterling2 = [[0]*(SIZE+1) for _ in range(SIZE+1)]
Sterling2[0][0] = Sterling2[1][1] = 1
for i in range(2,SIZE+1):
    for k in range(1,i+1):
        Sterling2[i][k] = (Sterling2[i-1][k-1] + k*Sterling2[i-1][k])%MOD





SIZE = n
f = [[0]*(SIZE+1) for _ in range(SIZE+1)]
f[0][0] = 1
for i in range(1,SIZE+1):
    for k in range(i+1):
        f[i][k] = (f[i-1][k] + f[i-1][k-1] + k*f[i-1][k])%MOD

#print(f)

def size(s):
    res = 0
    for b in range(n+1):
        res += f[s][b]*pow(2,b*(n-s),MOD)
    return res*pow(2,pow(2,n-s,MOD-1),MOD)%MOD

#for i in range(n+1):
#    print(size(i))

ans = 0
sgn = 1
for j in range(n+1):
    ans += sgn*choose(n,j)*size(j)
    ans %= MOD
    sgn *= -1

print(ans)








### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,MOD = [int(i) for i in readline().split()]

SIZE=3001; #MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE # fac[j] = j! mod MOD
finv = [0]*SIZE# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0


"""
make the table of Sterling numbers of the second kind
Sterling[ball][box]

SIZE = n
Sterling2 = [[0]*(SIZE+1) for _ in range(SIZE+1)]
Sterling2[0][0] = Sterling2[1][1] = 1
for i in range(2,SIZE+1):
    for k in range(1,i+1):
        Sterling2[i][k] = (Sterling2[i-1][k-1] + k*Sterling2[i-1][k])%MOD
"""





SIZE = n+1
f = [[0]*(SIZE) for _ in range(SIZE)]
f[0][0] = 1
for i in range(1,SIZE):
    f[i][0] = 1
    for k in range(1,i+1):
        f[i][k] = (f[i-1][k] + f[i-1][k-1] + k*f[i-1][k])%MOD

#print(f)

#pow(2,n-s,MOD-1)
pp = [1]*SIZE
for i in range(1,SIZE):
    pp[i] = 2*pp[i-1]%(MOD-1)

def size(s):
    """
    for b in range(n+1):
        res += f[s][b]*pow(2,b*(n-s),MOD)
    """
    res = 0
    p = 1
    e = pow(2,(n-s),MOD)
    for b in range(SIZE):
        res += f[s][b]*p
        p *= e
        p %= MOD
    return res*pow(2,pp[n-s],MOD)%MOD

#for i in range(n+1):
#    print(size(i))

ans = 0
sgn = 1
for j in range(n+1):
    ans += sgn*choose(n,j)*size(j)
    ans %= MOD
    sgn *= -1

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

a = int(input())
min_steps=a
if a==2:
    print(1)
elif a==3:
    print(2)
else:
    for i in range(2, int(a/2)+1):
            if a%i==0:
                b=i+int(a/i)-2
                if b<min_steps:
                    min_steps=b
    print(min_steps)


### FIXED CODE ###

a = int(input())
min_steps=a
if a==2:
    print(1)
elif a==3:
    print(2)
else:
    j=2
    while(1):
        if j*j>=a:
            break
        else:
            j+=1

    for i in range(2, j+1):
            if a%i==0:
                b=i+int(a/i)-2
                if b<min_steps:
                    min_steps=b
    if (min_steps==a):
        min_steps-=1
    print(min_steps)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())

edges = [set() for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    edges[u-1].add(v-1)

S, T = map(int, input().split())
S -= 1
T -= 1


step2 = [set() for _ in range(N)]

for u in range(N):
    for v in edges[u]:
        step2[u] |= edges[v]

step3 = [set() for _ in range(N)]

for u in range(N):
    for v in edges[u]:
        step3[u] |= step2[v]

cost = [-1 for _ in range(N)]
cost[S] = 0

q = []

for v in step3[S]:
    heapq.heappush(q, (1, v))

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for v in step3[u]:
        heapq.heappush(q, (c+1, v))

print(cost[T])


### FIXED CODE ###

import heapq
N, M = map(int, input().split())

edges = [set() for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    edges[u-1].add(v-1)

S, T = map(int, input().split())
S -= 1
T -= 1

cost = [-1 for _ in range(N)]
q = []
heapq.heappush(q, (0, S))

step1memo = set()
step2memo = set()
step3memo = set()

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for u1 in edges[u]:
        if u1 in step1memo:
            continue
        step1memo.add(u1)
        for u2 in edges[u1]:
            if u2 in step2memo:
                continue
            step2memo.add(u2)
            for u3 in edges[u2]:
                heapq.heappush(q, (c+1, u3))

print(cost[T])
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

''' ????????????????????£????????\??? '''


class PQueue(object):
    """ Priority Queue """

    def __init__(self):
        self.pqueue = []

    def insert(self, x):
        self.pqueue.append(x)

    def extractMax(self):
        max_value = max(self.pqueue)
        self.pqueue.pop(self.pqueue.index(max_value))
        return max_value


if __name__ == '__main__':

    pqueue = PQueue()
    result = []

    while True:
        line = input()
        if line == 'end':
            break

        if line.split()[0] == 'insert':
            pqueue.insert(int(line.split()[1]))
        elif line.split()[0] == 'extract':
            result.append(pqueue.extractMax())

    for i in range(len(result)):
        print(result[i])

### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

''' ????????????????????£????????\??? '''

import heapq


class PQueue(object):
    """ Priority Queue """

    def __init__(self):
        self.pqueue = []

    def insert(self, x):
        # self.pqueue.append(x)
        heapq.heappush(self.pqueue, -x)

    def extractMax(self):
        # return self.pqueue.pop(self.pqueue.index(max(self.pqueue)))
        return -heapq.heappop(self.pqueue)


if __name__ == '__main__':

    pqueue = PQueue()
    result = []

    while True:
        line = input()
        if line == 'end':
            break

        if line.split()[0] == 'insert':
            pqueue.insert(int(line.split()[1]))
        elif line.split()[0] == 'extract':
            result.append(pqueue.extractMax())

    for i in range(len(result)):
        print(result[i])
### BUGGY CODE ###

n=int(input())
heights=list(map(int,input().split(" ")))
res=0
for i in range(n):
    for j in range(n):
        if abs(j-i)==heights[i]+heights[j]:
            res+=1
print(int(res/2))

### FIXED CODE ###

n=int(input())
heights=list(map(int,input().split(" ")))
dic={}
res=0
for i in range(n):
    if heights[i]-i not in dic:
        dic[heights[i]-i]=1
    else:
        dic[heights[i]-i]+=1
for j in range(n):
    if -heights[j]-j in dic:
        res+=dic[-heights[j]-j]
print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
Q = int(input())
query = []
rmax = -1
for _ in range(Q):
    line = list(map(int, input().split()))
    query.append(line)
    rmax = max(rmax, line[1])

prime = [2]

for x in range(3, rmax+1):
    pflag = True
    for n in prime:
        if x%n==0:
            pflag = False
            break
        if x<n*n:
            break
    if pflag:
        prime.append(x)
# print(prime)
acc = [0 for _ in range(rmax+1)]
for n in range(rmax+1):
    if n in prime and (n+1)//2 in prime:
        acc[n] += 1
    if n<rmax:
        acc[n+1] += acc[n]
# print(acc)
for q in query:
    print(acc[q[1]] - acc[q[0]-1])


### FIXED CODE ###

def sieve(n):
    res = list(range(n+10)) # nが小さい時よう
    res[0] = -1
    res[1] = -1
    i = 2
    while i*i<n:
        if res[i]<i:
            i += 1
            continue
        j = i*i
        while j<n:
            if res[j]==j:
                res[j] = i
            j += i
        i += 1
    return res

s = sieve(10**5+10)
acc = [0]*(10**5+10)
for i in range(2,10**5+9):
    if i%2==1 and s[i]==i and s[(i+1)//2]==(i+1)//2:
        acc[i+1] = acc[i]+1
    else:
        acc[i+1] = acc[i]

q = int(input())
res = [0]*q
for i in range(q):
    l,r = map(int, input().split())
    res[i] = acc[r+1]-acc[l]

for r in res:
    print(r)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10 ** 9

dp = [INF] * N
dp[0] = 0

for i in range(N - 1):
    for k in range(1, K + 1):
        if i + k > N - 1:
            break
        dpp = dp[i] + abs(h[i + k] - h[i])
        dp[i + k] = min(dp[i + k], dpp)

print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

INF = 10 ** 9
dp = [INF] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

def chmin(a, b):
    if a > b:
        return b
    else:
        return a
        
for i in range(2, N):
    for j in range(1, K + 1):
        dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[-1])