Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G.
G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.
First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.
Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.

-----Constraints-----
 - 2 \leq N \leq 10^5
 - 0 \leq M \leq \min(10^5, N (N-1))
 - 1 \leq u_i, v_i \leq N(1 \leq i \leq M)
 - u_i \neq v_i (1 \leq i \leq M)
 - If i \neq j, (u_i, v_i) \neq (u_j, v_j).
 - 1 \leq S, T \leq N
 - S \neq T

-----Input-----
Input is given from Standard Input in the following format:
N M
u_1 v_1
:
u_M v_M
S T

-----Output-----
If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1.
If he can, print the minimum number of ken-ken-pa needed to reach vertex T.

-----Sample Input-----
4 4
1 2
2 3
3 4
4 1
1 3

-----Sample Output-----
2

Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.

Difficulty: interview

Starter code:

Solutions:
from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy

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

data=[[] for i in range(N+1)]
for u,v in UV:
    data[u].append(v)

visited={S}
visited1=set()
visited2=set()
stack=deque([[S,0]])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        z=(m+1)

        if z%3==0:
            if p in visited:
                continue
            elif p == T:
                print((z//3))
                return
            else:
                visited.add(p)
        if z%3==1:
            if p in visited1:
                continue
            else:
                visited1.add(p)
        if z%3==2:
            if p in visited2:
                continue
            else:
                visited2.add(p)
        stack.append([p,z])

print((-1))


import copy
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
graph = [[] for i in range(n+1)]
for i in range(m):
    u, v = map(int,input().split())
    graph[u].append(v)
s, g = map(int,input().split())

INF = 10**7
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

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 = list(map(int, readline().split()))
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v = list(map(int, readline().split()))
        G[u - 1].append(v - 1)
    S, T = list(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


def __starting_point():
    main()

__starting_point()

import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: list(map(int, sys.stdin.readline().split()))
na = lambda: list(map(int, sys.stdin.readline().split()))
nb = lambda: list([int(x) - 1 for x in sys.stdin.readline().split()])


# ===CODE===


def main():
    n, m = ns()
    e = [[] for _ in range(n)]
    for _ in range(m):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)

    s, t = ns()
    s, t = s - 1, t - 1

    visited = [[True] * 3 for _ in range(n)]

    que = collections.deque()
    que.append([0, s])
    visited[s][0] = False
    cnt = 0
    ans = -1
    flg = True

    while que and flg:
        cnt += 1
        for _ in range(len(que)):
            i, q = que.popleft()
            for ei in e[q]:
                tmp = (i + 1) % 3
                if tmp == 0 and ei == t:
                    ans = cnt // 3
                    flg = False
                    break
                elif visited[ei][tmp]:
                    visited[ei][tmp] = False
                    que.append([tmp, ei])

    print(ans)


def __starting_point():
    main()

__starting_point()

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

n, m = list(map(int, readline().split()))
graph = [[] for _ in range(n * 3)]
for i in range(m):
    u, v = list(map(int, readline().split()))
    u -= 1
    v -= 1
    graph[u].append(v + n)
    graph[u + n].append(v + 2 * n)
    graph[u + 2 * n].append(v)
s, t = [int(x) - 1 for x in readline().split()]
inf = float('inf')
q = deque([s])
dist = [inf] * (3 * n)
dist[s] = 0

while q:
    now = q.popleft()
    for next in graph[now]:
        if dist[next] != inf:
            continue
        dist[next] = dist[now] + 1
        if next == t:
            print((dist[next] // 3))
            return
        q.append(next)
print((-1))


import sys
from collections import deque

sys.setrecursionlimit(10000000)

n,m = map(int,input().split())
to=[[] for _ in range(n)]
dist=[[0] *3 for _ in range(100005)]
INF=10**15

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

sv,tv=map(int,input().split())
sv-=1;tv-=1

for i in range(n):
    for j in range(3):
        dist[i][j] =INF

q=deque()
q.append((sv,0))
dist[sv][0]=0

while q:
    v,l=q.popleft()
    for u in to[v]:
        nl =(l+1)%3
        if dist[u][nl] != INF: continue
        dist[u][nl] = dist[v][l]+1
        q.append((u,nl))

ans=dist[tv][0]
if ans == INF:ans=-1
else: ans //=3
print(ans)

from collections import deque
n,m = map(int,input().split())
G = [[[] for _ in range(3)] for _ in range(n)]
for _ in range(m):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    G[u][0].append((v,1))
    G[u][1].append((v,2))
    G[u][2].append((v,0))
s,t = map(int,input().split())
s -= 1
t -= 1

dist = [[-1]*3 for _ in range(n)]
dist[s][0] = 0
Q = deque([(s,0)])
while Q:
    now,r = Q.popleft()
    for nxt,nr in G[now][r]:
        if dist[nxt][nr] != -1: continue
        dist[nxt][nr] = dist[now][r]
        if r == 2: dist[nxt][nr] += 1
        Q.append((nxt,nr))
# print(dist)
print(dist[t][0])

import sys
sys.setrecursionlimit(10**6)
from collections import deque
n,m=map(int,input().split())
edges=[[] for i in range(n)]
for i in range(m):
    u,v=map(int,input().split())
    edges[u-1].append(v-1)
s,t=map(int,input().split())
inf=100000000000
score=[[inf]*3 for i in range(n)]
now=deque()
now.append(s-1)
score[s-1][0]=0
def bfs(dep,l):
    nonlocal n,m,edges,s,t,score,inf,now
    f=False
    for i in range(l):
        ne=now.popleft()
        for j in edges[ne]:
            if score[j][dep%3]==inf:
                score[j][dep%3]=dep
                now.append(j)
    l_ne=len(now)
    if l_ne:bfs(dep+1,l_ne)
bfs(1,1)
if score[t-1][0]!=inf:
    print(score[t-1][0]//3)
else:
    print(-1)

n,m = map(int,input().split())
path = [[[],[],[]] for i in range(n)]

gone = [[0]*3 for i in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    path[u-1][0].append([v-1,1])
    path[u-1][1].append([v-1,2])
    path[u-1][2].append([v-1,0])

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

now = [[s-1,0]]
gone[s-1][0] = 1
for ans in range(1,1000000):
    next = []
    for point,key in now:
        for go,gokey in path[point][key]:
            if go == t-1 and gokey == 0:
                print(ans//3)
                return
            if gone[go][gokey] == 0:
                gone[go][gokey] = 1
                next.append([go,gokey])
    now = next
  #     print(now)
print(-1)

from collections import deque

def bfs(s, t):
    dist = [-1] * (3 * n + 1)
    q = deque()
    q.append(s)
    dist[s] = 0
    while q:
        p = q.popleft()
        for i in G[p]:
            if dist[i] == -1:
                dist[i] = dist[p] + 1
                q.append(i)
    return dist[t]

n, m = map(int, input().split())
G = [[] for _ in range(3 * n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    G[u].append(v + n)
    G[u + n].append(v + 2 * n)
    G[u + 2 * n].append(v)
s, t = map(int, input().split())
ans = bfs(s, t)
print(ans // 3 if not ans == -1 else ans)

from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = list(map(int, readline().split()))
UV = [[int(x) for x in readline().split()] for _ in range(M)]
S, T = list(map(int, readline().split()))

PATH = [[] for _ in range(N + 1)]

for u, v in UV:
    PATH[u].append(v)

dist = [[-1] * 3 for _ in range(N+1)]

q = deque()
q.append((S, 0))
dist[S][0] = 0

while q:
    u, mod = q.popleft()
    d = dist[u][mod]

    nmod = (mod + 1) % 3
    for v in PATH[u]:
        if dist[v][nmod] != -1:
            continue
        dist[v][nmod] = d + 1
        q.append((v, nmod))


if dist[T][0] == -1:
    ans = -1
else:
    ans = dist[T][0] // 3

print(ans)


import sys
input = sys.stdin.readline
N,M = map(int,input().split())
UV = [tuple(map(int,input().split())) for i in range(M)]
S,T = map(int,input().split())
S,T = S-1,T-1

es = [[] for _ in range(N*3)]
for u,v in UV:
    u,v = u-1,v-1
    es[u].append(v+N)
    es[u+N].append(v+N+N)
    es[u+N+N].append(v)

from collections import deque
q = deque([S])
INF = float('inf')
dist = [INF] * (N*3)
dist[S] = 0
while q:
    v = q.popleft()
    for to in es[v]:
        if dist[to] <= dist[v]+1: continue
        dist[to] = dist[v]+1
        q.append(to)
        if to==T:
            print(dist[to] // 3)
            return
print(-1)

from collections import deque
N, M = map(int, input().split())
INF = -1
dist = [[INF]*3 for _ in range(N)]
vector = [[] for _ in range(N)]

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1].append(graf2-1)
S, T = map(int, input().split())
S, T = S-1, T-1

# BFS
dist[S][0] = 0
q = deque()
q.append((S, 0))
while q:
    v, l = q.popleft()
    for i in vector[v]:
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        q.append((i, new_l))

ans = dist[T][0]
if ans == INF:
    print("-1")
else:
    print(int(ans/3))

from heapq import heappop, heappush
N, M = list(map(int, input().split()))
#3 * i
edge = [[] for i in range(3 * N)]
for i in range(M):
  u, v = list(map(int, input().split()))
  u, v = u - 1, v - 1
  edge[3 * u].append(3 * v + 1)
  edge[3 * u + 1].append(3 * v + 2)
  edge[3 * u + 2].append(3 * v)
  
S, T = list(map(int, input().split()))  
S, T = S - 1, T - 1
#print(edge)

used = [0] * (3 * N)
queue = [[0, 3 * S]]
used[3 * S] = 1
while queue:
  time, now = heappop(queue)
  for i in edge[now]:
    if (i == 3 * T):
      print((int((time + 1) / 3)))
      return
    elif used[i] == 0:
      used[i] = 1
      heappush(queue, [time + 1, i])
    
    
print((-1))  
  
  
  




  


from heapq import heappush, heappop
import sys
input = sys.stdin.readline

INF = float('inf')

N, M = list(map(int, input().split()))
adjL = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = list(map(int, input().split()))
    u, v = u-1, v-1
    adjL[3*u+0].append(3*v+1)
    adjL[3*u+1].append(3*v+2)
    adjL[3*u+2].append(3*v+0)
S, T = list(map(int, input().split()))
S, T = S-1, T-1

# 単一始点最短経路を求める（Dijkstra法）
def Dijkstra(adjList, vSt):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2 in adjList[vNow]:
            c2 = cNow + 1
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))
    return costs

costs = Dijkstra(adjL, 3*S)
#print('costs:', costs)

if costs[3*T] == INF:
    print((-1))
else:
    print((costs[3*T]//3))


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

N3=N*3
adj=[set() for _ in range(N3)]

for a,b in edges:
    for i in range(3):
        start = a+N*i
        dst = b+N*(i+1)
        adj[start%N3].add(dst%N3)


Q=[S]
visited={S}
dist=[-1]*N3
dist[S]=0

while Q:
    tmp=[]
    for q in Q:
        for i in adj[q]:
            if i in visited:
                continue
            else:
                dist[i]=dist[q]+1
                visited.add(i)
                tmp.append(i)
    Q = tmp
print((dist[T] if dist[T]==-1 else dist[T]//3))



def bfs(g, N, s, t):
    from collections import deque

    dist = [-1] * (N * 3)
    dist[s] = 0

    dq = deque()
    dq.append(s)

    while dq:
        v = dq.popleft()
        d = dist[v]
        for u in g[v]:
            if ~dist[u]: continue
            dist[u] = d + 1
            if u == t:
                return dist[t] // 3  # TLEしたので解を見つけたら即returnに変えた
            dq.append(u)
    return -1


def main():
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v + N)
        g[u + N].add(v + N * 2)
        g[u + N * 2].add(v)

    S, T = (int(x) - 1 for x in input().split())

    ans = bfs(g, N, S, T)

    print(ans)


def __starting_point():
    main()

__starting_point()

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

# 双方向グラフで幅優先探索

from collections import deque

n, m = list(map(int, input().split()))
g = [set([]) for _ in range(n)]
#隣接リストの作成
for i in range(m):
    a, b = list(map(int, input().split()))
    a, b = a-1, b-1
    g[a].add(b)

s, t = list(map(int, input().split()))
s, t = s-1, t-1

#幅優先探索
q = deque()
level = [[-1]*n for i in range(3)]
q.append((s, 0))
level[0][s] = 0
while len(q)>0:
    cur, lvl = q.popleft()
    nxtl = lvl + 1
    nxthp = nxtl%3
    for i in g[cur]:
        if level[nxthp][i]==-1:
            #階層
            level[nxthp][i] = nxtl
            q.append((i, nxtl))
print((level[0][t]//3))


# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
input = sys.stdin.readline
N,M = list(map(int,input().split()))
if M == 0:
  print((-1))
  return
edge = [[] for _ in range(N+1)]
for _ in range(M):
  u,v = list(map(int,input().split()))
  edge[u].append(v)
S,T = list(map(int,input().split()))

INF = 10 ** 9
dist = [[INF,INF,INF] for _ in range(N+1)]

d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in edge[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq

d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)


import sys
from collections import deque

input = sys.stdin.buffer.readline
int1 = lambda x: int(x) - 1

N, M = list(map(int, input().split()))
G = [[] for _ in range(3 * N)]
for _ in range(M):
    u, v = list(map(int1, input().split()))
    G[u * 3].append(v * 3 + 1)
    G[u * 3 + 1].append(v * 3 + 2)
    G[u * 3 + 2].append(v * 3)

S, T = list(map(int1, input().split()))
S *= 3
T *= 3

# bfs
d = deque([S])
distance = [0] * (3 * N)
while d:
    v = d.popleft()
    dist_v = distance[v]
    if v == T:
        print((dist_v // 3))
        return
    for x in G[v]:
        if not distance[x]:
            d.append(x)
            distance[x] = dist_v + 1
print((-1))


from collections import deque 
MOD = 10**9 +7
INF = 10**9
def main():
    n,m = list(map(int,input().split()))
    V0 = [[] for _ in range(n)]
    V1 = [[] for _ in range(n)]
    V2 = [[] for _ in range(n)]
    for _ in range(m):
        u,v = list(map(int,input().split()))
        u -= 1
        v -= 1
        V0[u].append(v)
        V1[u].append(v)
        V2[u].append(v)
    
    s,t = list(map(int,input().split()))
    s -= 1
    t -= 1
    
    d0 = [-1]*n
    d1 = [-1]*n
    d2 = [-1]*n
    d0[s] = 0

    q = deque()
    q.append((s,0))
    while len(q):
        v,mod = q.popleft()
        if mod == 0:
            for e in V0[v]:
                if d1[e] == -1:
                    d1[e] = d0[v] + 1
                    q.append([e,1])

        elif mod == 1:
            for e in V1[v]:
                if d2[e] == -1:
                    d2[e] = d1[v] + 1
                    q.append([e,2])
        
        else:
            for e in V2[v]:
                if e == t:
                    print(((d2[v] + 1)//3))
                    return           
                if d0[e] == -1:
                    d0[e] = d2[v] + 1
                    q.append([e,0])
    
    if d0[t] == -1:
        print((-1))
   
def __starting_point():
    main()

__starting_point()

from collections import deque
n,m=map(int,input().split())
G=[[] for i in range(3*n)]
for i in range(m):
  u,v=map(int,input().split())
  for j in range(3):
    G[u+n*j-1].append(v+n*((j+1)%3)-1)
s,g=map(int,input().split())
s=s-1
g=g-1
D=deque([s])
V=[0]*3*n
V[s]=1
DD=[0]*3*n
while len(D)>0:
  x=D[0]
  D.popleft()
  for y in G[x]:
    if V[y]==0:
      V[y]=1
      D.append(y)
      DD[y]=DD[x]+1
if DD[g]==0:
  print(-1)
else:
  print(DD[g]//3)

from collections import deque
import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))
UV = [[]for _ in range(n)]
for _ in range(m):
    u, v = list([int(x)-1 for x in input().split()])
    UV[u].append(v)
s, t = list([int(x)-1 for x in input().split()])

NV = 3*n
edges = [[]for _ in range(NV)]


def to_v(i, j):
    return 3*i+j


for i in range(n):
    for i2 in UV[i]:
        for j in range(3):
            edges[to_v(i, j)].append(to_v(i2, (j+1) % 3))

init_v = to_v(s, 0)
INF = 10**18
dist = [INF]*NV
dist[init_v] = 0
next_v = deque([init_v])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)

print((dist[to_v(t, 0)]//3 if dist[to_v(t, 0)] != INF else -1))


from collections import deque

def main():

  n,m=map(int,input().split())
  INF=10**9
  d=[[INF]*3 for i in range(n)]
  to=[[] for i in range(n)]
  for i in range(m):
    u,v=map(lambda x:int(x)-1,input().split())
    to[u].append(v)
  s,t=map(lambda x:int(x)-1,input().split())

  #print(to)
  # calc d (after 3 times dist)
  d[s][0]=0
  cnt=0
  q=deque([(s,cnt)])
  while q:
    u,c=q.popleft()
    for v in to[u]:
      nc=(c+1)%3
      if d[v][nc]!=INF: continue;
      d[v][nc]=d[u][c]+1
      q.append((v,nc))
      
  #print(d)
  ans=d[t][0]
  print(ans//3 if ans!=INF else -1)

  
def __starting_point():
  main()
__starting_point()

import sys
input = sys.stdin.readline
def MI():
  return map(int,input().split())
def main():
  n,m=MI()
  G=[[] for _ in range(n)]
  for _ in range(m):
    u,v=MI()
    u-=1
    v-=1
    G[u].append(v)
  s,t=MI()
  s-=1
  t-=1
  
  fi=[True]*n
  se=[True]*n
  th=[True]*n
  th[s]=False

  dq=[s]
  depth=0
  
  while dq:
    depth+=1
    tank1=[]
    tank2=[]
    tank3=[]
    
    for p in dq:
      for c in G[p]:
        if fi[c]:
          fi[c]=False
          tank2.append(c)
    for p in tank2:
      for c in G[p]:
        if se[c]:
          se[c]=False
          tank3.append(c)
    for p in tank3:
      for c in G[p]:
        if th[c]:
          th[c]=False
          tank1.append(c)
        if c==t:
          print(depth)
          return
    dq=tank1
  print(-1)  
def __starting_point():
  main()
__starting_point()

from collections import deque

n, m = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = list(map(int, input().split()))

N = 3 * (n + 1)
adj = [[] for _ in range(N)]
for u, v in uv:
    for i in range(3):
        uu = u + i * n
        vv = v + ((i + 1) % 3) * n
        adj[uu].append(vv)

dq = deque([s])
d = [-1] * N
d[s] = 0
while dq:
    u = dq.popleft()
    for v in adj[u]:
        if d[v] == -1:
            d[v] = d[u] + 1
            dq.append(v)

ans = d[t] // 3
print(ans)


from sys import stdin
from collections import deque


def input():
    return stdin.readline().strip()


def bfs():
    q = deque([(S, 0)])
    dist = [[-1] * 3 for _ in range(N)]
    dist[S][0] = 0
    while q:
        v, r = q.popleft()
        for nv in g[v]:
            nr = (r + 1) % 3
            if dist[nv][nr] >= 0:
                continue
            dist[nv][nr] = dist[v][r] + 1
            q.append((nv, nr))
    return dist[T][0] // 3


N, M = list(map(int, input().split()))
g = [[] for _ in range(3 * N)]
for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    g[a].append(b)
S, T = [int(x) - 1 for x in input().split()]
print((bfs()))


from collections import deque

n, m = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = list(map(int, input().split()))

adj = [[] for _ in range(3 * n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v + n)
    adj[u + n].append(v + 2 * n)
    adj[u + 2 * n].append(v)


def bfs(s):
    q = deque([s])
    d = [-1] * (3 * n)
    d[s] = 0
    while q:
        u = q.popleft()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                q.append(v)

    return d


dist = bfs(s - 1)
ans = dist[t - 1]
print((ans // 3))


import sys

input = sys.stdin.readline
n,m = list(map(int,input().split()))
from collections import defaultdict
dic = defaultdict(list)

for _ in range(m):
    u,v = list(map(int,input().split()))
    dic[u-1].append(v-1+n)
    dic[u - 1+n].append(v - 1 + 2*n)
    dic[u - 1+2*n].append(v - 1)

G = dic
s,t = list(map(int,input().split()))

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*(n*3)
que = deque([s-1])
dist[s-1] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)
print((dist[t-1]//3))



n,m=map(int,input().split())
u=[]
v=[]
g=[[] for _ in range(n)]

for i in range(m):
    uu,vv=map(int,input().split())
    u.append(uu)
    v.append(vv)
    g[uu-1].append(vv-1)
    
s,t=map(int,input().split())
s-=1
t-=1

from collections import deque
 
def bfs(u):
    queue1 = deque([u])
    queue2 = deque([0])
    d=[]
    for i in range(n):
        d.append([-1]*3)
    d[u][0]=0
    while queue1:
        v=queue1.popleft()
        l=queue2.popleft()
        nl=(l+1)%3
        for i in g[v]:
            if d[i][nl] is -1:
                d[i][nl]=d[v][l]+1
                queue1.append(i)
                queue2.append(nl)
    return d

d=bfs(s)

ans=int(d[t][0]/3)
if d[t][0]==-1:
    ans=-1
print(ans)

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, M: int, G, S: int, T: int):
    S -= 1
    T -= 1
    now = deque([S])
    dist = [0 for _ in range(N * 3)]
    while now:
        p = now.popleft()
        for n in G[p]:
            if dist[n] != 0:
                continue
            dist[n] = dist[p] + 1
            if n == T:
                print((dist[n] // 3))
                return
            now.append(n)
    print((-1))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    G = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = int(next(tokens)) - 1, int(next(tokens))-1
        G[u].add(v + N)
        G[u + N].add(v + 2 * N)
        G[u + 2 * N].add(v)

    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, G, S, T)

def __starting_point():
    main()

__starting_point()

from collections import defaultdict, deque


def kenkenpa(s, visited):
    res = []
    for v1 in e[s]:
        if visited[v1][1]:
            continue
        visited[v1][1] = True
        for v2 in e[v1]:
            if visited[v2][2]:
                continue
            visited[v2][2] = True
            for v3 in e[v2]:
                if visited[v3][0]:
                    continue
                visited[v3][0] = True
                res.append(v3)
    return res


N, M = list(map(int, input().split()))
e = defaultdict(list)
for i in range(M):
    u, v = list(map(int, input().split()))
    e[u].append(v)

S, T = list(map(int, input().split()))
q = deque([[S, 0]])
visited = [[False]*3 for _ in range(N+1)]
visited[S][0] = True
ans = -1
while q:
    u, c = q.popleft()
    if u == T:
        ans = c
        break
    l = kenkenpa(u, visited)
    for v in l:
        q.append([v, c+1])
print(ans)


n,m=map(int,input().split())
G=[[] for i in range(n)]
for i in range(m):
  u,v=map(int,input().split())
  G[u-1].append(v-1)

s,t=map(int,input().split())
s-=1
t-=1
from collections import deque
dist=[[-1]*3 for i in range(n)]
dist[s][0]=0
q=deque()
q.append([s,0])
while q:
  cur,parity=q.popleft()
  for nx in G[cur]:
    nx_parity=(parity+1)%3
    if dist[nx][nx_parity]==-1:
      dist[nx][nx_parity]=dist[cur][parity]+1
      q.append([nx,nx_parity])
if dist[t][0]==-1:
  print(-1)
else:
  print(int(dist[t][0]//3))

import sys
from collections import deque

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  roads0 = [[] for _ in range(n)]
  roads1 = [[] for _ in range(n)]
  roads2 = [[] for _ in range(n)]
  
  for i in range(m):
    u, v = map(int, input().split())
    roads0[u-1].append(v-1)
    roads1[u-1].append(v-1)
    roads2[u-1].append(v-1)
  

  s, t = map(int, input().split())
  not_yet = deque([])
  already = [[False]*3 for _ in range(n)]
  dist = [[0]*3 for _ in range(n)]
  for v in roads0[s-1]:
    not_yet.append((v, 1))
    dist[v][1] = 1
    already[v][1] = True
  already[s-1][0] = True
  while not_yet:
    key = not_yet.popleft()
    k1, k2 = key[0], key[1]
    if k2 == 0:
      for v in roads1[k1]:
        if already[v][1]:
          continue
        dist[v][1] = dist[k1][0]+1
        already[v][1] = True
        not_yet.append((v, 1))
    elif k2 == 1:
      for v in roads2[k1]:
        if already[v][2]:
          continue
        dist[v][2] = dist[k1][1]+1
        already[v][2] = True
        not_yet.append((v, 2))
    else:
      for v in roads0[k1]:
        if already[v][0]:
          continue
        dist[v][0] = dist[k1][2]+1
        already[v][0] = True
        not_yet.append((v, 0))
  if already[t-1][0]:
    print(dist[t-1][0]//3)
  else:
    print(-1)
  
    
def __starting_point():
  main()
__starting_point()

from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u-1].append(v-1)
s, t = map(int, input().split())
s -= 1
t -= 1
q = deque([s])
INF = 10**10
dist = [[INF]*3 for _ in range(n)]
dist[s][0] = 0
while q:
    node = q.popleft()
    for c_node in graph[node]:
        flg = False
        for i in range(3):
            nd = dist[node][i]+1
            if dist[c_node][nd%3] > nd:
                dist[c_node][nd%3] = nd
                flg = True
        if flg:
            q.append(c_node)
if dist[t][0]==INF:
    print(-1)
else:
    print(dist[t][0]//3)

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# vertexごとに3つの状態数を持つ
N, M = lr()
graph = [[] for _ in range((N+1)*3)]  # 1-indexed
for _ in range(M):
    a, b = lr()
    a *= 3; b *= 3
    for i in range(3):
        j = i+1 if i < 2 else 0
        graph[a+i].append(b+j)

INF = 10 ** 15

def dijkstra(start):
    dist = [INF] * (N+1) * 3
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

S, T = lr()
dist = dijkstra(S*3)
answer = dist[T*3]
if answer == INF:
    answer = -1
else:
    answer //= 3
print(answer)


from collections import deque

N,M,*f = map(int, open(0).read().split())
uv = [f[i:i+2] for i in range(0, len(f)-2, 2)]
S = f[-2]
T = f[-1]
connected = [[] for _ in range(N+1)]
for u, v in uv:
    connected[u].append(v)
dist = [[-1] * 3 for _ in range(N+1)]
dist[S][0] = 0
ans = 0
d = deque([(S,0)])
while d:
    temp = d.popleft()
    for edge in connected[temp[0]]:
        if edge == T and temp[1] == 2:
            print((dist[temp[0]][2]+1)//3)
            break
        else:
            if dist[edge][(temp[1]+1)%3] < 0:
                dist[edge][(temp[1]+1)%3] = dist[temp[0]][temp[1]] + 1
                d.append((edge,(temp[1]+1)%3))
    else:
        continue
    break
else:
    print(-1)

N,M=map(int,input().split())
A=[[]for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  A[a-1].append(b-1)
S,T=map(int,input().split())  
from collections import deque
import sys
sys.setrecursionlimit(10**7) #再帰制限のとっぱらい
D=[[-1]*3 for i in range(N)]
def bfs(x,n):
  q=deque()
  q.append((x,n)) 
  while len(q):
    x,n=q.popleft()
    for i in A[x]:
      d=(n+1)%3
      if D[i][d]==-1:
        D[i][d]=D[x][n]+1
        q.append((i,d))
D[S-1][0]=0
bfs(S-1,0)
if D[T-1][0]==-1:
  print(-1)
else:
  print(D[T-1][0]//3)

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

import heapq

INF = float('inf')

def dijkstra(graph, st):
    n  = len(graph)
    ds = [INF]*n
    ds[st] = 0
    prevs = [None]*n
    
    qs = [(0, st)]

    while len(qs) > 0:
        d, nodeId = heapq.heappop(qs)
        
        if d > ds[nodeId]:
            continue
        
        for destId, length in graph[nodeId]:
            d2 = d + length
            if ds[destId] > d2:
                ds[destId] = d2
                prevs[destId] = nodeId
                heapq.heappush(qs, (d2, destId))
                
    return (ds, prevs)


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

for _ in range(M):
    u, v = list(map(int, input().split()))
    
    for i in range(3):
        G[u*3 - 3 + i].append((v*3-3 + (i+1)%3, 1))


S, T = list(map(int, input().split()))
ds, prevs = dijkstra(G, S*3-3)

ans = ds[T*3-3]
print((ans//3 if ans != INF else -1))


from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())
dijkstra = Dijkstra(3 * N)
for a, b in edges:
    a, b = a - 1, b - 1
    dijkstra.add_edge(a, N + b, 0)
    dijkstra.add_edge(N + a, 2 * N + b, 0)
    dijkstra.add_edge(2 * N + a, b, 1)
ans = dijkstra.distance(S - 1)[T - 1]
print(ans if ans != float('inf') else -1)

import heapq

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

L=[[]    for i in range(3*N)]

for i in range(M):
  u,v=list(map(int,input().split()))
  u,v=u-1,v-1
  L[u].append(N+v)
  L[N+u].append(2*N+v)
  L[2*N+u].append(v)

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

D=[10**6 for i in range(3*N)]
D[~-S]=0
A=[(0,~-S)]
heapq.heapify(A)

while len(A)>0:
  d,v=heapq.heappop(A)
  if D[v]<d:
    continue
  for i in L[v]:
    if D[i]>D[v]+1:
      D[i]=D[v]+1
      heapq.heappush(A,(D[v]+1, i))

print((D[~-T]//3 if D[~-T]!=10**6 else -1))


N,M=list(map(int,input().split()))
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=list(map(int,input().split()))
    tree[u-1].append(v-1)
S,T=list(map(int,input().split()))
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=[]
q.append([s,0])
while q:
    v,c=q.pop(0)
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]=1
print(ans)


N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    ta, tb = map(int, input().split())
    E[ta-1].append(tb-1)
S, T = map(int, input().split())
S -= 1
T -= 1

INF = float('inf')
dist = [[INF] * N for _ in range(3)]
dist[0][S] = 0
q = [[S,0]]

while q:
    cp, cd = q.pop(0)
    nd = (cd + 1) % 3
    for np in E[cp]:
        if dist[nd][np] != INF:
            continue
        else:
            dist[nd][np] = dist[cd][cp] + 1
            q.append([np,nd])

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

import copy

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

INF = 10**11
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

import heapq
INF = 10 ** 10


def dijkstra(n, adj, s, t):
    dist = [INF for _ in range(n)]
    dist[s] = 0
    h = [(0, s)]
    while len(h) > 0:
        d, node = heapq.heappop(h)
        for next_node in adj[node]:
            next_d = d + 1
            if next_d < dist[next_node]:
                dist[next_node] = next_d
                heapq.heappush(h, (next_d, next_node))
    return dist[t]


def main():
    N, M = list(map(int, input().split(' ')))
    adj = [[] for _ in range(3 * N)]
    for _ in range(M):
        u, v = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[3 * u].append(3 * v + 1)
        adj[3 * u + 1].append(3 * v + 2)
        adj[3 * u + 2].append(3 * v)
    S, T = list(map(lambda x: int(x) - 1, input().split(' ')))
    d = dijkstra(3 * N, adj, 3 * S, 3 * T)
    if d == INF:
        print(-1)
    else:
        print(d // 3)


def __starting_point():
    main()
__starting_point()

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

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


INF = N*3

dist = [[INF]*3 for _ in range(N)]

dist[S][0] = 0

q = [(0,S)]

while q:
    d, vs = heapq.heappop(q)
    if d > dist[vs][d%3]: continue
    
    for ve in edge[vs]:
        lev = (d+1)%3
        if d+1 < dist[ve][lev]:
            dist[ve][lev] = d+1
            heapq.heappush(q,(d+1,ve))
    
    if dist[T][0] < INF: break
        
print(dist[T][0]//3 if dist[T][0]<INF else -1)

n,m=list(map(int,input().split()))
uv=[list(map(int, input().split())) for _ in range(m)]
s,t=list(map(int,input().split()))

graph = [[] for _ in range(n)]
for v in uv:
    graph[v[0]-1].append(v[1]-1)
# print(graph)
s-=1
t-=1

is_checked=[[0]*3 for _ in range(n)]
is_checked[s][0]=1

ans=-1

from collections import deque
q=deque()
q.append([s,0])

while q:
    v, cnt=q.popleft()
    if v==t and cnt%3==0:
        ans=cnt//3
        break
    for i in graph[v]:
        if is_checked[i][(cnt+1)%3]==0:
            q.append([i, cnt+1])
            is_checked[i][(cnt+1)%3]=1
# print(is_checked)
print(ans)



from collections import deque
n, m = list(map(int, input().split()))

graph = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = list(map(int, input().split()))
    graph[u].append(v)

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

dist = [[-3] * 3 for _ in range(n+1)]
dist[s][0] = 0

q = deque([(s, 0)])

while q:
    now, c = q.popleft()
    ne = (c+1) % 3
    for node in graph[now]:
        if dist[node][ne] != -3:
            continue
        dist[node][ne] = dist[now][c] + 1
        q.append((node, ne))

print((dist[t][0] // 3))


import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    #graph[b-1].append(a-1)
S, T = map(int, input().split())
S -= 1; T -= 1

D = [[-1]*3 for _ in range(N)]
D[S][0] = 0
q = [(S, 0)]
while q:
    qq = []
    for p, d in q:
        for np in graph[p]:
            nd = (d+1)%3
            if D[np][nd] == -1:
                D[np][nd] = D[p][d] + 1
                qq.append((np, nd))
    q = qq

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

N,M=map(int,input().split())
list=[[] for i in range(3*N)]
for i in range(M):
  u,v=map(int,input().split())
  list[3*u-3].append(3*v-2)
  list[3*u-2].append(3*v-1)
  list[3*u-1].append(3*v-3)
s,t=map(int,input().split())
def bfs(a,b):
  visited=[-1 for i in range(3*N)]
  visited[a]=0
  h=[]
  h.append(a)
  while h:
    v=h.pop(0)
    for k in list[v]:
      if visited[k]==-1:
        visited[k]=visited[v]+1
        h.append(k)
  return visited[b]

print(bfs(3*s-3,3*t-3)//3) 

from collections import deque

n, m = list(map(int, input().split()))
uv  =[[] for _ in range(n)]
for _ in range(m):
    u, v = list(map(int, input().split()))
    uv[u - 1].append(v - 1)
s, t = list(map(int, input().split()))
s -= 1
t -= 1

queue = deque()
queue.append(s)
queue.append(1)
queue.append(0)
check = [[False for _ in range(3)] for _ in range(n)]
check[s][0] = True

while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    kkp = queue.popleft()
    for next_pos in uv[pos]:
        if next_pos == t and kkp == 2:
            print((ans // 3))
            return
        if check[next_pos][(kkp + 1) % 3]:
            continue
        check[next_pos][(kkp + 1) % 3] = True
        queue.append(next_pos)
        queue.append(ans + 1)
        queue.append((kkp + 1) % 3)
print((-1))


import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readlines
from collections import deque
def main():
    lines = input()
    n, m = list(map(int, lines[0].split()))
    #隣接リスト
    edges=[[] for i in range(n)]
    for i in range(m):
        u,v=list(map(int,lines[i+1].split()))
        edges[u-1].append(v-1)

    s,t=list(map(int,lines[m+1].split()))
    inf=100000000000
    score=[[inf]*3 for i in range(n)]
    now=deque()
    now.append((s-1, 0))
    score[s-1][0]=0
    def bfs():
        if now:
            u, mod = now.popleft()
            time = score[u][mod]
            mod = (mod+1)%3
            for v in edges[u]:
                if score[v][mod] == inf:
                    score[v][mod] = time+1
                    now.append((v, mod))

            bfs()

    bfs()
    ans = score[t-1][0]
    if ans == inf:
        print(-1)
    else:
        print(score[t-1][0]//3)
main()

import collections
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
S,T=map(int,input().split())
s=S-1
t=T-1
ischecked=[[0]*3 for _ in range(N)]
ischecked[s][0]=1
ans=-1
q=collections.deque()
q.append([s,0])
while q:
    v,c=q.popleft()
    if v==t and c%3==0:
        ans=c//3
        break
    for i in tree[v]:
        if ischecked[i][(c+1)%3]==0:
            q.append([i,c+1])
            ischecked[i][(c+1)%3]=1
print(ans)

from collections import deque
n, m = map(int, input().split())
edge = [[] for i in range(n)]
kkp = [0] * n
for i in range(m):
    u, v = map(int, input().split())
    edge[u - 1].append(v - 1)
s, t = map(int, input().split())
que = deque([(s - 1, 0)])
while que:
    now, dis = que.popleft()
    for next in edge[now]:
        if next == t - 1 and (dis + 1) % 3 == 0:
            print((dis + 1) // 3);return
        if not kkp[next] & (2 ** ((dis + 1) % 3)):
            kkp[next] = kkp[next] | (2 ** ((dis + 1) % 3))
            que.append((next, dis + 1))
print(-1)

# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
UV = [tuple(map(int,input().split())) for _ in range(M)]
S,T = map(int,input().split())

S,T = S-1,T-1

E = [[] for i in range(3*N)]
for u,v in UV:
    u,v = u-1,v-1
    E[u].append(v+N)
    E[u+N].append(v+2*N)
    E[u+2*N].append(v)

from collections import deque
dq = deque([S])
inf = float("inf")
dist = [inf]*(3*N)
dist[S] = 0

while dq:
    v = dq.popleft()
    for e in E[v]:
        if dist[e] != inf:
            continue
        dist[e] = dist[v]+1
        if e==T:
            print(dist[e]//3)
            return
        dq.append(e)

print(-1)

from collections import deque


N, M, *uv, S, T = list(map(int, open(0).read().split()))
g = [[] for _ in range(N)]
for u, v in zip(*[iter(uv)] * 2):
    g[u - 1].append(v - 1)
S -= 1
T -= 1

q = deque([(S, 0)])
dist = [[-1, -1, -1] for _ in range(N)]
dist[S][0] = 0
r = 0
while q:
    v, r = q.popleft()
    nr = (r + 1) % 3
    for nv in g[v]:
        if dist[nv][nr] >= 0:
            continue
        dist[nv][nr] = dist[v][r] + 1
        q.append((nv, nr))
print((dist[T][0] // 3))


from collections import deque
n, m = list(map(int, input().split()))
adjacent_list = [[] for i in range(3*n + 3)]
for i in range(m):
    u, v = list(map(int, input().split()))
    for j in range(1,4):
        p = j + 3 * u - 3
        q = (j % 3) + 3 * v - 2
        #print("{} -> {}".format(p, q))
        adjacent_list[p].append(q)
s, t = list(map(int, input().split()))

def bfs(start, target):
    que = deque()
    finished = set()
    que.append([start, 0])
    while que:
        node, dist = que.popleft()
        if (node, dist % 3) in finished:
            continue
        if node == target:
            return dist // 3
        for i in adjacent_list[node]:
            que.append([i, dist+1])
            finished.add((node, dist % 3))
    return -1
print((bfs(s*3 -2, 3*t-2)))



# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, ipti().split()))
    node_next = [set() for _ in range(n)]

    for i in range(m):
        u, v = list(map(int, ipti().split()))
        node_next[u - 1].add(v - 1)

    s, t = list(map(int, ipti().split()))
    s, t = s - 1, t - 1

    dist = [[INF] * n for _ in range(3)]
    dist[0][s] = 0

    que = deque()
    que.append((0, s))

    while que:
        cstate, cnode = que.popleft()
        d = dist[cstate][cnode]
        nstate = (cstate + 1) % 3
        for nnode in node_next[cnode]:
            if dist[nstate][nnode] == INF:
                dist[nstate][nnode] = d + 1
                que.append((nstate, nnode))

    if dist[0][t] != INF:
        print((dist[0][t] // 3))
    else:
        print((-1))


def __starting_point():
    main()

__starting_point()

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = list(map(int, input().split()))
    G = [set() for i in range(N)]
    G2 = [set() for i in range(N*3)]
    for i in range(M):
        u, v = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u].add(v)
    S, T = list(map(int, input().split()))
    S -= 1
    T -= 1

    import collections
    q = collections.deque()
    q.append((S, 0))
    D = [-1]*N*3
    D[3*S] = 0
    while(q):
        x, d = q.popleft()
        for y in G[x]:
            if D[y*3+(d+1) % 3] < 0:
                # G2[x*3 + d].add(y)
                q.append((y, d+1))
                D[y*3 + (d+1) % 3] = d+1

    if D[T*3] > 0:
        print((D[T*3] // 3))

    else:
        print((-1))


main()


from heapq import heappop, heappush, heapify

INF = float("inf")
n, m = list(map(int, input().split()))
idx = [[i*3 + j for j in range(3)] for i in range(n)]
g = [[] for _ in range(n*3)]
for _ in range(m):
    u, v = [int(x)-1 for x in input().split()]
    for i in range(3):
        g[idx[u][i]].append((idx[v][(i+1) % 3], 1))
s, t = [int(x)-1 for x in input().split()]

def dijkstra(graph, n, s):
    d = [INF] * n
    d[s], q = 0, []
    heappush(q, (0, s))
    while q:
        dist, v = heappop(q)
        if d[v] < dist: continue
        for nv, cost in graph[v]:
            if d[nv] > d[v] + cost:
                d[nv] = d[v] + cost
                heappush(q, (d[nv], nv))
    return d

res = dijkstra(g, n*3, idx[s][0])[idx[t][0]]
print((-1 if res == INF else res // 3))


from collections import deque
import sys

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

graph = [[] for _ in range(3*n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b+n)
    graph[a+n].append(b+2*n)
    graph[a+2*n].append(b)

dist = [-3] * (3*n+1)
dist[0] = 0
s, t = map(int, input().split())
dist[s] = 0

d = deque()
d.append(s)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -3:
            continue
        dist[i] = dist[v] + 1
        d.append(i)

print(dist[t]//3)

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

def main():
    n,m = map(int,input().split())
    G = [[] for _ in range(3*n)]
    for _ in range(m):
        u,v = map(int,input().split())
        u -= 1
        v -= 1
        for i in range(3):
            G[u*3 + i].append(v*3 + (i + 1)%3)
    
    s,g = map(int,input().split())
    s -= 1
    g -= 1

    q = deque([3*s])
    dist = [-1] * (3*n)
    dist[3*s] = 0
    while q:
        p = q.popleft()
        for e in G[p]:
            if dist[e] < 0:
                dist[e] = dist[p] + 1
                q.append(e)
                
    print(dist[3*g]//3 if dist[3*g] >= 0 else -1)
def __starting_point():
    main()
__starting_point()

def solve():
  N, M = map(int, input().split(' '))
  G = [[] for _ in range(N + 10)]
  dist = [[-1 for _ in range(3)] for _ in range(N + 10)]
  for _ in range(M):
    u, v = map(int, input().split(' '))
    G[u].append(v)
  S, T = map(int, input().split(' '))
  que = [[S, 0]]
  dist[S][0] = 0
  while que:
    q = que.pop(0)
    nv, np = q[0], q[1]
    for item in G[nv]:
      if dist[item][(np + 1) % 3] == -1:
        que.append([item, (np + 1) % 3])
        dist[item][(np + 1) % 3] = dist[nv][np] + 1
  if dist[T][0] == -1:
    return -1
  else:
    return dist[T][0] // 3
print(solve())

import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N,M= list(map(int,input().split()))
g = defaultdict(list)

for i in range(M):
    u,v = list(map(int,input().split()))
    g[u].append(N + v)
    g[N + u].append(2*N + v)
    g[2*N + u].append(v)
S,T= list(map(int,input().split()))

dq = deque([S])
inf = 10**15
d = [inf for i in range(3*N+1)]
d[S] = 0

while dq:
    v = dq.popleft()
    for nv in g[v]:
        if d[nv] > d[v] + 1:
            d[nv] = d[v] + 1
            dq.append(nv)

if inf == d[T]:
    print((-1))
else:
    print((d[T]//3))





from sys import stdin
from collections import deque


def input():
    return stdin.readline().strip()


def bfs():
    q = deque([3 * S])
    dist = [-1] * (3 * N)
    dist[3 * S] = 0
    while q:
        p = q.popleft()
        v, r = divmod(p, 3)
        nr = (r + 1) % 3
        for nv in g[v]:
            np = 3 * nv + nr
            if dist[np] >= 0:
                continue
            dist[np] = dist[p] + 1
            q.append(np)
    return dist[3 * T] // 3


N, M = list(map(int, input().split()))
g = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    g[a].append(b)
S, T = [int(x) - 1 for x in input().split()]
print((bfs()))


#Hopscotch Addict

N,M=list(map(int,input().split()))
graph={(i,j):[] for i in range(1,N+1) for j in range(1,4)}
for _ in range(M):
    u,v=list(map(int,input().split()))
    graph[(u,1)].append((v,2))
    graph[(u,2)].append((v,3))
    graph[(u,3)].append((v,1))
S,T=list(map(int,input().split()))

import heapq
def dijkstra(s,graph):
    dist={(i,j):float("inf") for i in range(1,N+1) for j in range(1,4)}
    dist[(s,3)]=0
    pq=[]
    heapq.heapify(pq)
    heapq.heappush(pq,(0,(s,3)))
    while pq:
        x=heapq.heappop(pq)
        node,mini_dis=x[1],x[0]
        for next_node in graph[node]:
            newlen=dist[node]+1
            if newlen<dist[next_node]:
                heapq.heappush(pq,(newlen,next_node))
                dist[next_node]=newlen
    return dist
K=dijkstra(S,graph)[(T,3)]
if K==float("inf"):
    print((-1))
else:
    print((K//3))



import copy

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

INF = 10**18
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N * 3))
    for _ in range(M):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v + N)
        g[u + N].add(v + N + N)
        g[u + N + N].add(v)

    S, T = (int(x) - 1 for x in input().split())

    dist = [-1] * (N * 3)
    dist[S] = 0

    dq = deque()
    dq.append(S)
    while dq:
        v = dq.popleft()
        for u in g[v]:
            if ~dist[u]: continue
            dist[u] = dist[v] + 1
            dq.append(u)

    if dist[T] % 3:
        print((-1))
        return

    print((dist[T] // 3))


def __starting_point():
    main()

__starting_point()

from collections import deque
def bfs(start, goal, g, n, visited):
    visited1 = [False]*(n+1)
    visited2 = [False]*(n+1)
    q = deque([start])
    visited[start] = 0
    while q:
        curr_node = q.popleft()
        if curr_node == goal: 
            return
        for next1_node in g[curr_node]:
            if visited1[next1_node]: continue
            visited1[next1_node] = True
            for next2_node in g[next1_node]:
                if visited2[next2_node]: continue
                visited2[next2_node] = True
                for next3_node in g[next2_node]:
                    if visited[next3_node] >= 0: continue
                    visited[next3_node] = visited[curr_node] + 1
                    q.append(next3_node)



def main():
    n,m = map(int, input().split())
    g = [ [] for _ in range(n+1)]

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

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

    visited = [-1]*(n+1)
    visited[0] = 0

    bfs(s, t, g, n, visited)
    print(visited[t])

def __starting_point():
    main()
__starting_point()

N, M = map(int, input().split())
to = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    to[a].append(b)

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

from collections import deque

q = deque([(S, 0)])
v = [[-1] * 3 for i in range(N+1)]

while q:
    a, t = q.popleft()
    b = t % 3
    if v[a][b] != -1:
        continue
    v[a][b] = t
    t += 1
    for x in to[a]:
        q.append((x, t))
    #print(q)


if v[T][0] == -1:
    print("-1")
else:
    print(v[T][0] // 3)

n,m=list(map(int,input().split()))
uv=[list(map(int, input().split())) for _ in range(m)]
s,t=list(map(int,input().split()))

graph = [[] for _ in range(n)]
for v in uv:
    graph[v[0]-1].append(v[1]-1)
# print(graph)
s-=1
t-=1

is_checked=[[0]*3 for _ in range(n)]
is_checked[s][0]=1

ans=-1

from collections import deque
q=deque()
q.append([s,0])

while q:
    v, cnt=q.popleft()
    if v==t and cnt%3==0:
        ans=cnt//3
        break
    for i in graph[v]:
        if is_checked[i][(cnt+1)%3]==0:
            q.append([i, cnt+1])
            is_checked[i][(cnt+1)%3]=1
# print(is_checked)
print(ans)



from collections import deque
INF = 10**9

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

G = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int,input().split())
    u, v = u-1, v-1

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

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

dist = [INF] * (3*N)
dist[s] = 0

Q = deque([s])
while len(Q) > 0:
    u = Q.popleft()
    for v in G[u]:
        if dist[v] == INF:
            dist[v] = dist[u] + 1
            Q.append(v)

if dist[t] == INF:
    print(-1)
else: 
    print(dist[t] // 3)

from collections import deque
n, m = list(map(int, input().split()))
graph = [[[] for _ in range(3)] for _ in range(n+1)]
for _ in range(m):
    u, v = list(map(int, input().split()))
    graph[u][0].append([v, 1])
    graph[u][1].append([v, 2])
    graph[u][2].append([v, 0])


s, t = list(map(int, input().split()))
q = deque([[s, 0]])
visited = [[False] * 3 for _ in range(n+1)]
visited[s][0] = True
dist = [[-3] * 3 for _ in range(n+1)]
dist[s][0] = 0
while q:
    num, cnt = q.popleft()
    for i, j in graph[num][cnt]:
        if visited[i][j]:
            continue
        q.append([i, j])
        visited[i][j] = True
        dist[i][j] = dist[num][cnt] + 1

print((dist[t][0]//3))


N,M = map(int,input().split())
UV = [tuple(map(int,input().split())) for i in range(M)]
S,T = map(int,input().split())
S -= 1
T -= 1
es = [[] for _ in range(3*N)]
for u,v in UV:
    u,v = u-1,v-1
    es[3*u].append(3*v+1)
    es[3*u+1].append(3*v+2)
    es[3*u+2].append(3*v)

from collections import deque
dist = [0] * (3*N)
visited = [0] * (3*N)
visited[3*S] = 1
q = deque([3*S])
while q:
    v = q.popleft()
    if v==3*T:
        assert dist[v]%3==0
        print(dist[v]//3)
        return
    for to in es[v]:
        if visited[to]: continue
        visited[to] = 1
        dist[to] = dist[v] + 1
        q.append(to)
print(-1)

from collections import deque
n, m = list(map(int, input().split()))
graph = [[[] for _ in range(3)] for _ in range(n+1)]
for _ in range(m):
    u, v = list(map(int, input().split()))
    graph[u][0].append([v, 1])
    graph[u][1].append([v, 2])
    graph[u][2].append([v, 0])


s, t = list(map(int, input().split()))
q = deque([[s, 0]])
visited = [[False] * 3 for _ in range(n+1)]
visited[s][0] = True
dist = [[-3] * 3 for _ in range(n+1)]
dist[s][0] = 0
while q:
    num, cnt = q.popleft()
    for i, j in graph[num][cnt]:
        if visited[i][j]:
            continue
        q.append([i, j])
        visited[i][j] = True
        dist[i][j] = dist[num][cnt] + 1

print((dist[t][0]//3))


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

graph = [[] for i in range(N)]

for i in range(M):
  u,v = map(int,input().split())
  graph[u - 1].append(v - 1)

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

from collections import deque
q = deque([])
q.append([S, 0, 0])

seen = [[False] * 3 for i in range(N)]

while q:
  v,cost,step = q.popleft()
  if seen[v][step]:
    continue
  seen[v][step] = True
  if step == 0:
    if v == T:
      print(cost)
      break
    cost += 1
    step = 3
  for u in graph[v]:
    q.append([u, cost, step - 1])
else:
  print(-1)

from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(3*N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[3*u].append(3*v+1)
  graph[3*u+1].append(3*v+2)
  graph[3*u+2].append(3*v)

S, T = map(int, input().split())
S -= 1; T -= 1
dist = [-1] * (3*N)
dist[3*S] = 0
d = deque([3*S])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] < 0:
      dist[child] = dist[node] + 1
      d.append(child)

if dist[3*T] > 0:
  print(dist[3*T] // 3)
else:
  print(-1)

from collections import deque
import sys
input = sys.stdin.readline
n, m = list(map(int, input().split()))
NV = 3*n
edges = [[]for _ in range(NV)]


def to_v(i, j):
    return 3*i+j


for _ in range(m):
    u, v = list([int(x)-1 for x in input().split()])
    for j in range(3):
        edges[to_v(u, j)].append(to_v(v, (j+1) % 3))
s, t = list([int(x)-1 for x in input().split()])
init_v = to_v(s, 0)
INF = 10**18
dist = [INF]*NV
dist[init_v] = 0
next_v = deque([init_v])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)

print((dist[to_v(t, 0)]//3 if dist[to_v(t, 0)] != INF else -1))


import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            start node

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node 
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s)) # (cost, 探索候補ノード)
        v = collections.defaultdict(bool) # 確定済かどうか
        while len(q):
            # ノードuにおけるコストはk
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]: # cost is ud from u to uv
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev
n, m = inpl()
graph=Dijkstra()
for i in range(m):
    u, v = inpl()
    graph.add(u,v+n,1,directed=True)
    graph.add(u+n,v+n+n,1,directed=True)
    graph.add(u+n+n,v,1,directed=True)
s,t=inpl()
ans = 0
d, _ = graph.Dijkstra_search(s)
ans = d[t] if d[t] != INF else - 1
# print(d)
print(ans//3)

from collections import deque
n,m = map(int,input().split())
l = [[] for i in range(n+1)]
rl = [[-1 for i in range(n+1)] for i in range(3)]
for i in range(m):
    u,v = map(int,input().split())
    l[u].append(v)
s,t = map(int,input().split())
d = deque()
ans = -1
d.append([s,0])
rl[0][s] = 0
while len(d):
    now,count = d.popleft()
    for i in l[now]:
        if i == t and count % 3 == 2:
            ans = (count + 1)//3
            break
        else:
            if rl[(count%3 + 1)%3][i] == -1:
                d.append([i,count+1])
                rl[(count%3+1)%3][i] = count+1
    if ans >= 0:
        break
print(ans)

import heapq
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
INF = 10**18
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
s,t = map(int,input().split())

def dijkstra_heap(s,g,p):
    d = [[INF] * p for i in range(n)] 
    used = [[True] * p for i in range(n)] 
    used[s][0] = False
    ed_list = []
    for es in edge[s]:
        heapq.heappush(ed_list,[1,es,1]) # 回数、向かう頂点、あまり
    while len(ed_list):
        ken,v,md = heapq.heappop(ed_list)
        if not used[v][md]:
            continue
        d[v][md] = ken
        used[v][md] = False
        if not used[g][0]:
            break
        for e in edge[v]:
            if used[e][(md+1)%p]:
              if (md+1)%p == 1:
                heapq.heappush(ed_list,[ken+1,e,1])
              else:
                heapq.heappush(ed_list,[ken,e,(md+1)%p])
    return d[g][0]

ans = dijkstra_heap(s-1,t-1,3)
if ans == INF:
  print(-1)
else:
  print(ans)

from collections import defaultdict
n,m=list(map(int,input().split()))
d = defaultdict(list)
for _ in range(m):
    u,v=list(map(int,input().split()))
    d[u-1].append(v-1)
S,T=list(map(int,input().split()))
s=S-1
t=T-1
cd=[[0]*3 for _ in range(n)]
cd[s][0]=1
ans=-1
q=[]
q.append([s,0])
while q:
    v,c=q.pop(0)
    if v==t and c%3==0:
        ans=c//3
        break
    for i in d[v]:
        if cd[i][(c+1)%3]==0:
            q.append([i,c+1])
            cd[i][(c+1)%3]=1
print(ans)


from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n*3)]
    for i in range(m):
        a,b=map(lambda x:int(x)-1,readline().split())
        for j in range(3):
            G[3*a+j].append(3*b+(j+1)%3)

    s,t=map(lambda x:int(x)-1,readline().split())
    s*=3
    t*=3
    #bfs
    d=deque([s])
    flags=[-1]*(3*n)
    flags[s]=0
    while len(d)>0:
        now=d.popleft()
        for nex in G[now]:
            if flags[nex]==-1:
                flags[nex]=flags[now]+1
                d.append(nex)

    print(flags[t]//3)

def __starting_point():
    main()
__starting_point()

import collections

n, m = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
flag = [False for i in range(n + 1)]
s, t = map(int, input().split())

queue = collections.deque([s])
count = 0
while True:
    for i in range(2):
        temp = set()
        while queue:
            test = queue.popleft()
            for j in graph[test]:
                if j not in temp:
                    temp.add(j)
        for j in temp:
            queue.append(j)
    temp = set()
    while queue:
        test = queue.popleft()
        for i in graph[test]:
            if flag[i] == True:
                continue
            else:
                if i not in temp:
                    temp.add(i)
                    flag[i] = True
    count += 1
    if flag[t] == True:
        print(count)
        break
    if len(temp) == 0:
        print(-1)
        break
    for i in temp:
        queue.append(i)

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

N, M = list(map(int, input().split()))
if M == 0:
    print((-1))
    return
adj = [[] for _ in range(N)]
for i in range(M):
    u, v = list(map(int, input().split()))    
    u -= 1
    v -= 1
    adj[u].append(v)
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [[INF,INF,INF] for _ in range(N+1)]
 
d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in adj[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq
 
d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)




from collections import deque

n, m = map(int, input().split())
adj_list = [[] for _ in range(3 * n)]
for _ in range(m):
  u, v = map(int, input().split())
  adj_list[3 * u - 3].append(3 * v - 2)
  adj_list[3 * u - 2].append(3 * v - 1)
  adj_list[3 * u - 1].append(3 * v - 3)

s, t = map(int, input().split())
dist = [-1] * (3 * n)
queue = deque([3 * s - 3])
dist[3 * s - 3] = 0
while queue:
  vertex = queue.popleft()
  for next_vertex in adj_list[vertex]:
    if dist[next_vertex] != -1:
      continue
    dist[next_vertex] = dist[vertex] + 1
    queue.append(next_vertex)
t_distance = dist[3 * t - 3]
if t_distance == -1:
  print(-1)
else:
  print(t_distance // 3)

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def dfs(v, p):
        for u in edge_extend[p][v]:
            next_p = 0 if p == 2 else p + 1
            if dist[next_p][u] <= dist[p][v] + 1:
                continue
            else:
                dist[next_p][u] = dist[p][v] + 1
                dfs(u, next_p)

    n, m = list(map(int, input().split()))
    edge = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split()))
        edge[u - 1].append(v - 1)
    s, t = list(map(int, input().split()))

    edge_extend = []
    for _ in range(3):
        edge_extend.append(edge)

    dist = [[f_inf] * n for _ in range(3)]
    dist[0][s - 1] = 0
    que = deque([[0, s - 1]])
    while que:
        p, v = que.popleft()
        next_p = 0 if p == 2 else p + 1
        for u in edge_extend[p][v]:
            if dist[next_p][u] > dist[p][v] + 1:
                dist[next_p][u] = dist[p][v] + 1
                que.append([next_p, u])

    print((dist[0][t - 1] // 3 if dist[0][t - 1] != f_inf else -1))


def __starting_point():
    resolve()

__starting_point()

from collections import deque
n, m = list(map(int, input().split()))
edges = [[] for i in range(3*n)]
for i in range(m):
    u,v = list(map(int, input().split()))
    u -= 1
    v -= 1
    edges[u].append(v+n)
    edges[u+n].append(v+2*n)
    edges[u+2*n].append(v)

s,t = list(map(int, input().split()))
s -= 1
t -= 1
INF = 1<<50
dists = [INF] * (3*n)

q = deque([])
q.append(s)
dists[s] = 0

while len(q)>0:
    v = q.popleft()
    for u in edges[v]:
        if dists[u] != INF: continue
        q.append(u)
        dists[u] = dists[v] + 1

if dists[t] == INF:
    print((-1))
else:
    print((dists[t]//3))




from collections import deque


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



es = [[] for _ in range(3*N)]
for _ in range(M):
    u,v = list(map(int, input().split()))
    u,v = u-1, v-1
    es[u].append(N + v)
    es[N + u].append(2*N + v)
    es[2*N + u].append(v)

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

q = deque()
q.append(S-1)
INF = float("inf")
dist = [INF] * (3*N)
dist[S-1] = 0

while q:
    curr = q.popleft()
    
    for nxt in es[curr]:
        if dist[nxt] == INF:
            dist[nxt] = dist[curr] + 1
            if nxt == T-1:
                print((dist[nxt] // 3))
                
                return
            
            q.append(nxt)

print((-1))


from collections import deque
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m, *uv, s, t = list(map(int, read().split()))
m = iter(uv)
UV = list(zip(m, m))
graph = [[] for _ in range(3 * n)]
for u, v in UV:
    u -= 1
    v -= 1
    graph[u].append(v + n)
    graph[u + n].append(v + 2 * n)
    graph[u + 2 * n].append(v)
s -= 1
t -= 1
infi = 10 ** 20
dist = [-1] * (3 * n)


def bfs(s):
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        v = que.popleft()
        if v == t:
            return dist[t]
        d = dist[v]
        for u in graph[v]:
            if dist[u] > 0:
                continue
            dist[u] = d + 1
            que.append(u)
    return -1


ans = bfs(s)
if ans > 0:
    ans //= 3
print(ans)


n, m = list(map(int, input().split()))
to = [[] for _ in range(n)]
for _ in range(m):
    u, v = list(map(int, input().split()))
    to[u - 1].append(v - 1)

s, t = list(map(int, input().split()))
s -= 1
t -= 1

cnt = 0
phase = 0
q = [s]
visited = [[False] * 3 for _ in range(n)]
while q:
    nextq = []
    for v in q:
        if visited[v][phase]:
            continue
        visited[v][phase] = True
        if v == t and phase == 0:
            print(cnt)
            return
        nextq += to[v]
    if phase == 0:
        cnt += 1
    phase = (phase + 1) % 3
    q = nextq
print((-1))


inf=10**12
n,m=map(int,input().split())
node=[[]for _ in range(n)]
dis=[inf]*(n*3)
for _ in range(m):
	a,b=map(int,input().split())
	node[a-1].append(b-1)
s,t=map(int,input().split())
dis[(s-1)*3]=0
from collections import deque
queue=deque([(s-1)*3])
while queue:
	r=queue.popleft()
	p=(r%3+1)%3
	for x in node[r//3]:
		if dis[x*3+p]==inf:
			dis[x*3+p]=dis[r]+1
			queue.append(x*3+p)
print(dis[(t-1)*3]//3 if dis[(t-1)*3]!=inf else -1)

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

N, M = list(map(int, input().split()))
if M == 0:
    print((-1))
    return
adj = [[] for _ in range(N)]
for i in range(M):
    u, v = list(map(int, input().split()))    
    u -= 1
    v -= 1
    adj[u].append(v)
S, T = list(map(int, input().split()))
S -= 1
T -= 1

dist = [[INF,INF,INF] for _ in range(N+1)]
 
q = queue.Queue()
q.put((S, 0))
dist[S][0] = 0
while not q.empty():
    u, l = q.get()
    for v in adj[u]:
        nl = (l + 1) % 3
        if dist[v][nl] != INF:
            continue
        dist[v][nl] = dist[u][l] + 1
        q.put((v, nl))
d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)




import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = list(map(int, input().split()))
    edge = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split()))
        edge[u - 1].append(v - 1)
    s, t = list(map(int, input().split()))

    dist = [[f_inf] * 3 for _ in range(n)]
    que = deque([])
    que.append([s - 1, 0])
    dist[s - 1][0] = 0
    while que:
        v, l = que.popleft()
        for u in edge[v]:
            nl = (l + 1) % 3
            if dist[u][nl] == f_inf:
                dist[u][nl] = dist[v][l] + 1
                que.append([u, nl])

    res = dist[t - 1][0]
    print((-1 if res == f_inf else res // 3))


def __starting_point():
    resolve()

__starting_point()

import copy
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
edge = []
graph = [[] for i in range(n+1)]
for i in range(m):
    edge.append(list(map(int,input().split())))
    graph[edge[-1][0]].append(edge[-1][1])
s, g = map(int,input().split())

INF = 10**18
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = copy.deepcopy(nq)
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

import copy
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
graph = [[] for i in range(n+1)]
for i in range(m):
    u, v = map(int,input().split())
    graph[u].append(v)
s, g = map(int,input().split())

INF = 10**7
ans = [[INF, INF, INF] for i in range(n+1)]
q = [s]
d = 0
while q:
    nq = []
    d += 1
    p = d % 3
    for cf in q:
        for ct in graph[cf]:
            if ans[ct][p] == INF:
                ans[ct][p] = d
                nq.append(ct)
    q = nq
if ans[g][0] == INF:
    print(-1)
else:
    print(ans[g][0]//3)

from sys import stdin
from collections import deque


def input():
    return stdin.readline().strip()


def bfs():
    q = deque([S])
    dist = [-1] * (3 * N)
    dist[S] = 0
    while q:
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] >= 0:
                continue
            dist[nv] = dist[v] + 1
            q.append(nv)
    return dist[T] // 3


N, M = list(map(int, input().split()))
g = [[] for _ in range(3 * N)]
for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    g[3 * a].append(3 * b + 1)
    g[3 * a + 1].append(3 * b + 2)
    g[3 * a + 2].append(3 * b)
S, T = [3 * (int(x) - 1) for x in input().split()]
print((bfs()))


#ダイクストラ
#単一始点最短経路(正の辺のみ)
#s=始点 n=頂点数 edgeは隣接リスト(edge=[[[1,2],[2,4]],[[2,1]],[]])
#0-indexed
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
n,m=list(map(int,input().split()))
edge=[[]for _ in range(n*3)]
for _ in range(m):
	u,v=list(map(int,input().split()))
	u-=1
	v-=1
	edge[u*3].append([v*3+1,1])
	edge[u*3+1].append([v*3+2,1])
	edge[u*3+2].append([v*3,1])
s,t=list(map(int,input().split()))
s-=1
t-=1
dij=dijkstra(s*3,n*3,edge)
if dij[t*3]==10**20:print((-1))
else:print((dij[t*3]//3))


def main():
  N, M = map(int, input().split())
  edge = [[[] for _ in range(3)] for _ in range(N)]
  for i in range(M):
    u, v = map(int, input().split())
    edge[u-1][0].append([v-1,1])
    edge[u-1][1].append([v-1,2])
    edge[u-1][2].append([v-1,0])
  d = [[-1]*3 for _ in range(N)]
  S, T = map(int, input().split())
  d[S-1][0] = 0
  que = [[S-1, 0]]
  while len(que)>0:
    now = que.pop(0)
    for nex in edge[now[0]][now[1]]:
      if d[nex[0]][nex[1]] != -1:continue
      d[nex[0]][nex[1]] = d[now[0]][now[1]]
      if now[1] == 2:
        d[nex[0]][nex[1]] += 1
      que.append(nex)
  print(d[T-1][0])
  
def __starting_point():
  main()
__starting_point()

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

# 双方向グラフで幅優先探索

from collections import deque

n, m = list(map(int, input().split()))
g = [set([]) for _ in range(n)]
#隣接リストの作成
for i in range(m):
    a, b = list(map(int, input().split()))
    a, b = a-1, b-1
    g[a].add(b)

s, t = list(map(int, input().split()))
s, t = s-1, t-1

#幅優先探索
q = deque()
level = [[-1]*n for i in range(3)]
q.append((s, 0))
level[0][s] = 0
while len(q)>0:
    cur, hp = q.popleft()
    lvl = level[hp][cur]
    for i in g[cur]:
        if level[(hp+1)%3][i]==-1:
            #階層
            level[(hp+1)%3][i] = lvl + 1
            q.append((i, (hp+1)%3))
print((level[0][t]//3))