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

import copy

n,m=map(int, input().split())
p=list(map(int, input().split()))
q=list()
for i in range(m):
    q.append(set(map(int, input().split())))
count=0
while count!=5000:
    a=q.pop()
    for j in q:
        if len(j&a) != 0:
            j |=a
            count=0
            break
    else:q=[a]+q
    if count>len(q): break
    count+=1

q2=copy.copy(set(p))
for i in q:
    q2 -= i
    
count2=len([i for i in q2 if i==p[i-1]])

for i in q:
    r=list()
    for j in list(i):
        r.append(p[j-1])
    #print(i,r)
    count2 += len(i&set(r))
print(count2)

### FIXED CODE ###

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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

n,m=map(int, input().split())
p=list(map(int, input().split()))
uf1=UnionFind(n)
for i in range(m):
    a,b=map(int, input().split())
    uf1.union(a-1,b-1)
count=0
for i in range(n):
    if uf1.is_same(i,p[i]-1):count+=1
print(count)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

a_b = []
for i in range(X):
    for j in range(Y):
        a_b.append(A[i]+B[j])

ans = []
for k in range(len(a_b)):
    for l in range(Z):
        ans.append(a_b[k]+C[l])
ans = sorted(ans, reverse=True)
for m in range(K):
    print(ans[m])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

a_b = []
for i in range(X):
    for j in range(Y):
        a_b.append(A[i]+B[j])
a_b = sorted(a_b, reverse=True)
ans = []
for k in range(min(K, len(a_b))):
    for l in range(min(K, len(C))):
        ans.append(a_b[k]+C[l])
ans = sorted(ans, reverse=True)
for m in range(K):
    print(ans[m])
### BUGGY CODE ###

from itertools import accumulate

def main():
    n, k = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in range(k):
        b=[0]*(n+1)
        
        for i,v in enumerate(A):
            b[max(0,i-v)]+=1
            b[min(n,i+v+1)]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)][:-1]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

if '__main__' == __name__:
    main()

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

n = int(input())
ans = 0
t = 0
import fractions
for i in range(1,n+1):
  for j in range(1,n+1):
    t = fractions.gcd(i,j)
    for k in range(1,n+1):
      ans += fractions.gcd(t,k)
print(ans)

### FIXED CODE ###

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

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x2-1,y2-1])
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp[x][y+j]=d
                now.append([x,y+j])
            if dp[x][y+j]==-1:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp[x][y-j]=d
                now.append([x,y-j])
            if dp[x][y-j]==-1:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp[x+j][y]=d
                now.append([x+j,y])
            if dp[x+j][y]==-1:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp[x-j][y]=d
                now.append([x-j,y])
            if dp[x-j][y]==-1:
                break
    bfs(d+1)
bfs(1)
print(dp[x1-1][y1-1] if dp[x1-1][y1-1]!=inf else -1)

### FIXED CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                #dp[x][y+j]=d
                cand.add((x,y+j))
                #now.append([x,y+j])
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                #dp[x][y-j]=d
                cand.add((x,y-j))
                #now.append([x,y-j])
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                #dp[x+j][y]=d
                cand.add((x+j,y))
                #now.append([x+j,y])
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                #dp[x-j][y]=d
                cand.add((x-j,y))
                #now.append([x-j,y])
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
### BUGGY CODE ###

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**18
d = [[INF for i in range(N)] for j in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for i in range(N):
    d[i][i] = 0

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

import itertools
ans = INF
for v in itertools.permutations(r,R):
    anss = 0
    for i in range(R-1):
        anss += d[v[i]-1][v[i+1]-1]
    ans = min(ans,anss)
print(ans)

### FIXED CODE ###

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**10
d = [[INF for i in range(n)] for j in range(n)]

for i in range(m):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])

from itertools import permutations

ans = INF
for v in permutations(r,R):
    dis = 0
    for i in range(R-1):
        dis += d[v[i]-1][v[i+1]-1]
    ans = min(ans,dis)

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

A, B, K = map(int, input().split())
for n in range(A, B + 1):
    if A + K > n or n > B - K:
        print(n)

### FIXED CODE ###

A, B, K = map(int, input().split())
for n in range(A, A + K):
    if B >= n:
        print(n)
if A + K > B:
    K = 0
elif A + K > B - K:
    K = B - A - K + 1
for n in range(B - K + 1, B + 1):
    print(n)
### BUGGY CODE ###

K, S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        if i + j > S:
            break
        for k in range(K+1):
            if i + j + k == S:
                cnt += 1
print(cnt)


### FIXED CODE ###

K, S = map(int, input().split())
cnt = 0
for i in range(K+1):
    for j in range(K+1):
        if 0 <= S - i - j <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

from itertools import product

N = int(input())
for h, n in product(range(1, 3501), repeat=2):
    numer = N * h * n
    denom = 4 * h* n - N * n - N * h
    if denom == 0:
        continue
    w, r = divmod(numer, denom)
    if r == 0 and w > 0:
        print(h, n, w)
        break

### FIXED CODE ###

from itertools import product

N = int(input())
for h, n in product(range(1, 3501), repeat=2):
    if 4 / N > 1 / h + 1 / n:
        numer = N * h * n
        denom = 4 * h* n - N * (n + h)
        if denom <= 0:
            continue
        w, r = divmod(numer, denom)
        if r == 0:
            print(h, n, w)
            break
### BUGGY CODE ###

from math import sqrt
from math import ceil
N = int(input())
s = ceil(sqrt(N))
for i in range(1, N+1):
  count = 0
  for x in range(1,s+1):
    for y in range(1,s+1):
      for z in range(1,s+1):
        if (x**2 + y**2 + z**2 + x*y + y*z + x*z) == i:
          count += 1
  print(count)

### FIXED CODE ###

N = int(input())
arr = [0]*(N+2)
 
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            n = x**2 + y**2 + z**2 + x*y + x*z + y*z
            if n <= N :
                arr[n] += 1
 
for i in range(1,N+1):
    print(arr[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited = [0] * n
vmap = dict()
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

ans = []
def dfs(prev, n):
    if prev < n:
        if (prev, n) in vmap:
            return 0 
        else:
            vmap[(prev, n)] = 1
    else:
        if (n, prev) in vmap:
            return 0 
        else:
            vmap[(n, prev)] = 1
    child_num = 0
    for v in edge[n]:
        if prev == v:
            continue
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n, v])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n, prev])
        return 0

dfs(-1, 0)
for f, t in ans:
    print(f+1, t+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = [int(item) for item in input().split()]
if m % 2 != 0:
    print(-1)
    exit()
visited_e = [False] * m
visited_v = [False] * n
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append([b, i])
    edge[b].append([a, i])
 
ans = []
def dfs(prev, n):
    if visited_v[n]:
        return 1
    visited_v[n] = True
    child_num = 0
    for v, index in edge[n]:
        if visited_e[index]:
            continue
        visited_e[index] = True
        if dfs(n, v) == 1:
            child_num += 1
            ans.append([n+1, v+1])
    if child_num % 2 == 0:
        return 1
    else:
        ans.append([n+1, prev+1])
        return 0
 
dfs(-1, 0)
print("\n".join([str(f) + " " + str(t) for f, t in ans]))
### BUGGY CODE ###

import numpy as np

l,r = map(int, input().split())
 
seki = []
for j in range(r,l,-1):
    for i in range(j-1,l-1,-1):
        seki.append(i*j)

mod = np.array(seki) % 2019
print(mod.min())

### FIXED CODE ###

l,r = map(int, input().split())
n = r - l + 1
if 2019<=n:
    print(0)
elif 3<=n and n<2019:
    for k in range(l,r+1):
        if k%673==0:
            print(0)
            exit()

    mod = 2019
    for i in range(l,r):
        for j in range(l+1,r+1):
            mod_new = (i*j)%2019
            if mod_new == 1:
                print(1)
                exit()
            else:
                mod = min(mod,mod_new)
    print(mod)                             
else:
    print((l*r)%2019)
### BUGGY CODE ###

INF = float('inf')
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))
S = [0]*N
for i in range(N):
    S[i] = S[i-1]+A[i]

ans = INF
for i in range(2,N-1):
    l = S[:i]
    r = S[i:]
    j = bisect(l,l[-1]/2)
    k = bisect(r,(r[-1]+l[-1])/2)
    for p in {j-1,min(j,len(l)-2)}:
        for q in {k-1,min(k,len(r)-2)}:
            a,b,c,d = l[p],l[-1]-l[p],r[q]-l[-1],r[-1]-r[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

print(ans)


### FIXED CODE ###

INF = float('inf')
from bisect import bisect
N = int(input())
A = list(map(int,input().split()))
S = [0]*N
for i in range(N):
    S[i] = S[i-1]+A[i]

ans = INF
for i in range(2,N-1):
    j = bisect(S,S[i-1]/2)
    k = bisect(S,(S[-1]+S[i-1])/2)
    for p in {j-1,min(j,i-2)}:
        for q in {k-1,i,min(k,N-2)}:
            a,b,c,d = S[p],S[i-1]-S[p],S[q]-S[i-1],S[-1]-S[q]
            m = min(a,b,c,d)
            M = max(a,b,c,d)
            ans = min(ans,M-m)

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

import heapq

def h(l):
    heapq.heapify(l)
    return l[0]

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
for i in range(N-L+1) : ans.append(str(h(A[i:i+L])))
print(" ".join(ans))

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

from bisect import bisect_left

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

a.sort(reverse=True)
b = list(reversed(a))

rs = [0] * n
rs[0] = a[0]
for i, x in enumerate(a[1:]):
    rs[i+1] = rs[i] + x

L = 0
H = sum(a) ** 2 + 1

#print(b)

while H - L > 1:
    #print(L, H)
    M = (L + H) // 2
    count = 0
    for x in a:
       count += n - bisect_left(b, M - x)
    #print(L, H, count)
    if count == m:
        L = M
        break
    elif count > m:
        L = M
    else:
        H = M

ans = 0
count = 0
for x in a:
    c = n - 1 -  bisect_left(b, L - x)
    count += c + 1
    if c >= 0:
        ans += rs[c] + x * (c+1)

#print(L, count - m)

print(ans - (count-m) * L)

### FIXED CODE ###

from bisect import bisect_left

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

a.sort(reverse=True)
b = list(reversed(a))

rs = [0] * n
rs[0] = a[0]
for i, x in enumerate(a[1:]):
    rs[i+1] = rs[i] + x

L = a[-1] * 2
H = a[0] * 2

while H - L > 1:
    M = (L + H) // 2
    count = 0
    for x in a:
       count += n - bisect_left(b, M - x)
    if count == m:
        L = M
        break
    elif count > m:
        L = M
    else:
        H = M

ans = 0
count = 0
for x in a:
    c = n - 1 -  bisect_left(b, L - x)
    count += c + 1
    if c >= 0:
        ans += rs[c] + x * (c+1)

print(ans - (count-m) * L)
### BUGGY CODE ###

n = int(input())
p = [0 for i in range(n)]
for i in range(n):
    p[i] = int(input())

max_count = 1
for i in range(n):
    count = 1
    target = p[i] + 1
    for j in range(i + 1, n):
        if p[j] == target:
            count += 1
            target += 1
    if max_count<count:
        max_count=count
print(n-max_count)



### FIXED CODE ###

n = int(input())
p = [0 for i in range(n)]
for i in range(n):
    p[i] = int(input())

visited = [0 for i in range(n+1)]

"""
for i in reversed(range(n)):
    if visited[i] == 0:
        visited[i] = 1
        count = 1
        target = p[i] - 1

        for j in reversed(range(i)):
            if p[j] == target:
                count += 1
                visited[j] = count
                target -= 1
"""
for i in range(n):
    visited[p[i]] = visited[p[i] - 1] + 1
print(n - max(visited))
### BUGGY CODE ###

def binary_search(*, ok, ng, func):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    N, K = map(int, input().split())
    *A, = sorted(map(int, input().split()))
    *F, = sorted(map(int, input().split()), reverse=True)

    def is_ok(score):
        rest = K
        for a, f in zip(A, F):
            exceed = max(0, a * f - score)
            if exceed:
                need = (exceed + f - 1) // f
                if need > a or need > rest:
                    return False
                rest -= need
        return True

    ans = binary_search(ok=10 ** 12, ng=-1, func=is_ok)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()

# int(input())
# map(int, input().split())


from math import ceil


def is_ok(mid):
    remain = k
    for ff, aa in zip(f, a):
        if ff * aa > mid:
            x = ceil(aa - (mid / ff))
            if x <= aa and x <= remain:
                remain -= x
            else:
                return False
    return True


def bs():
    ng, ok = -1, 10 ** 12
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok


n, k = map(int, input().split())
a = tuple(sorted(map(int, input().split())))
f = tuple(sorted(map(int, input().split()), reverse=True))
print(bs())
### BUGGY CODE ###

n,m=map(int,input().split())
a = list(int(input()) for i in range(m))

INF=1000000007
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1

for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=INF

print(dp[n])

### FIXED CODE ###

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

INF=1000000007
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,n+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=INF
print(dp[n])
### BUGGY CODE ###

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1:
            x += 1
    ans += x * (n - x) * 2 ** i
    ans %= MOD
print(ans)

### FIXED CODE ###

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1:
            x += 1
    ans += x * (n - x) * 2 ** i
    ans %= MOD
print(ans)
### BUGGY CODE ###

N, L = map(int, input().split())
S = [input() for i in range(N)]

while True:
    t = 0
    for i in range(N - 1):
        #print("i = {}".format(i))
        for j in range(L):
            #print("j = {}".format(j))
            if S[i+1][j] < S[i][j]:
                #print(S[i][j])
                temp = S[i+1]
                S[i+1] = S[i]
                S[i] = temp

                t = 1
                
    #print(S)
    if t == 0:
        break
        
print(''.join(S))


### FIXED CODE ###

N, L = map(int, input().split())
S = [input() for i in range(N)]

print(''.join(sorted(S)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N, -1, -1):
        for j in range(W + 1):
            if i == N:
                try:
                    dp[j][i] = 0
                except IndexError:
                    print(j)
            else:
                if shina[i][0] > j:
                    dp[j][i] = dp[j][i + 1]
                else:
                    dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N, W = [int(x) for x in input().split()]
    shina = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        shina.append([a, b])

    dp = [[0 for i in range(N + 1)] for j in range(W + 1)]

    for i in range(N - 1, -1, -1):
        for j in range(W + 1):
            if shina[i][0] > j:
                dp[j][i] = dp[j][i + 1]
            else:
                dp[j][i] = max(dp[j][i + 1], dp[j - shina[i][0]][i + 1] + shina[i][1])

    ans = 0
    for j in range(W + 1):
        ans = max(ans, max(dp[j]))

    print(ans)


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

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, readline().split())
        G[u - 1].append(v - 1)
    S, T = map(int, readline().split())
    S -= 1
    T -= 1

    seen = [[False] * 4 for _ in range(N)]

    def dfs(G, v, step, seen):
        if step == 0:
            if v == T:
                return 0
            else:
                step = 3

        ans = INF
        for nv in G[v]:
            if seen[nv][step - 1]:
                continue
            seen[nv][step - 1] = True
            tmp = dfs(G, nv, step - 1, seen) + 1
            seen[nv][step - 1] = False
            if ans > tmp:
                ans = tmp

        return ans

    ans = dfs(G, S, 3, seen)
    if ans == INF:
        print(-1)
    else:
        print(ans // 3)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M = map(int, readline().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, readline().split())
        G[u - 1].append(v - 1)
    S, T = map(int, readline().split())
    S -= 1
    T -= 1

    dist = [[-1] * 3 for _ in range(N)]
    dist[S][0] = 0
    queue = deque([(S, 0)])
    while queue:
        v, step = queue.popleft()
        if step == 0 and v == T:
            break

        for nv in G[v]:
            if dist[nv][(step - 1) % 3] != -1:
                continue
            dist[nv][(step - 1) % 3] = dist[v][step] + 1
            queue.append((nv, (step - 1) % 3))

    if dist[T][0] == -1:
        print(-1)
    else:
        print(dist[T][0] // 3)
    return


if __name__ == '__main__':
    main()