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

from heapq import heappop, heappush, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()

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

    if x == y:
        return
    if parents[x] > parents[y]:
        x, y = y, x
    parents[x] += parents[y]
    parents[y] = x

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

N = int(input())

verticies_x = []
verticies_y = []

for i in range(N):
    x, y = map(int, input().split())
    verticies_x.append((x,i))
    verticies_y.append((y,i))
verticies_x.sort()    
verticies_y.sort()

edge = []

for i in range(N-1):
    tmp_x = verticies_x[i+1][0] - verticies_x[i][0]
    tmp_y = verticies_y[i+1][0] - verticies_y[i][0]
    heappush(edge, (tmp_x, verticies_x[i][1], verticies_x[i+1][1]))
    heappush(edge, (tmp_y, verticies_y[i][1], verticies_y[i+1][1]))

ans = 0
parents = [-1] * N
while edge:
    cost, s, g = heappop(edge)
    if same(s,g):      
        continue
    else:
        union(s,g)
        ans += cost
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

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

X.sort()
Y.sort()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()
parent=[-1]*N

ans=0
for l,a,b in edge:
    if find_parent(a)==find_parent(b):
        continue
    else:
        ans+=l
        connect(a,b)

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

def bubble(A, N):
    count = 0
    flag = True
    while flag == True:
        for j in range(N-1, 0, -1):
            flag = False
            if A[j] < A[j - 1]:
                A[j -1],A[j] = A[j], A[j - 1]
                count += 1
                flag = True
        print(" ".join(map(str, A)))
        print(count)

if __name__ == "__main__":
    N = int(input())
    A = [int(i) for i in input().split(" ")]
    print(bubble(A, N))

### FIXED CODE ###

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


def bubble_sort(A, N):
    cnt = 0
    flag = True
    while(flag):
        flag = False
        for i in range(N-1, 0, -1):
            if(A[i-1] > A[i]):
                A[i-1], A[i] = A[i], A[i-1]
                cnt += 1
                flag = True

    print(" ".join(list(map(str, A))))
    print(cnt)

bubble_sort(A, N)
### BUGGY CODE ###

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

if N == 1:
    print(1)
    exit()

def saisho_ko_baisu(A,B):
    # A < B
    if B < A:
        A,B = B,A
    x = A*B
    r = B%A
    while r!=0:
        B = A
        A = r
        r = B%A
    return x//A

A.sort(reverse = True)
tmp = saisho_ko_baisu(A[0], A[1])
for i in range(2,N):
    if tmp % A[i] != 0:
        tmp = saisho_ko_baisu(tmp, A[i])
res = 0
for a in A:
    res += tmp//a

print(res % (10**9 + 7))


### FIXED CODE ###

from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

div = 10**9 + 7
lcm_num = lcm(a)
ans = [lcm_num//ai for ai in a]

print(sum(ans)%div)
### BUGGY CODE ###

def main():
  MOD=10**9+7
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  import numpy as np
  A=np.array(A)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  MOD=10**9+7
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]
blacks = deque([])
for h in range(H):
  for w in range(W):
    if A[h][w] == "#":
      blacks.append((h, w))
ans = 0
for h in range(H):
  for w in range(W):
    if A[h][w] == ".":
      dist = 10000
      for b in blacks:
        dist = min(dist, abs(b[0]-h)+abs(b[1]-w))
        if dist == 1:
          break
      ans = max(dist, ans)
print(ans)



### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
blacks = deque([])
for h in range(H):
  for w in range(W):
    if A[h][w] == "#":
      blacks.append((h, w))
count = 0
while len(blacks) > 0:
  newblacks = deque([])
  while len(blacks) > 0:
    b = blacks.popleft()
    for y, x in zip((b[0]-1, b[0], b[0], b[0]+1), (b[1], b[1]-1, b[1]+1, b[1])):
      if y < 0 or y >= H or x < 0 or x >= W:
        continue
      if A[y][x] == ".":
        newblacks.append((y, x))
      A[y][x] = "#"
  blacks = newblacks
  count += 1
print(count-1)
### BUGGY CODE ###

#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def next_kenp(node, edges, dones):
    nodes = set()
    nodes2 = set()
    if node not in edges:
        return nodes

    for n1 in edges[node]:
        if n1 not in edges:
            continue
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)

    for nn in nodes2:
        if nn not in edges:
            continue
        for n3 in edges[nn]:
            if n3 in dones or n3 in nodes:
                continue
            nodes.add(n3)
    return nodes


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[u].append(v)

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

    dones = set()
    que = deque()
    que.append((s, 0))
    while que:
        node, step = que.popleft()
        next_nodes = next_kenp(node, edges, dones)
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

            if n not in dones:
                que.append((n, step + 1))
                dones.add(n)
    print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[(u, 0)].append((v, 1))
        edges[(u, 1)].append((v, 2))
        edges[(u, 2)].append((v, 0))

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

    # print(new_edges)

    dones = set()
    que = deque()
    que.append(((s, 0), 0))
    while que:
        node, step = que.popleft()

        next_nodes = edges[node]
        # print(next_nodes)
        for n, l in next_nodes:
            if n == t and l == 0:
                print((step + 1) // 3)
                exit()

            if (n, l) not in dones:
                que.append(((n, l), step + 1))
                dones.add((n, l))
    print(-1)


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

import numpy as np

H,W = map(int,input().split())
grid = [list(input()) for i in range(H)]
dp = np.zeros([H + 1,W + 1],dtype = int)
dp[0][0] = 1
mod = (10 ** 9) + 7

for i in range(H):
  for j in range(W):
    if i > 0 or j > 0:
      if grid[i][j] == "#":
        dp[i][j] = 0
      else:
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod

print(dp[H - 1][W - 1])

### FIXED CODE ###

import sys
import numpy as np
from functools import lru_cache
from collections import deque

#input = sys.stdin.readline
#sys.setrecursionlimit(10 ** 5)

H,W = map(int,input().split())
grid = [list(input()) for i in range(H)]
dp = [[0] * (W + 1) for i in range(H + 1)]
dp[0][0] = 1
mod = (10 ** 9) + 7

for i in range(H):
  for j in range(W):
    if i > 0 or j > 0:
      if grid[i][j] == "#":
        dp[i][j] = 0
      else:
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod

print(dp[H - 1][W - 1])
#print(dp)
### BUGGY CODE ###

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

# process
INF = 10**9
dp = [INF]*(H+max(a for a, _ in AB))
dp[0] = 0

for i in range(H):
    if dp[i] == INF:
        continue
    for a, b in AB:
        t = dp[i]+b
        if dp[i+a] > t:
            dp[i+a] = t

# output
print(min(dp[H:]))


### FIXED CODE ###

import numpy as np

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

AB = [list(map(int, input().split())) for _ in range(N)]
A, B = np.array(AB, dtype=np.int64).reshape(N, 2).T

# process
dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

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

# output
print(dp[H])
### BUGGY CODE ###

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

from fractions import gcd
lcm = c * d // gcd(c, d)

num = 0
for i in range(a, b+1):
    if i % c == 0:
        num += 1
    if i % d == 0:
        num += 1
    if i % lcm == 0:
        num -= 1

print(b - a + 1 - num)


### FIXED CODE ###

import fractions

a,b,c,d = map(int, input().split())
#print(a,b,c,d)
total = b-a+1
#print(total)
lcm = int(c*d / fractions.gcd(c,d))
#print(lcm)
x = (b//c) + (b//d) - (b//lcm)
y = ((a-1)//c) + ((a-1)//d) - ((a-1)//lcm)
#print(x,y)
print(total - (x - y))
### BUGGY CODE ###

n=int(input())
a=input().split()
ans=1

for i in a:
  ans*=int(i)
  
if ans>10**18:
  print("-1")
else:
  print(str(ans))

### FIXED CODE ###

n=int(input())
a=input().split()
ans=1

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

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

n = int(input())

a = []
for i in range(n): a.append(int(input()))

for i in range(n):
    big = 0
    for j in range(n):
        if j == i: continue
        big = max(big, a[j])
    print(big)

### FIXED CODE ###

n = int(input())

a = []
for i in range(n):
    a.append(int(input()))
rev_a = sorted(a, reverse=True)

for i in range(n):
    if rev_a[0] == a[i]: print(rev_a[1])
    else: print(rev_a[0])
### BUGGY CODE ###

#!/usr/bin/env python3


N = int(input())
A = [int(s) for s in input().split()]

ans = 1
for a in A:
    ans *= a

if ans > 10**18:
    print(-1)
else:
    print(ans)




### FIXED CODE ###

#!/usr/bin/env python3

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    for a in A:
        if a == 0:
            return 0
    ans = 1
    for a in A:
        ans *= a
        if ans > 10**18:
            return -1
    return ans

def main():
    print(solve())

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L = {}
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L:
    h.add(i+1,1)
    on.add(i+1)
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

for q in LOO:
  print(ans[q])

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L = {}
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L:
    h.add(i+1,1)
    on.add(i+1)
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

p = []
for q in LOO:
  p.append(ans[q])
  
print(*p, sep="\n")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = input()
n = len(s)
t = input()
m = len(t)

d = {}
for c in t:
    if c in d:
        continue
    else:
        d[c] = []
    for i in range(2*n):
        if s[i%n]==c:
            d[c].append(i)

res = -1
for i in range(m):
    c = t[i]
    if len(d[c])==0:
        print(-1)
        exit()

    j = 0
    while res%n>=d[c][j]:
        j += 1
    res += d[c][j] - res%n

print(res+1)


### FIXED CODE ###

# -*- coding: utf-8 -*-

def lower_bound(l,k):
    def isOk(i):
        return l[i]>k

    ok = len(l)
    ng = -1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2

        if isOk(mid):
            ok = mid
        else:
            ng = mid
    return ok

s = input()
n = len(s)
t = input()
m = len(t)

d = {}
for c in t:
    if c in d:
        continue
    else:
        d[c] = []
    for i in range(2*n):
        if s[i%n]==c:
            d[c].append(i)
res = -1
for i in range(m):
    c = t[i]
    if len(d[c])==0:
        print(-1)
        exit()

    j = lower_bound(d[c],res%n)
    res += d[c][j] - res%n

print(res+1)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
if K == 1:
    print(0)
    exit()
C = [[] for _ in range(K)]
m = 0
C[0].append(-1)
for i in range(N):
    m = (m + A[i] - 1) % K
    C[m].append(i)

ans = 0
for k in range(K):
    L = len(C[k])
    if L <= 1:
        continue
    l = r = 0
    while r < L:
        r = bisect_left(C[k], C[k][l]+K-1, l)
        if r == L:
            ans += (L-l)*(L-l-1)//2
        else:
            ans += r - l - 1
            if C[k][r] == C[k][l]+K-1:
                ans += 1
            l += 1
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
from collections import defaultdict
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
A = inpl()
if K == 1:
    print(0)
    exit()
C = defaultdict(list)
k_list = set()
m = 0
C[0].append(-1)
for i in range(N):
    m = (m + A[i] - 1) % K
    C[m].append(i)
    k_list.add(m)

ans = 0
for k in k_list:
    L = len(C[k])
    if L <= 1:
        continue
    l = r = 0
    while r < L:
        r = bisect_left(C[k], C[k][l]+K-1, l)
        if r == L:
            ans += (L-l)*(L-l-1)//2
        else:
            ans += r - l - 1
            if C[k][r] == C[k][l]+K-1:
                ans += 1
            l += 1
print(ans)
### BUGGY CODE ###

answer = []


def point_check(num):
    for i in A_dic.keys():
        A_dic[i] -= 1
    A_dic[num] += 1


N, K, Q = map(int, input().split())
A_dic = {i: K for i in range(1, N + 1)}

for j in range(Q):
    answer.append(int(input()))

for l in answer:
    point_check(l)
# print(A_dic)

for k in A_dic.values():
    if k <= 0:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

answer = []


def point_check(num):
    for i in A_dic.keys():
        A_dic[i] -= num


N, K, Q = map(int, input().split())
A_dic = {i: K for i in range(1, N + 1)}

for j in range(Q):
    answer.append(int(input()))

point_check(Q)

for l in answer:
    A_dic[l] += 1

for k in A_dic.values():
    if k <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

import collections
N=int(input())
lst=input().split()
s=0
dic=collections.Counter(lst)
for i in dic.values():
    s+=(i*i-i)//2
for i in lst:
    print(s+1-lst.count(i))

### FIXED CODE ###

import collections
N=int(input())
lst=input().split()
s=0
dic=collections.Counter(lst)
for i in dic.values():
    s+=(i*i-i)//2
for i in lst:
    print(s+1-dic[i])
### BUGGY CODE ###

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

sum=1
for i in range(N):
    sum*=A[i]

if sum>(10**18):
    print(int(-1))
else:
    print(int(sum))


### FIXED CODE ###

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


if 0 in A:
    sum=0
else:
    sum=1
    for i in range(N):
        sum *= A[i]
        if sum>(10**18):
            sum=-1
            break

print(int(sum))
### BUGGY CODE ###

from collections import deque

S = input()
num_of_query = int(input())
querys = []
for _ in range(num_of_query):
    querys.append(list(input().split()))

for query in querys:
    if query[0] == '1':
        S = S[::-1]
    else:
        if query[1] == '1':
            S = deque(S)
            S.appendleft(query[2])
            S = list(S)
        else:
            S = deque(S)
            S.append(query[2])
            S = list(S)

print(''.join(S))

### FIXED CODE ###

from collections import deque

S = deque(input())
num_of_query = int(input())
querys = []
is_reverse = False

for _ in range(num_of_query):
    # querys.append(list(input().split()))
    query = list(input().split())
    
    if query[0] == '1':
        is_reverse = not is_reverse
    else:
        if query[1] == '1':
            if is_reverse:
                S.append(query[2])
            else:
                S.appendleft(query[2])

        else:
            if is_reverse:
                S.appendleft(query[2])
            else:
                S.append(query[2])

S = list(S)
if is_reverse:
    S = S[::-1]

# for query in querys:
#     if query[0] == '1':
#         S = S[::-1]
#     else:
#         if query[1] == '1':
#             S = deque(S)
#             S.appendleft(query[2])
#             S = list(S)
#         else:
#             S = deque(S)
#             S.append(query[2])
#             S = list(S)

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

n = int(input())

nums = [0]*n
m = n//6
for i in range(1,m+1):
  if i**2//6 >= n: break
  for j in range(i, m+1):
    if i**2 + j**2 + i*j >= n//2: break
    for k in range(j, m+1):
      t = i**2 + j**2 + k**2 + i*j + j*k + i*k
      if t <= n:
        if i == j and i == k: nums[t-1] += 1
        else: nums[t-1] += 3
        
print(*nums, sep="\n")

### FIXED CODE ###

from itertools import product
n = int(input())

nums = [0]*(n+1)
for i in product(range(1, int(n**0.5)+1),repeat=3):
  t = i[0]**2 + i[1]**2 + i[2]**2 + i[0]*i[1] + i[1]*i[2] + i[0]*i[2]
  if t <= n: nums[t] += 1

for i in range(1,n+1): print(nums[i])
### BUGGY CODE ###

import math
from itertools import accumulate
from collections import Counter
import itertools


N = int(input())

strings = []
for i in range(N):
    strings.append(input())


def is_anagrams(t1, t2):
    c1 = Counter(t1)
    c2 = Counter(t2)
    if sorted(c1.values()) == sorted(c2.values()) and sorted(c1.keys()) == sorted(c2.keys()):
        return 1
    else:
        return 0



count = 0
for t1, t2 in list(itertools.combinations(strings, 2)):
    count += is_anagrams(t1, t2)
print(count)

### FIXED CODE ###

import math
from itertools import accumulate
from collections import Counter
import itertools
import functools


N = int(input())

strings = []
for i in range(N):
    strings.append(input())


strings = [''.join(sorted(i)) for i in strings]
c = Counter(strings)
count = 0
for i in c.values():
    if i > 1:
        count += (i * (i - 1)) / 2
print(int(count))
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    

    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in set(roots[now]):
                    purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    layers = [set() for _ in range(3)]
    
    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    if root not in layers[i]:
                        layers[i].add(root)
                        purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()