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

def prime(n):
    num=[i for i in range(n,1,-1)]
    prime=[]
    p = 2
    while p <=n**0.5 or num:
        p=num.pop()
        prime.append(p)
        num = [i for i in num if i%p != 0]
    return prime
def chk_prime(n):
    for i in range(2,-1*int(-n**0.5//1)):
        if n%i == 0:
            return False
    return True

def main():
    a,b=map(int,input().split(' '))

    ans = 1
    if chk_prime(min(a,b)):
        if max(a,b)%min(a,b) == 0 and min(a,b) != 1:
            ans = 2
    else:
        prime_list=prime(int(min(a,b)/2))
        for i in prime_list:
            if a%i == 0 and b%i==0:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from math import *
def gcd(n,m):
    while m != 0:
        n,m=m,n%m
    return n
def main():
    a,b=map(int,input().split(' '))
    g=gcd(a,b)
    cnt = 1
    g2 = int(sqrt(g))
    for i in range(2,g2+1):
        if g%i ==0:
            while g%i ==0:
                g //= i
            cnt += 1
    if g > 1:
        cnt += 1
    print(cnt)

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

import sys
input=sys.stdin.readline

def main():
    s=input().strip()
    q=int(input())
    cnt=0
    Q=[]
    for _ in range(q):
        query=input().strip()
        if query=='1':
            cnt+=1
        else:
            _,f,c=query.split()
            Q.append((cnt,int(f),c))
    if cnt%2==0:
        ans=s
    else:
        ans=s[::-1]
    for a,f,c in Q:
        if (cnt-a+f)%2==0:
            ans+=c
        else:
            ans=c+ans
    print(ans)
    
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque

def main():
    S=deque(input().strip())
    q=int(input())
    rev=0
    for _ in range(q):
        query=input().strip()
        if query=='1':
            rev^=1
        else:
            _,f,c=query.split()
            if (int(f)+rev)%2:
                S.appendleft(c)
            else:
                S.append(c)
    if rev:
        S.reverse()
    print(''.join(S))
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

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

ans = 1
for i in range(n):
    ans *= a[i]
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

if 0 in a:
    print(0)
    exit()
ans = 1
for i in range(n):
    ans *= a[i]
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
inf = float('inf')

class SegmentTree:
    def __init__(self, N):
        tmp = 1
        while tmp < N:
            tmp <<= 1
        self.N = tmp
        self.data = [inf for _ in range(2*self.N-1)]
    
    def update(self, l, r, x):
        L = l + self.N
        R = r + self.N

        while L < R:
            if R & 1:
                R -= 1
                self.data[R] = min(self.data[R], x)
            if L & 1:
                self.data[L] = min(self.data[L], x)
                L += 1
            L >>= 1; R >>= 1
    
    def value(self, k):
        k += self.N
        res = self.data[k]
        while k != 0:
            k >>= 1
            res = min(res, self.data[k])
        return res

N, Q = map(int,input().split())
STX = [list(map(int,input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

st = SegmentTree(Q)
for S, T, X in STX:
    l = bisect_left(D, S-X)
    r = bisect_left(D, T-X)
    st.update(l, r, X)

for k in range(Q):
    ans = st.value(k)
    if ans == inf:
        ans = -1
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left
inf = float('inf')

N, Q = map(int,input().split())
STX = [list(map(int,input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

res = 1
while res < Q:
    res <<= 1
N0 = res
data = [inf for _ in range(2*N0-1)]

def update(l, r, x):
    L = l + N0
    R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R] = min(data[R], x)
        if L & 1:
            data[L] = min(data[L], x)
            L += 1
        L >>= 1; R >>= 1

def value(k):
    k += N0
    res = data[k]
    while k != 0:
        k >>= 1
        res = min(res, data[k])
    return res


for S, T, X in STX:
    l = bisect_left(D, S-X)
    r = bisect_left(D, T-X)
    update(l, r, X)

for k in range(Q):
    ans = value(k)
    if ans == inf:
        ans = -1
    print(ans)
### BUGGY CODE ###

n = int(input())
arr = list(map(int, input().split()))
res = arr[0]
 
for a in arr[1:]:
  res *= a
 
if res > 1000000000000000000:
  print("-1")
else:
  print(res)

### FIXED CODE ###

def main():
  n = int(input())
  arr = list(map(int, input().split()))
  
  
  if 0 in arr:
    print(0)
    return 0
  res = arr[0]
  for a in arr[1:]:
    res *= a
    if res > 1000000000000000000:
      print("-1")
      return 0

  print(res)

main()
### BUGGY CODE ###

def solve():
    H, N = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]
    
    INF = 10 ** 9
    dp = [INF for _ in range(10 ** 7)]
    dp[0] = 0

    for a, b in A:
        for i in range(H+1):
            if dp[i] == INF: continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
            
    return min(dp[H:])

print(solve())

### FIXED CODE ###

import numpy as np

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

A = []
B = []
for i in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

A = np.array(A)
B = np.array(B)

dp = np.full((H+1), np.inf)
dp[0] = 0

def solve():
    for i in range(1, H + 1):
        dp[i] = np.amin(dp[np.maximum(i - A , 0)] + B)
    return int(dp[H])

print(solve())
### BUGGY CODE ###

A, B = map(int, input().split())
ans = 0
for i in range(60):
    # 含まれる1の数を数える
    tmp = (B-A) // 2**(i+1) * 2**i
    p = A%(2**(i+1))
    q = (B-A)%(2**(i+1))
    for j in range(p, p + q + 1):
        if j % (2**(i+1)) >= 2**i:
            tmp += 1
    ans += (tmp%2) * 2**i
print(ans)

### FIXED CODE ###

A, B = map(int, input().split())
ans = 0
for i in range(40):
    # 含まれる1の数を数える
    tmp = (B-A) // 2**(i+1) * 2**i
    p = A%(2**(i+1))
    q = (B-A)%(2**(i+1))
    # p から p+qの中で余りが2**i ~ 2**(i+1)-1になる個数を求める
    tmp += max(min(p+q,2**(i+1)-1) - max(p,2**i)+1,0)
    tmp += max(min(p+q,2**(i+1)-1 + 2**(i+1)) - max(p,2**i + 2**(i+1))+1,0)
    ans += (tmp%2) * 2**i
print(ans)
### BUGGY CODE ###

import math

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

min_ind = a.index(min(a))

start = sorted([min_ind - x for x in range(k) if min_ind - x >= 0])
end = [s+k-1 for s in start]

ans = 10**6
for s, e in zip(start, end):
    ans = min(ans, math.ceil(len(a[:s])/(k-1)) + math.ceil(len(a[e+1:])/(k-1)))

print(ans+1)

### FIXED CODE ###

import math

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

    min_ind = a.index(min(a))

    start = [min_ind - x for x in range(k) if min_ind - x >= 0]
    end = [s+k-1 for s in start]

    ans = 10**6
    for s, e in zip(start, end):
        ans = min(ans, math.ceil(s/(k-1)) + math.ceil((n-(e+1))/(k-1)))

    print(ans+1)

main()
### BUGGY CODE ###

import numpy as np
from itertools import product

H,W,K = map(int, input().split())
S = np.array(([list(map(int,list(input()))) for _ in range(H)])).T

if np.sum(S)<=K:
    print(0)
else:
    answer = (H-1) * (W-1)
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        if ans >= answer:
            continue
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = np.zeros(len(M))
        for s in S:
            D[:] += [np.sum(s[m]) for m in M]
            if any(d > K  for d in D):
                ans += 1
                if ans >= answer:
                    break
                D[:] = [np.sum(s[m]) for m in M]

        if answer > ans:
            answer = ans
        elif answer==1:
            break

    print(min(answer,ans))

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
### BUGGY CODE ###

import sys
import numpy as np

N, M = input().split()

N = int(N)
M = int(M)

A = np.zeros([2,M])

cnt = 0

for i in range(M):
    A[:,i] = input().split()

for i in range(1,N+1):
    for j in range(M):
        if A[0,j] <= i and i <= A[1,j]:
            continue
        else:
            cnt += 1
            break

print(N - cnt)

### FIXED CODE ###

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

left = 1
right = N

for l, r in LR:
    left = max(left, l)
    right = min(right, r)

ans = right - left

print(ans + 1 if ans >= 0 else 0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
import math
import itertools
import re
 
# 入力
N = int(input())
S = str(input())
#M1, D1 = map(int, input().split())
 
si = ""
cnt = 0
for i in range(1000) :
  
  si = str(i).zfill(3)
  pattern = "^.*"+ si[0] + ".*" + si[1] + ".*" + si[2] + ".*$"
  
  if re.match(pattern, S) :
    cnt += 1

print (cnt)

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
import math
import itertools
import re
 
# 入力
N = int(input())
S = str(input())
#M1, D1 = map(int, input().split())
 
si = ""
cnt = 0
for i in range(1000) :
  
  si = str(i).zfill(3)
  
  c = 0
  for x in range(N) :
    if S[x] == si[c] :
      c += 1
      if c == 3 :
        cnt += 1
        break    

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

INF = 10**10 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for (A, B) in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

### FIXED CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])
### BUGGY CODE ###

import math
import numpy as np
result = 0
n = int(input())
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            result +=  np.gcd.reduce((i,j,k))
print(result)


### FIXED CODE ###

from math import gcd
ans = 0
k = int(input())
for i in range(1, k+1):
	for j in range(1, k+1):
		for l  in range(1, k+1):
			ans += gcd(gcd(i, j), l)
print(ans)
### BUGGY CODE ###

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

s=0
for i in range(a,b+1):
    if i%c==0 or i%d==0:
        s+=1
print(b-a+1-s)


### FIXED CODE ###

a,b,c,d=map(int,input().split())
import fractions


lcm=int(c*d/fractions.gcd(c,d))

cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
cd=b//lcm-(a-1)//lcm

print((b-a+1)-(cc+dd-cd))
### BUGGY CODE ###

n,q = [int(i) for i in input().split()]

s = input()

l = [[int(i) for i in input().split()] for _ in range(q)]

for i in l:
    ct = 0
    ss = s[i[0]-1:i[1]]
    while ss.find('AC') > -1:
        ss = ss.replace('AC','',1)
        ct += 1
    print(ct)

### FIXED CODE ###

n,q = [int(i) for i in input().split()]
string = input()
l = [[int(i) for i in input().split()] for _ in range(q)]

ans = [0 for _ in range(n)]

for i in range(n-1):
    if string[i] == 'A' and string[i+1] == 'C':
        ans[i+1] = ans[i] +1
    else:
        ans[i+1] = ans[i]
        
for x,y in l:
    print(ans[y-1] - ans[x-1])
### BUGGY CODE ###

def comb(li):
    return len(li) * (len(li) - 1) // 2


def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


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

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n * (n - 1) // 2 - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()

    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg) + count_large(m, pos)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)


# k-th is 0
else:
    print(0)


### FIXED CODE ###

def comb(li):
    return len(li) * (len(li) - 1) // 2


def count_large(x, li):
    cnt = 0
    j = 0
    for e in li:
        cnt -= e * e >= x
        while li[j-1] * e >= x:
            j -= 1

        cnt -= j

    cnt //= 2
    return cnt


n, k = map(int, input().split())
a = list(map(int, input().split()))
INF = 10 ** 20

neg = []
pos = []

for e in a:
    if e > 0:
        pos.append(e)
    elif e < 0:
        neg.append(e)

# k-th is negative
if k <= len(pos) * len(neg):
    neg.sort()
    neg.append(0)
    pos.sort()

    lb = -10 ** 18 - 1
    ub = 0
    while ub - lb > 1:
        m = (lb + ub) // 2
        j = -1
        cnt = 0
        for e in pos:
            while neg[j+1] * e <= m:
                j += 1

            cnt += j + 1

        if cnt >= k:
            ub = m
        else:
            lb = m

    print(ub)

# k-th is positive
elif k >= n * (n - 1) // 2 - comb(pos) - comb(neg) + 1:
    neg = [-e for e in neg]
    neg.append(0)
    neg.sort()
    pos.append(0)
    pos.sort()

    lb = 1
    ub = 10 ** 18 + 1
    while ub - lb > 1:
        m = (lb + ub) // 2
        cnt = count_large(m, neg) + count_large(m, pos)
        if cnt >= n * (n - 1) // 2 - k + 1:
            lb = m
        else:
            ub = m

    print(lb)


# k-th is 0
else:
    print(0)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    gamed = [0 for _ in range(N)]
    while 1:
        for i in range(N):
            gamed[i] = 0
            
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

import fractions
import math
def cf(X, Y):
    ans = []
    for i in range(2, min(X, Y) + 1):
        if X % i == 0 and Y % i == 0:
            ans.append(i)
    return ans

def is_prime(N):
    if N == 1:
        return False
    for k in range(2, int(math.sqrt(N)) + 1):
        if N % k == 0:
            return False
    return True
A, B = map(int, input().split())
##print(cf(A, B))
cf_list = cf(A, B)
ans = 1

for n in cf_list:
    if is_prime(n):
        ans += 1
print(ans)

### FIXED CODE ###

import fractions

def prime_factorization(N):
    tmp = N
    ans = []
    for i in range(2, int(N ** 0.5) + 1):
        count = 0
        while tmp % i == 0:
            tmp //= i
            count += 1
        if count != 0:
            ans.append([i, count])
    if tmp != 1:
        ans.append([tmp, 1])
    if ans == []:
        ans.append([N, 1])
    return ans

A, B = map(int, input().split())

gcdAB = fractions.gcd(A, B)

if gcdAB == 1:
    print(1)
else:
    print(len(prime_factorization(gcdAB)) + 1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*bc)]


ans = sum(a)
for i in range(q):
  dif = c[i] - b[i]
  ans += dif * a.count(b[i])
  a = [c[i] if j == b[i] else j for j in a]
  print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*bc)]

app = [0] * 100001
for num in a:
  app[num] += 1

ans = sum(a)
for i in range(q):
  dif = c[i] - b[i]
  ans += dif * app[b[i]]
  app[c[i]] += app[b[i]]
  app[b[i]] = 0
  print(ans)
### BUGGY CODE ###

def resolve():
    import copy
    n = int(input())
    x = int(input(), 2)

    for i in range(n):
        ans = 0
        temp_x = copy.deepcopy(x)
        m = 2**(n - i - 1)
        temp_x ^= m
        while temp_x > 0:
            pc = sum(list(map(lambda i: int(i), format(temp_x, 'b'))))
            temp_x %= pc
            ans += 1

        print(ans)

resolve()

### FIXED CODE ###

def resolve():
    def popcnt(x):
        return bin(x).count("1")

    N = int(input())
    Xs = input()
    X = int(Xs, 2)
    d = popcnt(X)

    lut = [0] * N
    for i in range(1, N):
        Xi = i % popcnt(i)
        lut[i] = lut[Xi] + 1

    dp = d+1
    dm = d-1
    mp = X % dp
    mm = X % dm if dm else 0
    # print(lut)
    # print(format(X, 'b'))

    ans = []
    for i in range(N):
        mask = 1 << (N-i-1)
        Xi = X ^ mask
        _ans = 0
        if Xs[i] == '1':
            if dm:
                m = (mm - pow(2, N-i-1, dm)) % dm
                _ans = lut[m] + 1
            # m = (mm - mask) % dm
        else:
            # m = (mp + mask) % dp
            m = (mp + pow(2, N-i-1, dp)) % dp
            _ans = lut[m] + 1
        ans.append(_ans)
    print(*ans, sep='\n')

resolve()
### BUGGY CODE ###

import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def calc_step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = calc_step2patterns(num_step)
        step_dict[num_step] = ret
        return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1, d)

print(num_pattern % 1000000007)
exit(0)


### FIXED CODE ###

def exec_ncr(max_step, record_dict):
    for i in range(2, max_step+1):
        record_dict[i] = record_dict[i-1] + record_dict[i-2]


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1}
exec_ncr(num_stair, d)

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= d[dry_step-1]

# last step
dry_step = num_stair - last_wet

num_pattern *= d[dry_step-1]

print(num_pattern % 1000000007)
exit(0)
### BUGGY CODE ###

from collections import Counter

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

a=Counter(A)
b=Counter(B)
c=Counter(C)

ans=0

for i in a:
    for j in [x for x in b if x > i]:
        for k in [y for y in c if y > j]:
            ans += a[i]*b[j]*c[k]

print(ans)

### FIXED CODE ###

import bisect

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort()
B.sort()
C.sort()

ans = 0
for i in B:
    ins_a = bisect.bisect_left(A,i)
    ins_c = bisect.bisect_right(C,i)
    ans+=ins_a*(N-ins_c)

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

# -*- coding: utf-8 -*-
import sys
# 12:55~
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
uv = [list(map(int,input().split())) for _ in range(M)]
S,T = map(int,input().split())

S -= 1
T -= 1
#%%
adj_list = [[] for _ in range(N)]
for u,v in uv:
    adj_list[u-1].append(v-1)

INF = 10**9+7
dist = [[INF]*3 for _ in range(N)]
dist[S][2] = 0

stack = [[S,0]]
while stack:
    v,count = stack.pop()
    nxt_v = adj_list[v]
    cnt = count%3
    for nv in nxt_v:
        if dist[nv][cnt]>(count+1)//3:
            dist[nv][cnt] = min(dist[nv][cnt],(count+1)//3)
            stack.append([nv,count+1])
            
            
if dist[T][2]==INF:
    ans = -1
else:
    ans = dist[T][2]
print(ans)
            
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from queue import Queue
# 12:55~
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
uv = [list(map(int,input().split())) for _ in range(M)]
S,T = map(int,input().split())

S -= 1
T -= 1
#%%
adj_list = [[[] for _ in range(3)] for _ in range(N)]
for u,v in uv:
    for i in range(3):
        adj_list[u-1][i].append([v-1,(i+1)%3])


INF = 10**9+7
dist = [[INF]*3 for _ in range(N)]
dist[S][0] = 0

stack = Queue()
stack.put([S,0])
while not stack.empty():
    v,c = stack.get()
    nxt_v = adj_list[v][c]
    for nv,nc in nxt_v:
        if dist[nv][nc]==INF:
            dist[nv][nc] = dist[v][c] + 1
            stack.put([nv,nc])
            
            
if dist[T][0]==INF:
    ans = -1
else:
    ans = dist[T][0]//3
print(ans)