Harryxun/stf_run huggingface dataset:
# coding: utf-8
# Your code here!
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n,k=map(int,input().split())
b=k
r=n-k
if k>r+1:
    m=r+2
ans=r+1
print(ans)
for i in range(2,k+1):
    ans=0
    for j in range(3):
        if i>=m:
            print(0)
            break
        if r-1>=i-j:
            tmp=cmb(r-1,i-j)
            p=1
            if j==1:
                p=2
            ans+=cmb(b-1,i-1)*tmp*p
            ans=ans%(10**9+7)
    print(ans)

        


### FIXED CODE ###

# coding: utf-8
N,K=map(int,input().split())
MOD=10**9+7

fac=[None for i in range(5000)]
finv=[None for i in range(5000)]
inv=[None for i in range(5000)]

def COMinit(num):
    global fac
    global finv
    global inv
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(2,num):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def COM(n,k):
    if n<k:
        return 0
    elif n<0 or k<0:
        return 0
    else:
        return int(fac[n] * (finv[k] * finv[n - k] % MOD) % MOD)


COMinit(5000)

for i in range(1,K+1):
    print(COM(N-K+1,i)*COM(K-1,i-1)% MOD)

#print(COM(0,0))
x = input()
t = input()

if t < x:
  print( x - t )
else:
  print( 0 )

### FIXED CODE ###

x , t = map(int ,input().split() )


if t < x:
  print( x - t )
else:
  print( 0 )
p,q,r = [int(i) for i in input().split(' ')]

l = list(p,q,r)
l.sort()

ans=l[0]+l[1]

print(ans)

### FIXED CODE ###

p,q,r = [int(i) for i in input().split(' ')]

x = p+q
y = q+r
z = r+p

print(min([x,y,z]))
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
flag = True
r = set(list(range(n)))
while True:
    ne = set()
    if not r:
        print(ans)
        break
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in n:
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
        ans += 1


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if not r:
        print(_)
        break
    ne = set()
    flag = True
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j].pop(0)
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
S = input()
T = input()
ans = 0
for i in range(N):
  if S[i] == T[i]:
    ans +=1
print(ans)

### FIXED CODE ###

S = input()
T = input()
ans = 0
for i in range(3):
  if S[i] == T[i]:
    ans +=1
print(ans)
v = []
v = str(input()).split()
dif_max = -200000

for i in range(len(v)):
    v[i] = int(v[i])

print("{}".format(v[3]))

### FIXED CODE ###

cnt = int(input())
dif_max = -1000000000
v_min = 1000000000

for i in range(cnt):
    buf = int(input())
    if i > 0:
        dif_max = dif_max if buf - v_min < dif_max else buf - v_min
    v_min = buf if buf < v_min else v_min
print(dif_max)
a,b,x = list(map(int,input().split()))
if a*10**9+b*10 <= x:
  print(10**9)
elif a+b > x:
  print(0)
else:
  for i in range(9,0,-1):
    y = (x - i*b)//a
    if len(str(y))==i:
      print(max(0,y))
      break
  else:
    print(0)

### FIXED CODE ###

s = input()
x = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']
print(7-x.index(s))
K = input()
D = int(input())
L = len(K)
mod = 10 ** 9 + 7

dp = [[[0] * 2 for _ in range(D)] for _ in range(L+1)]
dp[0][0][0] = 1

for i in range(L):
    nd = int(K[i])
    for j in range(D):
        for k in range(2):
            #lim = 9 if k == 1 else nd
            for d in range(10):
                nk = k
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[i+1][(j+d) % D][nk] += dp[i][j][k]
                dp[i+1][(j+d) % D][nk] %= mod

ans = (dp[L][0][0]+dp[L][0][1]-1+mod) % mod

#for i in range(L+1):
#    print(dp[i])
print(ans)

### FIXED CODE ###

K = input()
D = int(input())
L = len(K)
mod = 10 ** 9 + 7

dp = [[[0] * 2 for _ in range(D)] for _ in range(L+1)]
dp[0][0][0] = 1

for i in range(L):
    nd = int(K[i])
    for j in range(D):
        for k in range(2):
            #lim = 9 if k == 1 else nd
            for d in range(10):
                nk = k
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[i+1][(j+d) % D][nk] += dp[i][j][k]
                dp[i+1][(j+d) % D][nk] %= mod

ans = (dp[L][0][0]+dp[L][0][1]-1+mod) % mod

#for i in range(L+1):
#    print(dp[i])
print(ans)
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,W = inpl()
value = []
weight = []
for i in range(n):
    a,b = inpl()
    value.append(a)
    weight.append(b)
dp = [[0 for i in range(n+5)] for j in range(W+5)]
for i in range(n):
    for w in range(W+1):
        if w >= weight[i]:
            dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[n][w])

# n=6
# (weight,value)=(2,3),(1,2),(3,6),(2,1),(1,3),(5,85)
# W=8

# >> 91

### FIXED CODE ###

from collections import Counter,defaultdict
import sys,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,w = inpl()
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i],vv[i] = inpl()
dp = [[mod for i in range(sum(vv)+1)] for j in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum(vv)+1):
        if j >= vv[i]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-vv[i]]+ww[i])
        else:
            dp[i+1][j] = dp[i][j]
for i in range(sum(vv)+1)[::-1]:
    if dp[n][i] <= w:
        print(i)
        break
x, a = map(int, input().split)
if x < a:
    print(0)
else:
    print(10)

### FIXED CODE ###

x, a = map(int, input().split())
if x < a:
    print(0)
else:
    print(10)
N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G = [[] for _ in range(N + 1)]
for el in XYZ:
    x, y, z = el
    G[x].append(y)
    G[y].append(x)

seen=[False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)

cnt = 0
for start in range(1, N + 1):
    if seen[start] == False:
        dfs(start)
        cnt += 1
print(cnt)


### FIXED CODE ###

import queue
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

seen=[False]*(N+1)
todo=queue.Queue()
def bfs(n):
    seen[n]=True
    for nxt in G[n]:
        if seen[nxt]==False:
            bfs(nxt)


cnt=0
for check in range(1, N+1):
    if seen[check]==False:
        cnt+=1
        bfs(check)
print(cnt)
def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        ab.sort()
        
        plus = [0 for _ in range(N)]
        for _ in range(Q):
        	p,x = map(int,input().split())
        	plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        print(*p)

if __name__ == '__main__':
        main()

### FIXED CODE ###

def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        px = [list(map(int,input().split())) for _ in range(Q)]
        ab.sort()
        # px.sort()
        plus = [0 for _ in range(N)]

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

if __name__ == '__main__':
        main()
n=int(input())
da=list(map((int,input().split()))
ans=0
for i in da:
  ans+=i-1
print(ans)


### FIXED CODE ###

n=int(input())
da=list(map(int,input().split()))
ans=0
for i in da:
  ans+=i-1
print(ans)
N = int(input())
steps = list(map(int, input().split(" ")))

costs = [None] * N
costs[0] = 0
costs[1] = abs(steps[1] - steps[0])
costs[2] = min(abs(steps[2] - steps[0]), costs[1] + abs(steps[2] - steps[1]))

for i in range(3, N):
    cost1 = costs[i-1] + abs(steps[i-1] - steps[i])
    cost2 = costs[i-2] + abs(steps[i-2] - steps[i])
    costs[i] = min(cost1, cost2)

print(costs[N-1])

### FIXED CODE ###

N = int(input())
steps = list(map(int, input().split(" ")))

costs = [None] * N
costs[0] = 0
costs[1] = abs(steps[1] - steps[0])
if N > 2:
    costs[2] = min(abs(steps[2] - steps[0]), costs[1] + abs(steps[2] - steps[1]))

for i in range(3, N):
    cost1 = costs[i-1] + abs(steps[i-1] - steps[i])
    cost2 = costs[i-2] + abs(steps[i-2] - steps[i])
    costs[i] = min(cost1, cost2)

print(costs[N-1])
import numpy as np

MOD = 10**9 + 7
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
ans = 1
plus = a[a >= 0]
plus = np.sort(plus)[::-1]
plus = np.append(plus, [0, 0])
minus = a[a < 0]
minus = np.sort(minus)
minus = np.append(minus, [0, 0])
if n == k:
    for i in range(len(a)):
        ans *= a[i]
        ans %= MOD
    print(ans)
    exit()
if len(plus) == 2 and k % 2 == 1:
    for i in range(3, k + 3):
        ans *= minus[-i]
        ans %= MOD
else:
    if k % 2 == 1:
        p = k // 2
        ans *= plus[0]
        cplus = 1
        cminus = 0
    else:
        p = k // 2
        cplus = 0
        cminus = 0
    for l in range(p):
        if plus[cplus] * plus[cplus + 1] > minus[cminus] * minus[cminus + 1]:
            ans *= plus[cplus] * plus[cplus + 1]
            ans %= MOD
            cplus += 2
        else:
            ans *= minus[cminus] * minus[cminus + 1]
            ans %= MOD
            cminus += 2
print(int(ans))

### FIXED CODE ###

    #n,k,*a=map(int,open(0).read().split())
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
mod=10**9+7
ans=1
i=0
j=-1
kk=k
while kk>1:
    if a[i]*a[i+1]>a[j]*a[j-1]:
        ans=ans*a[i]*a[i+1]%mod
        i+=2
        kk-=2
    else:
        ans=ans*a[j]%mod
        j-=1
        kk-=1
if kk==1:
    ans=ans*a[j]%mod

if a[-1]<0 and k%2==1:
    ans=1
    for i in a[n-k:]:
        ans=ans*i%mod
print(ans)
sec_time = int(input())

hour = sec_time // 3600
minutes = sec_time % 3600 // 60
seconds = sec_time % 3600 % 60

time = ':'.join(hour, minutes, seconds)

print(time)

### FIXED CODE ###

sec_time = int(input())

hour = sec_time // 3600
minutes = sec_time % 3600 // 60
seconds = sec_time % 3600 % 60

print("{}:{}:{}".format(hour, minutes, seconds))
d = int(input())
if d = 25:
  print("Christmas")
elif d = 24:
  print("Christmas Eve")
elif d = 23:
  print("Christmas Eve Eve")
elif d = 22:
  print("Christmas Eve Eve Eve")

### FIXED CODE ###

d = int(input())
if d == 25:
  print("Christmas")
elif d == 24:
  print("Christmas Eve")
elif d == 23:
  print("Christmas Eve Eve")
elif d == 22:
  print("Christmas Eve Eve Eve")
from math import prod
n = int(input())

a = list(map(int,input().split()))
new = math.prod(a)
val = pow(10,18)
if new > val:
	print(-1)
else:
	print(new)	 


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
new = 1
if 0 in a:
	print(0)
	exit()
for i in a:
	new *= i
	if new > (10**18):
		new = -1
		break
print(new)
N = input()
l = [int(input()) for i in range(N)]
_max = 0
_min = l[0]
for t in l:
  if _max < t:
    _max = t
  if _min > t:
    _min = t  
return _max - _min

### FIXED CODE ###

N = input()
string_list = input().rstrip().split()
l = [int(x) for x in string_list]
_max = 0
_min = l[0]
for t in l:
  if _max < t:
    _max = t
  if _min > t:
    _min = t  
print(_max - _min)
x = int(input())

if x, 1200:
  print(ABC)
  
else:
  print(ARC)

### FIXED CODE ###

x = int(input())
 
if x < 1200:
  print("ABC")
  
else:
  print("ARC")
N, M=map(int, input().split())
if M>0:
  a=[int(input()) for i in range(M)]

  if a[0]==1:
    way=[1, 0]
    a.remove(1)
  else:
    way=[1, 1]
else:
  way=[1, 1]
  
for i in range(2, N+1):
  if len(a)>0:
    if i==a[0]:
      a.remove(i)
      way=[way[1], 0]
    else:
      way=[way[1], sum(way)]
  else:
    way=[way[1], sum(way)]
    
print(way[1]%1000000007)

### FIXED CODE ###

temp=input().split()
N=int(temp[0])
M=int(temp[1])

index=[int(1) for i in range(N)]
for i in range(M):
  index[int(int(input())-1)]=0

temp=[0, 1]
for i in range(N):
  if index[i]==1:
    temp=[temp[1], temp[0]+temp[1]]
  else:
    temp=[temp[1], 0]
    
print(temp[1]%1000000007)
l=[]
n,W=list(map(int,input().split()))
for i in range(n):
	item=list(map(int,input().split))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

print(l)
def solve(i,w):
	if i==n:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		a=solve(i+1,w)
		b=l[i][1]+solve(i+1,w-l[i][0])
		if b>a:
			print("select",i)
			return(b)
		else:
			return(a)

print(solve(0,W))

### FIXED CODE ###

value=[0]
weight=[0]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	value.append(item[0])
	weight.append(item[1])

dp=[[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	for j in range(W+1):
		if i==0:
			res=0
		elif j-weight[i]<0:
			res=dp[i-1][j]
		else:
			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
		dp[i][j]=res
print(dp[n][W])
n = int(input()
a = list(map(int, input().split()))
cnt = 0
for i in range(len(a)):
  if (i+1)%2 != 0 and a[i]%2 != 0:
    cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(len(a)):
  if (i+1)%2 != 0 and a[i]%2 != 0:
    cnt += 1
print(cnt)
list = int(input().split)

if a * b % 2 == 0:
    print("Even")
else:
    print("Odd")

### FIXED CODE ###

list = input().split()
a, b = int(list[0]), int(list[1])

if a * b % 2 == 0:
    print("Even")
else:
    print("Odd")
a, b, c, k = map(int, input().split());

if a > k:
  print(k)
  break;
else:
  num = a; 
  
  if k >= a + b:
  num -= k - (a + b);
  print(num)

### FIXED CODE ###

a, b, c, k = map(int, input().split());

if a > k:
  print(k)
else:
  num = a; 
  
  if k >= a + b:
      num -= k - (a + b);
  print(num)
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
m = 0
if a[0] == 1 or a[1]==1 or a[2]==1:
    for i in range(n-2):
        if a[i] == a[i+1] == a[i+2] or a[i] == a[i+1]:
            if a[i+2] == a[n-1]:
                a[i] = min(a[i],a[i+1],a[i+2])
                a[i+1] = min(a[i],a[i+1],a[i+2])
                a[i+2] = min(a[i],a[i+1],a[i+2])
                ans+= 1
            else:
                continue

        else:
            a[i] = min(a[i],a[i+1],a[i+2])
            a[i+1] = min(a[i],a[i+1],a[i+2])
            a[i+2] = min(a[i],a[i+1],a[i+2])
            ans+= 1
else:
    for i in range(n):
        if a[i]==1:
            m = i
            break
    for i in range(m,n-2):
        if a[i] == a[i+1] == a[i+2] or a[i] == a[i+1]:
            if a[i+2] == a[n-1]:
                a[i] = min(a[i],a[i+1],a[i+2])
                a[i+1] = min(a[i],a[i+1],a[i+2])
                a[i+2] = min(a[i],a[i+1],a[i+2])
                ans+= 1
            else:
                continue
        else:
            a[i] = min(a[i],a[i+1],a[i+2])
            a[i+1] = min(a[i],a[i+1],a[i+2])
            a[i+2] = min(a[i],a[i+1],a[i+2])
            ans+= 1
    for i in reversed(range(m)):
        if a[i] == a[i-1] == a[i-2] or a[i] == a[i-1]:
            if a[i-2] == a[0]:
                a[i] = min(a[i],a[i-1],a[i-2])
                a[i+1] = min(a[i],a[i-1],a[i-2])
                a[i+2] = min(a[i],a[i-1],a[i-2])
                ans+= 1
            else:
                continue
        else:
            a[i] = min(a[i],a[i-1],a[i-2])
            a[i+1] = min(a[i],a[i-1],a[i-2])
            a[i+2] = min(a[i],a[i-1],a[i-2])
            ans+= 1
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(input())
Ans = 0
 
if (N-1)%(K-1)==0:
    Ans = (N-1)//(K-1)
else:
    Ans = (N-1)//(K-1) + 1
 
print(Ans)
import bisect

N = int(input())
S = list(str(input()))

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      I = bisect.bisect(li[ordN(S[Q2])])
      li[ordN(S[Q2])].pop(I)
      bisect.insort(li[ordN(Q3)], Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      I = bisect.bisect_left(li[j], Q2)
      if I < len(li[j]) and li[j][I] <= Q3:
        count += 1
    print(count)

### FIXED CODE ###

import bisect

N = int(input())
S = list(str(input()))

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      I = bisect.bisect_left(li[ordN(S[Q2])], Q2)
      li[ordN(S[Q2])].pop(I)
      bisect.insort(li[ordN(Q3)], Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      I = bisect.bisect_left(li[j], Q2)
      if I < len(li[j]) and li[j][I] <= Q3:
        count += 1
    print(count)
a=[0]*26
w='abcdefghijklmnopqrstuvwxyz'
try:
    while True:
        s=list(input().upper())
        for i in s:
            if i=='A':
                a[0]+=1
            elif i=='B':
                a[1]+=1
            elif i=='C':
                a[2]+=1
            elif i=='D':
                a[3]+=1
            elif i=='E':
                a[4]+=1
            elif i=='F':
                a[5]+=1
            elif i=='G':
                a[6]+=1
    elif i=='H':
        a[7]+=1
    elif i=='I':
        a[8]+=1
    elif i=='J':
        a[9]+=1
    elif i=='K':
        a[10]+=1
    elif i=='L':
        a[11]+=1
    elif i=='M':
        a[12]+=1
    elif i=='N':
        a[13]+=1
    elif i=='O':
        a[14]+=1
    elif i=='P':
        a[15]+=1
    elif i=='Q':
        a[16]+=1
    elif i=='R':
        a[17]+=1
    elif i=='S':
        a[18]+=1
    elif i=='T':
        a[19]+=1
    elif i=='U':
        a[20]+=1
    elif i=='V':
        a[21]+=1
    elif i=='W':
        a[22]+=1
            elif i=='X':
                a[23]+=1
            elif i=='Y':
                a[24]+=1
            elif i=='Z':
                a[25]+=1 

except EOFError:
    pass

for i in range(26):
    print(w[i:i+1], ':', str(a[i]))

### FIXED CODE ###

a=[0]*26
w='abcdefghijklmnopqrstuvwxyz'
try:
    while True:
        s=list(raw_input().upper())
        for i in s:
            if i=='A':
                a[0]+=1
            elif i=='B':
                a[1]+=1
            elif i=='C':
                a[2]+=1
            elif i=='D':
                a[3]+=1
            elif i=='E':
                a[4]+=1
            elif i=='F':
                a[5]+=1
            elif i=='G':
                a[6]+=1
            elif i=='H':
                a[7]+=1
            elif i=='I':
                a[8]+=1
            elif i=='J':
                a[9]+=1
            elif i=='K':
                a[10]+=1
            elif i=='L':
                a[11]+=1
            elif i=='M':
                a[12]+=1
            elif i=='N':
                a[13]+=1
            elif i=='O':
                a[14]+=1
            elif i=='P':
                a[15]+=1
            elif i=='Q':
                a[16]+=1
            elif i=='R':
                a[17]+=1
            elif i=='S':
                a[18]+=1
            elif i=='T':
                a[19]+=1
            elif i=='U':
                a[20]+=1
            elif i=='V':
                a[21]+=1
            elif i=='W':
                a[22]+=1
            elif i=='X':
                a[23]+=1
            elif i=='Y':
                a[24]+=1
            elif i=='Z':
                a[25]+=1 

except EOFError:
    pass

for i in range(26):
    print w[i:i+1], ':', str(a[i])
k = int(input('k: '))
a, b = int(input('a: ')), int(input('b: '))

res = False

for i in range(a, b + 1):
    if i % k == 0:
        res = True
        break

if res == True:
    print('OK')
else:
    print('NG')

### FIXED CODE ###

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

flag = False

for i in range(a, b + 1):
    if i % k == 0:
        flag = True
        break

if flag:
    print('OK')
else:
    print('NG')
import queue as q

def main():
    N, M = list(map(int, input().split()))
    D = {}
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        D.setdefault(u, set()).add(v)

    S, T = list(map(int, input().split()))
    S -= 1
    T -= 1
    print(f(D, S, T, N * M))

def f(D, S, T, W):
    close = [set(), set(), set()]
    Q = [None] * W
    index = 0
    end = 1
    Q[0] = (S, 0, 0)

    while end > index:
        p, c, l = Q[index]
        index += 1
        if l == 0 and p == T:
            return c
        close[l].add(p)

        ns = D.setdefault(p, set())
        l, c = (l + 1) % 3, c + (l + 1) // 3
        for n in ns:
            if n in close[l]:
                continue
            Q[end] = (n, c, l)
            end += 1
    return -1

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))

def f(D, S, T):
    close = [[False] * N, [False] * N, [False] * N]
    Q = []
    index = 0
    Q.append((S, 0, 0))

    while len(Q) > index:
        p, c, l = Q[index]
        index += 1
        
        if close[l][p]:
            continue
        
        if l == 0 and p == T:
            return c // 3
        close[l][p] = True

        l, c = (l + 1) % 3, c + 1
        for n in D[p]:
            if close[l][n]:
                continue
            Q.append((n, c, l))
    return -1

if __name__ == "__main__":
    D = {n: set() for n in range(N)}
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        D[u].add(v)

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

    print(f(D, S, T))