CodeEff/ECCO huggingface dataset:
# Original solution
import sys
from collections import deque

sys.setrecursionlimit(10000000)

readline = sys.stdin.readline

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

S, T = S - 1, T - 1

nodes = [{} for i in range(N)]
for u, v in uv:
    nodes[u - 1][v - 1] = 1

visited = [False] * N

def kenken(u, rem):
    if rem > 0:
        a = []
        for v in nodes[u]:
            a += kenken(v, rem - 1)
        return a
    else:
        return [u]
    

q = deque()

q.append([S, 0])

_count = -1
while len(q) != 0:
    u, count = q.popleft()
    if not visited[u]:
        visited[u] = True

        ret = kenken(u, 3)
        if any(T == r for r in ret):
            _count = count + 1
            break
        q.extend([r, count + 1] for r in ret)


print(_count)

# Optimized solution
import sys
from collections import deque

sys.setrecursionlimit(10000000)

readline = sys.stdin.readline

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

S, T = S - 1, T - 1

nodes = [{} for i in range(N)]
for u, v in uv:
    nodes[u - 1][v - 1] = 1

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

def kenken(u, rem):
    if rem != 3 and visited[rem][u]:
        return deque()
    
    if rem != 3:
        visited[rem][u] = True
    if rem > 0:
        a = deque()
        for v in nodes[u]:
            a.extend(kenken(v, rem - 1))
        return a
    else:
        return deque([u])
    

q = deque()

q.append([S, 0])

_count = -1
while len(q) != 0:
    u, count = q.popleft()

    ret = kenken(u, 3)
    if any(T == r for r in ret):
        _count = count + 1
        break
    q.extend([r, count + 1] for r in ret)


print(_count)
# Original solution
N, M = list(map(int, input().split()))
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = list(map(int, input().split()))
  a[u].append(v)
#print(a)

S, T = list(map(int, input().split()))
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    vs = []
    for u in c:
      m[u][count %3] = True
      vs += a[u]
    c = []
    for v in vs:
      if (v == T and count %3 ==0):
        return count//3
      if not(m[v][(count+1) %3]):
        c.append(v)
  return -1
print((main()))


# Optimized solution
N, M = list(map(int, input().split()))
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = list(map(int, input().split()))
  a[u].append(v)
#print(a)

S, T = list(map(int, input().split()))
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    c2 = []
    for u in c:
      m[u][count %3] = True
      for v in a[u]:
        if (v == T and count %3 ==0):
          return count//3
        if not(m[v][(count+1) %3]):
          c2.append(v)
    c = c2
  return -1
print((main()))
# Original solution
import sys
from collections import deque


input = sys.stdin.readline
n, m = list(map(int, input().split()))
info = tuple(list(map(int, input().split())) for i in range(m))
s, t = list(map(int, input().split()))

graph = [[] for i in range(n)]
for i, j in info:
    graph[i-1].append(j-1)


graph2 = [[] for i in range(n)]
q = deque()
q.append((s - 1, 0))
INF = float("inf")
visited = [INF] * n
visited[0] = 0

while q:
    pos, times = q.popleft()
    for i in graph[pos]:
        if (times + 1) % 3 != 0:
            q.append((i, times + 1))
        if (times + 1) % 3 == 0 and times + 1 < visited[i]:
            visited[i] = times + 1
            q.append((i, times+1))

if visited[t-1] == float("inf"):
    print((-1))
else:
    print((visited[t-1]//3))
    

# Optimized solution
import sys
from collections import deque


input = sys.stdin.readline
n, m = list(map(int, input().split()))
info = tuple(list(map(int, input().split())) for i in range(m))
s, t = list(map(int, input().split()))

graph = [[] for i in range(n)]
for i, j in info:
    graph[i-1].append(j-1)

q = deque()
q.append((s - 1, 0))
INF = 10 ** 10
visited = [10 ** 10] * n
visited_1 = [10 ** 10] * n
visited_2 = [10 ** 10] * n
visited[s - 1] = 0
while q:
    pos, times = q.popleft()
    for i in graph[pos]:
        if (times + 1) % 3 == 1 and times + 1 < visited_1[i]:
            visited_1[i] = times + 1
            q.append((i, times + 1))

        elif (times + 1) % 3 == 2 and times + 1 < visited_2[i]:
            visited_2[i] = times + 1
            q.append((i, times + 1))
            
        elif (times + 1) % 3 == 0 and times + 1 < visited[i]:
            visited[i] = times + 1
            q.append((i, times + 1))

if visited[t - 1] == 10 ** 10:
    print((-1))
else:
    print((visited[t-1]//3))
# Original solution
# 最大でも3Nしか頂点には回らない
import sys
from collections import deque
input = sys.stdin.readline
n, m = list(map(int, input().split()))

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

dist = [[False]*3 for i in range(n)]
cnt = [[0]*3 for i in range(n)]
s, t = list(map(int, input().split()))
s -= 1
t -= 1
q = deque()
# now, dist(mod3), cnt
q.append((s, 0, 0))
while q:
    now, d, c = q.popleft()
    if dist[now][d] and cnt[now][d] < c:
        continue
    dist[now][d] = True
    cnt[now][d] = c
    next_d = (d+1)%3
    next_c = c+1
    for to in edges[now]:
        if not dist[to][next_d] or cnt[to][next_d] > c:
            q.appendleft((to, next_d,next_c))
if dist[t][0]:
    print((cnt[t][0]//3))
else:
    print((-1))

# Optimized solution
# 最大でも3Nしか頂点には回らない
import sys
from collections import deque
input = sys.stdin.readline
n, m = list(map(int, input().split()))

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

dist = [[False]*3 for i in range(n)]
cnt = [[0]*3 for i in range(n)]
s, t = list(map(int, input().split()))
s -= 1
t -= 1
q = deque()
# now, dist(mod3), cnt
q.append((s, 0, 0))
while q:
    now, d, c = q.popleft()
    if dist[now][d] and cnt[now][d] <= c:
        continue
    dist[now][d] = True
    cnt[now][d] = c
    next_d = (d+1)%3
    next_c = c+1
    for to in edges[now]:
        if not dist[to][next_d] or cnt[to][next_d] > c:
            q.append((to, next_d,next_c))
if dist[t][0]:
    print((cnt[t][0]//3))
else:
    print((-1))
# Original solution
n, m = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = list(map(int, input().split()))

l = [[] for u in range(n + 1)]
for u, v in uv:
    l[u].append(v)

def bfs(v):
    q = [(x, 0) for x in list(v)]
    visited = set(q)
    while len(q) > 0:
        x, step = q.pop(0)
        if step == 3:
            v.add(x)
            continue
        for y in l[x]:
            next = (y, step + 1)
            if next not in visited:
                visited.add(next)
                q.append(next)
    return v

v = set([s])
ret = 0
while True:
    olen = len(v)
    v = bfs(v)
    ret += 1
    if t in v:
        break
    if len(v) == olen:
        ret = -1
        break

print(ret)

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

l = [[] for u in range(n + 1)]
for u, v in uv:
    l[u].append(v)

def bfs(v):
    q = [(x, 0) for x in list(v)]
    index = 0
    ret = set()
    while len(q) > index:
        x, step = q[index]
        index += 1
        if step == 3:
            ret.add(x)
            continue
        for y in l[x]:
            next = (y, step + 1)
            if next not in visited:
                visited.add(next)
                q.append(next)
    return ret

v = set([s])
visited = set([(s, 0)])
ret = 0
while True:
    v2 = bfs(v)
    if len(v2) == 0:
        ret = -1
        break
    ret += 1
    if t in v2:
        break
    v = v2

print(ret)
# Original solution
n,m=list(map(int,input().split()))
path=[[] for i in range(n+1)]
for i in range(m):
    u,v=list(map(int,input().split()))
    path[u].append(v)
S,T=list(map(int,input().split()))

que=[S]
flag=[0]*(n+1)
flag[S]=1
data=[[] for i in range(n+1)]

while que:
    h=que.pop()
    lst=[h]
    for i in range(3):
        u=[]
        for j in lst:
            for k in path[j]:
                u.append(k)
        lst=u
    lst=list(set(lst))
    for i in lst:
        if i==h:
            continue
        data[h].append(i)
        if flag[i]==0:
            flag[i]=1
            que.append(i)

que=[S]
flag=[0]*(n+1)
flag[S]=1
count=0
while que:
    count+=1
    H=[]
    for u in que:
        for v in data[u]:
            if flag[v]==0:
                H.append(v)
                flag[v]=1
            if v==T:
                print(count)
                break
        else:
            continue
        break
    else:
        que=H
        continue
    break
else:
    print((-1))

# Optimized solution
n,m=list(map(int,input().split()))
data=[[] for i in range(3*n+1)]
for i in range(m):
    u,v=list(map(int,input().split()))
    data[u].append(v+n)
    data[u+n].append(v+2*n)
    data[u+2*n].append(v)
s,t=list(map(int,input().split()))
inf=float("inf") 
flag=[inf]*(3*n+1)
flag[s]=0
que=[s]
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==inf:
                flag[v]=flag[u]+1
                h.append(v)
    que=h
if flag[t]==inf:
    print((-1))
else:
    print((flag[t]//3))
# Original solution
import sys
from collections import defaultdict
input=sys.stdin.readline

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

D=defaultdict(int)
L=[s]
LL,LLL,LLLL,l=[],[],[],[]
cnt=0

while L:
    if t in L:
        print(cnt)
        exit()
    for i in L:
        for j in G[i]:
            LL.append(j)
    for ii in LL:
        for jj in G[ii]:
            LLL.append(jj)
    for iii in LLL:
        for jjj in G[iii]:
            LLLL.append(jjj)
    for iiii in LLLL:
        if D[iiii]==0:
            D[iiii]=1
            l.append(iiii)
    L,LL,LLL,LLLL=l,[],[],[]
    l=[]
    cnt+=1

print((-1))

# Optimized solution
import sys
from collections import deque
input=sys.stdin.readline

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

Q=deque()
Q.append(s*3)
D=[-3 for _ in range(3*(n+1))]
D[s*3]=0

while Q:
    q=Q.popleft()
    for i in G[q]:
        if D[i]==-3:
            D[i]=D[q]+1
            Q.append(i)

print((D[t*3]//3))
# Original solution
n, m = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = list(map(int, input().split()))

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

for u, v in uv:
    a = u - 1
    b = v - 1
    g[a].append(n + b)
    g[n+a].append(n*2 + b)
    g[n*2+a].append(b)

#print(g)

s -= 1
t -= 1
ans = 0
temp = [s]
while 1:
    ans += 1
    next = []
    for x in temp:
        next = next + g[x]
        g[x] = []
    if len(next) == 0:
        print((-1))
        exit()
    if t in next:
        print((ans // 3))
        exit()
    temp = [] + list(set(next))


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

g = [set() for _ in range(3 * n)]

for u, v in uv:
    a = u - 1
    b = v - 1
    g[a].add(n + b)
    g[n+a].add(n*2 + b)
    g[n*2+a].add(b)

#print(g)

s -= 1
t -= 1
ans = 0
temp = set()
temp.add(s)
while 1:
    ans += 1
    next = set()
    for x in temp:
        for y in g[x]:
            next.add(y)
        g[x] = []
    if len(next) == 0:
        print((-1))
        exit()
    if t in next:
        print((ans // 3))
        exit()
    temp = next
# Original solution
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = list(map(int, input().split()))

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

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

#p("N,M",N,M)
#p("G",G)
#p("S,T",S,T)


# グラフGから、3つ先の到達点のグラフXを作る
X=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]

for i in range(N+1):
	g = G[i]

	for g1 in g:
		for g2 in G[g1]:
			for g3 in G[g2]:
#				if (not g3 in X[i]):
#					X[i].append(g3)
				X[i].append(g3)

#p("X",X)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
V=[-1 for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
V[S]=0

# キューに行き先候補を入れて、
from collections import deque

Q = deque()
Q.append(S)

while Q:
	fm = Q.popleft()
#	p("fm, X[fm], Q ", fm, X[fm], Q)
	
	for to in X[fm]:
#		p("  to, V[to], Q ",to, V[to], Q)
		
		b = (V[to]==-1)							# 未訪問である
		#b = b or (V[to]>(V[fm]+1))	# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[to] = V[fm]+1		# 訪問ステップ数の記録
			Q.append(to)			# 次の訪問先として、キューに追加

#	p("V ",V)

#ans = V[T] if V[T]>0 else -1
#print(ans)

print((V[T]))


# Optimized solution
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = list(map(int, input().split()))

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

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

#p("N,M",N,M)
#p("G",G)
#p("S,T",S,T)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
V=[ [-1,-1,-1] for _ in range(N+1) ]			#=> [ [-1,-1,-1], [-1,-1,-1], ... [-1,-1,-1] ]
V[S][0]=0

# キューに行き先候補を入れて、
from collections import deque
Q = deque()
Q.append([S,0])

while Q:
	FM = Q.popleft()
	
	fm = FM[0]
	l =  FM[1]
	
	for to in G[fm]:
		nl = (l+1)%3
		b = (V[to][nl]==-1)							# 未訪問である
		#b = b or (V[to]>(V[fm]+1))	# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[to][nl] = V[fm][l]+1		# 訪問ステップ数の記録
			Q.append([to,nl])			# 次の訪問先として、キューに追加

ans = V[T][0]
if ans > -1: ans //= 3
print(ans)
# Original solution
# ABC132 E
from collections import deque

f=lambda:list(map(int,input().split()))
N,M=f()
KKP=[[set([]) for _ in [0]*(N+1)] for _ in [0]*3]
for _ in [0]*M:
    a,b=f()
    KKP[0][a].add(b)
S,T=f()

for j in range(2):
    # j:回数
    for a in range(1,N+1):
        # a:頂点
        for b in KKP[j][a]:
             # KKP[j][a]:aからj+1回でたどり着ける頂点
            for c in KKP[0][b]:
                # bから1回でたどり着ける頂点
                KKP[j+1][a].add(c)

F=set([])
q=deque()
q.append((S,0))
res=-1
while q:
    node,score=q.popleft()
    if node in F:
        continue
    if T==node:
        res=score
        break
    F.add(node)
    for nnode in KKP[2][node]:
        if nnode in F:
            continue
        q.append((nnode,score+1))
print(res)

# Optimized solution
# ABC132 E
from collections import deque

f=lambda:list(map(int,input().split()))
N,M=f()
KKP=[[[] for _ in [0]*(N+1)] for _ in [0]*3]
for _ in [0]*M:
    a,b=f()
    KKP[0][a].append(b)
S,T=f()

for j in range(2):
    # j:回数
    for a in range(1,N+1):
        # a:頂点
        for b in KKP[j][a]:
            # KKP[j][a]:aからj+1回でたどり着ける頂点 b
            for c in KKP[0][b]:
                # bから1回でたどり着ける頂点 c
                if not c in KKP[j+1][a]:
                    KKP[j+1][a].append(c)

F=set([])
q=deque()
q.append((S,0))
res=-1
while q:
    node,score=q.popleft()
    if node in F:
        continue
    if T==node:
        res=score
        break
    F.add(node)
    for nnode in KKP[2][node]:
        if nnode in F:
            continue
        q.append((nnode,score+1))
print(res)
# Original solution
# ABC132 E
from collections import deque

f=lambda:list(map(int,input().split()))
N,M=f()
KKP=[[[] for _ in [0]*(N+1)] for _ in [0]*3]
for _ in [0]*M:
    a,b=f()
    KKP[0][a].append(b)
S,T=f()

for j in range(2):
    # j:回数
    for a in range(1,N+1):
        # a:頂点
        for b in KKP[j][a]:
            # KKP[j][a]:aからj+1回でたどり着ける頂点 b
            for c in KKP[0][b]:
                # bから1回でたどり着ける頂点 c
                if not c in KKP[j+1][a]:
                    KKP[j+1][a].append(c)

F=set([])
q=deque()
q.append((S,0))
res=-1
while q:
    node,score=q.popleft()
    if node in F:
        continue
    if T==node:
        res=score
        break
    F.add(node)
    for nnode in KKP[2][node]:
        if nnode in F:
            continue
        q.append((nnode,score+1))
print(res)

# Optimized solution
# ABC132 E
from collections import deque

f=lambda:list(map(int,input().split()))
N,M=f()
G=[[] for _ in [0]*(N+1)]

for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
S=(S,0)
T=(T,0)

q=deque()
q.append(S)
F=set()
res=-1
while q:
    node,r=q.popleft()
    if (node,r%3) in F:
        continue
    if (node,r%3) == T:
        res=r//3
        break
    F.add((node,r%3))
    for next_node in G[node]:
        if (next_node,(r+1)%3) in F:
            continue
        q.append((next_node,r+1))
print(res)
# Original solution
NM=list(map(int,input().split()))
N=NM[0]
M=NM[1]
graph=[[0 for i in range(N)] for j in range(N)]

for i in range(M):
  edge=list(map(int,input().split()))
  graph[edge[0]-1][edge[1]-1]=1
  
ST=list(map(int,input().split()))
S=ST[0]-1
T=ST[1]-1



first=[]
second=[]
third=[]
able=[S]

step=0

while True:
  first=[]
  second=[]
  third=[]
  judge = 0
  for i in range(len(able)):
    for j in range(N):
      if (graph[able[i]][j] == 1) and not (j in first):
        first.append(j)
  for i in range(len(first)):
    for j in range(N):
      if (graph[first[i]][j] == 1) and not (j in second):
        second.append(j)
  for i in range(len(second)):
    for j in range(N):
      if (graph[second[i]][j] == 1) and not (j in third):
        third.append(j)
  for i in range(len(third)):
      if not third[i] in able:
        able.append(third[i])
        judge = 1
  if judge == 0:
    print((-1))
    break
  step+=1
  if T in able:
    print(step)
    break
    
  

      




# Optimized solution
NM=list(map(int,input().split()))
N=NM[0]
M=NM[1]
graph=[[] for j in range(N)]

for i in range(M):
  edge=list(map(int,input().split()))
  graph[edge[0]-1].append(edge[1]-1)
  
ST=list(map(int,input().split()))
S=ST[0]-1
T=ST[1]-1



first=[]
second=[]
third=[]
able=[S]

step=0

while True:
  first=[]
  second=[]
  third=[]
  judge = 0
  for i in range(len(able)):
    for j in range(len(graph[able[i]])):
      if not (graph[able[i]][j] in first):
        first.append(graph[able[i]][j])
  for i in range(len(first)):
    for j in range(len(graph[first[i]])):
      if not (graph[first[i]][j] in second):
        second.append(graph[first[i]][j])
  for i in range(len(second)):
    for j in range(len(graph[second[i]])):
      if not (graph[second[i]][j] in third):
        third.append(graph[second[i]][j])
  for i in range(len(third)):
      if not third[i] in able:
        able.append(third[i])
        judge = 1
  if judge == 0:
    print((-1))
    break
  step+=1
  if T in able:
    print(step)
    break
# Original solution


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

N, M = list(map(int, input().split()))
uv = []
for i in range(M):
	uv.append(list(map(int, input().split())))
S, T = list(map(int, input().split()))
G = [dict() for i in range(N+1)]
for i in range(N + 1):
	G[i]["eda"] = []
	G[i]["second"] = set()
	G[i]["third"] = set()
	G[i]["num"] = -1
for i in range(M):
	G[uv[i][0]]["eda"].append(uv[i][1])
for i in range(N + 1):
	for node in G[i]["eda"]:
		G[i]["second"] = G[i]["second"] | set(G[node]["eda"])
for i in range(N + 1):
	for node in G[i]["eda"]:
		G[i]["third"] = G[i]["third"] | G[node]["second"]

node_set = [S]
G[S]["num"] = 0
times = 1
while True:
	node_set2 = []
	for node in node_set:
		if T in G[node]["third"]:
			print(times)
			exit()
		for node2 in G[node]["third"]:
			if G[node2]["num"] == -1:
				G[node2]["num"] = times
				node_set2.append(node2)

	if len(node_set2) == 0:
		print((-1))
		exit()
	node_set = copy.deepcopy(node_set2)
	times += 1

# Optimized solution


import sys
from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import combinations, permutations

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


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

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

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

dist = [1000000000000000000 for _ in range(3*N)]
que = deque([])
que.append(S)
dist[S] = 0
while len(que) > 0:
	node = que.popleft()
	for edge in graph[node]:
		if dist[edge] > dist[node] + 1:
			dist[edge] = dist[node] + 1
			que.append(edge)

if dist[T] < 100000000000000:
	print((dist[T]//3))
else:
	print((-1))
# Original solution
from sys import stdin
from collections import defaultdict
from collections import deque

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

INF = 10 ** 15
# visit = [False] * ( (N + 1) * 3 )
dist  = [-1] * ( (N) * 3 + 1 )
graph_connection = defaultdict(lambda :[])
graph_cost = defaultdict(lambda :defaultdict(lambda :INF))
#
# def dfs(v,dist_before):
#
#     dist[v] = dist_before + 1
#     next_vertexs = graph_connection[v]
#     for next_v  in next_vertexs :
#         if dist[next_v] == -1:
#             dfs(next_v,dist[v])
#     return 0
#

for cost in  Cs:
    a,b= cost
    for i in range(0,3):
        from_v = a + (i) * N
        to_v = b + (i + 1) % 3 * N
        graph_connection[from_v].append(to_v )

        # from_v = b + (i) * N
        # to_v = a + (i + 1) % 3 * N
        # graph_connection[from_v].append(to_v )

# dist[S] = 0


que = deque()
#(from_v,to_v)
que.append((S,S))

while len(que) != 0:
    from_v, to_v = que.popleft()
    dist[to_v] = dist[from_v] + 1
    if to_v == T:
        break
    for next_v in graph_connection[to_v]:
        if dist[next_v] == -1:
            que.append((to_v,next_v))
if dist[T] < 0:
    print((dist[T] ))
else:
    print((dist[T]//3))


# Optimized solution
from sys import stdin
from collections import defaultdict
from collections import deque

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

INF = 10 ** 15
# visit = [False] * ( (N + 1) * 3 )
dist  = [-1] * ( (N) * 3 + 1 )
graph_connection = defaultdict(lambda :[])
graph_cost = defaultdict(lambda :defaultdict(lambda :INF))
#
# def dfs(v,dist_before):
#
#     dist[v] = dist_before + 1
#     next_vertexs = graph_connection[v]
#     for next_v  in next_vertexs :
#         if dist[next_v] == -1:
#             dfs(next_v,dist[v])
#     return 0
#

for cost in  Cs:
    a,b= cost
    for i in range(0,3):
        from_v = a + (i) * N
        to_v = b + (i + 1) % 3 * N
        graph_connection[from_v].append(to_v )

        # from_v = b + (i) * N
        # to_v = a + (i + 1) % 3 * N
        # graph_connection[from_v].append(to_v )

# dist[S] = 0


que = deque()
#(from_v,to_v)
dist[S] = 0
que.append(S)
while len(que) != 0:
    from_v = que.popleft()
    nexts = graph_connection[from_v]
    for next_v in nexts:
        if dist[next_v] == -1:
            dist[next_v] = dist[from_v] + 1
            que.append(next_v)

if dist[T] < 0:
    print((dist[T] ))
else:
    print((dist[T]//3))