AtCoder Beginner Contest 132 - Hopscotch Addict

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: MEDIUM

Starter code:

Solutions:
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)


import sys
from collections import deque
(n, m) = map(int, input().split())
g = [[] for _ in range(3 * n)]
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[3 * u].append(3 * v + 1)
	g[3 * u + 1].append(3 * v + 2)
	g[3 * u + 2].append(3 * v)
(s, t) = map(int, input().split())
s = 3 * (s - 1)
t = 3 * (t - 1)
depth = dict()
depth[s] = 0
q = deque([s])
while len(q) != 0:
	v = q.popleft()
	for u in g[v]:
		if u not in depth:
			q.append(u)
			depth[u] = depth[v] + 1
print(depth[t] // 3 if t in depth else -1)


(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))
if v[T][0] == -1:
	print('-1')
else:
	print(v[T][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)


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)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(N, M, *UV, S, T) = map(int, read().split())
it = iter(UV)
graph = [[] for _ in range(1 + N + N + N)]
for (x, y) in zip(it, it):
	x1 = x + N
	x2 = x1 + N
	y1 = y + N
	y2 = y1 + N
	graph[x].append(y1)
	graph[x1].append(y2)
	graph[x2].append(y)
INF = 10 ** 15
dist = [INF] * (N + N + N + 1)
dist[S] = 0
q = [S]
while q:
	qq = []
	for x in q:
		for y in graph[x]:
			if dist[y] != INF:
				continue
			qq.append(y)
			dist[y] = dist[x] + 1
	q = qq
d = dist[T]
answer = -1 if d == INF else d // 3
print(answer)


from collections import deque
(N, M) = map(int, input().split())
G = [[[] for j in range(3)] for i in range(N + 1)]
for _ in range(M):
	(u, v) = map(int, input().split())
	for i in range(3):
		G[u][i].append((v, (i + 1) % 3))
(S, T) = map(int, input().split())
visited = [[-1] * 3 for _ in range(N + 1)]
que = deque([(S, 0, 0)])
visited[S][0] = 0
while que:
	(ci, l, d) = que.popleft()
	for (ni, nl) in G[ci][l]:
		if visited[ni][nl] == -1:
			que.append((ni, nl, d + 1))
			visited[ni][nl] = d + 1
print(visited[T][0] // 3)


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)


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)


from collections import deque
(N, M) = map(int, input().split())
(A, B) = zip(*(map(int, input().split()) for _ in range(M))) if M else ((), ())
(S, T) = map(int, input().split())
G = [set() for _ in range(N + 1)]
for (x, y) in zip(A, B):
	G[x].add(y)
INF = 10 ** 10
dp = [[INF for j in range(3)] for i in range(N + 1)]
q = deque()
q.append((S, 0))
dp[S][0] = 0
while q:
	(i, k) = q.popleft()
	L = (k + 1) % 3
	for x in G[i]:
		if dp[x][L] == INF:
			dp[x][L] = dp[i][k] + (1 if L % 3 == 0 else 0)
			q.append((x, L))
ans = -1 if dp[T][0] == INF else dp[T][0]
print(ans)


import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
from functools import lru_cache
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):
		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):
		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):
		d = collections.defaultdict(lambda : float('inf'))
		prev = collections.defaultdict(lambda : None)
		d[s] = 0
		q = []
		heapq.heappush(q, (0, s))
		v = collections.defaultdict(bool)
		while len(q):
			(k, u) = heapq.heappop(q)
			if v[u]:
				continue
			v[u] = True
			for (uv, ud) in self.e[u]:
				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(ans // 3)


(n, m) = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
(s, t) = map(int, input().split())
alist = [[] for _ in range(3 * n)]
for (u, v) in uv:
	(u, v) = (u - 1, v - 1)
	alist[u].append(n + v)
	alist[n + u].append(2 * n + v)
	alist[2 * n + u].append(v)
queue = [s - 1]
visited = [-3] * (3 * n)
visited[s - 1] = 0
while len(queue) > 0:
	q = queue.pop(0)
	for v in alist[q]:
		if visited[v] < 0:
			queue.append(v)
			visited[v] = visited[q] + 1
print(visited[t - 1] // 3)


from collections import deque
(N, M, *L, S, T) = map(int, open(0).read().split())
G = [[] for _ in range(N)]
step = [[-1] * 3 for _ in range(N)]
step[S - 1][0] = 0
for (u, v) in zip(*[iter(L)] * 2):
	G[u - 1].append(v - 1)
q = deque([(S - 1, 0)])
while q:
	(cur, d) = q.popleft()
	for nxt in G[cur]:
		if nxt == T - 1 and (d + 1) % 3 == 0:
			print((d + 1) // 3)
			exit()
		if step[nxt][(d + 1) % 3] < 0:
			step[nxt][(d + 1) % 3] = d + 1
			q.append((nxt, d + 1))
print(-1)


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 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)


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)
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))


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()


(N, M) = map(int, input().split())
E = [[] for i in range(N)]
for i in range(M):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	E[u].append(v)
(S, T) = map(int, input().split())
(S, T) = (S - 1, T - 1)
from collections import deque
stack = deque()
seen = [[False for i in range(3)] for j in range(N)]
stack.append([S, 0, 1])
while stack:
	node = stack.popleft()
	v = node[0]
	step = node[1]
	turn = node[2]
	if step == 3:
		if v == T:
			print(turn)
			break
		step = 0
		turn += 1
	if seen[v][step]:
		continue
	seen[v][step] = True
	children = E[v]
	for child in children:
		stack.append([child, step + 1, turn])
else:
	print(-1)


(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 = []
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)


from collections import deque
(n, m) = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	g[u].append(v)
(s, t) = map(int, input().split())
(s, t) = (s - 1, t - 1)
visited = [[-1] * 3 for j in range(n)]
l = 0
queue = deque([[s, l]])
visited[s][l] = 0
while queue:
	(x, l) = queue.popleft()
	if [x, l] == [t, 0]:
		print(visited[x][l] // 3)
		exit()
	for x_ in g[x]:
		(new_x, new_l) = (x_, (l + 1) % 3)
		if visited[new_x][new_l] == -1:
			visited[new_x][new_l] = visited[x][l] + 1
			queue.append([new_x, new_l])
print(visited[t][0])


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()


from collections import deque
(n, m) = map(int, input().split())
edge = [[] for i in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	edge[u].append(v)
(s, t) = map(int, input().split())
queue = deque()
queue.append((s, 0))
visited = [[False] * 3 for _ in range(n + 1)]
while queue:
	(u, d) = queue.popleft()
	if visited[u][d % 3]:
		continue
	visited[u][d % 3] = True
	if d % 3 == 0 and u == t:
		print(d // 3)
		exit()
	for v in edge[u]:
		queue.append((v, d + 1))
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)


(N, M) = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(M)]
inf = 10 ** 20
c = [[] for i in range(N * 3)]
for (i, j) in edge:
	c[i - 1].append(N + j - 1)
	c[N + i - 1].append(N + N + j - 1)
	c[N + N + i - 1].append(j - 1)
(S, T) = map(int, input().split())
from collections import deque

def bfs(c, N, S):
	d = [inf] * N
	d[S] = 0
	q = deque([S])
	x = 1
	while len(q) > 0:
		q2 = deque()
		for i in q:
			for j in c[i]:
				if d[j] > x:
					d[j] = x
					q2.append(j)
		q = q2
		x += 1
	return d
d = bfs(c, N * 3, S - 1)
print(d[T - 1] // 3 if d[T - 1] < inf else -1)


from collections import deque
(n, m) = map(int, input().split())
graph = [[] for i in range(3 * n)]
for i in range(m):
	(s, e) = map(int, input().split())
	graph[s - 1].append(e + n - 1)
	graph[s + n - 1].append(e + 2 * n - 1)
	graph[s + 2 * n - 1].append(e - 1)
(s, t) = map(int, input().split())
s -= 1
t -= 1
queue = deque([s])
length = 0
dist = [-1] * (3 * n)
dist[s] = 0
while queue:
	v = queue.popleft()
	for i in graph[v]:
		if dist[i] != -1:
			continue
		dist[i] = dist[v] + 1
		queue.append(i)
print(dist[t] if dist[t] == 1 else dist[t] // 3)


(N, M) = map(int, input().split())
g = {}
for v in range(1, N * 3 + 1):
	g[v] = []
for _ in range(M):
	(u, v) = map(int, input().split())
	g[u + N * 0].append(v + N * 1)
	g[u + N * 1].append(v + N * 2)
	g[u + N * 2].append(v + N * 0)
(S, T) = map(int, input().split())
visiting = [S]
visited = {S: 0}
while visiting:
	v = visiting.pop(0)
	if v == T:
		break
	for v2 in g[v]:
		if v2 not in visited:
			visiting.append(v2)
			visited[v2] = visited[v] + 1
if T in visited:
	print(visited[T] // 3)
else:
	print(-1)


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)


from collections import deque
(N, M) = map(int, input().split())
data = [[] for _ in range(3 * N)]
for i in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	data[3 * u].append(3 * v + 1)
	data[3 * u + 1].append(3 * v + 2)
	data[3 * u + 2].append(3 * v)
(S, T) = map(int, input().split())
S -= 1
T -= 1
inf = 10 ** 6
stack = deque([[3 * S, 0]])
time = [inf] * (3 * N)
while stack:
	x = stack.popleft()
	for y in data[x[0]]:
		if time[y] > x[1] + 1:
			time[y] = x[1] + 1
			stack.append([y, x[1] + 1])
if time[3 * T] == inf:
	print(-1)
else:
	print(time[3 * T] // 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 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)

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)
if costs[3 * T] == INF:
	print(-1)
else:
	print(costs[3 * T] // 3)


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()))
(N, M) = lr()
graph = [[] for _ in range((N + 1) * 3)]
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) = map(int, input().split())
graph = [[] for _ 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
q = deque([(S, 0)])
visited = [[0] * 3 for _ in range(N)]
visited[S][0] = 1
flg = True
res = -1
while q and flg:
	v = q.popleft()
	for n_v in graph[v[0]]:
		n_dist = v[1] + 1
		if n_v == T and n_dist % 3 == 0:
			res = n_dist // 3
			flg = False
			break
		if not visited[n_v][n_dist % 3]:
			visited[n_v][n_dist % 3] = 1
			q.append((n_v, n_dist))
print(res)


from collections import deque
(N, M) = map(int, input().split())
E = {u: set() for u in range(1, N + 1)}
for i in range(M):
	(u, v) = map(int, input().split())
	E[u].add(v)
(S, T) = map(int, input().split())
X = {}
for u in E:
	for i in range(3):
		X[u, i] = set([(v, (i + 1) % 3) for v in E[u]])
queue = deque()
queue.append(((S, 0), 0))
visited = set()
while len(queue) > 0:
	(u, n) = queue.popleft()
	if u in visited:
		continue
	visited.add(u)
	if u == (T, 0):
		print(n // 3)
		exit()
	for v in X[u]:
		queue.append((v, n + 1))
print(-1)


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

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	M = int(next(tokens))
	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))
	T = int(next(tokens))
	solve(N, M, G, S, T)

def __starting_point():
	main()
__starting_point()


(n, m) = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(m):
	tmp = list(map(int, input().split()))
	link[tmp[0] - 1].append(tmp[1] - 1)
(s, t) = map(int, input().split())
from collections import deque
Q = deque()
Q.append([s - 1, 0, 0])
visited = [[] for _ in range(n)]
visited[s - 1] = [0]
while Q:
	(now, kkp, cnt) = Q.popleft()
	nxt_kkp = (kkp + 1) % 3
	for nxt in link[now]:
		if nxt == t - 1 and nxt_kkp == 0:
			print((cnt + 1) // 3)
			exit()
		if nxt_kkp in visited[nxt]:
			continue
		visited[nxt].append(nxt_kkp)
		Q.append([nxt, nxt_kkp, cnt + 1])
print(-1)


from collections import deque
(n, m) = map(int, input().split())
edges = [[] for i in range(3 * n)]
for i in range(m):
	(u, v) = 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) = 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 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 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
input = sys.stdin.readline
(N, M) = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]
(S, G) = map(int, input().split())
ELIST = [[] for i in range(N + 1)]
for (x, y) in E:
	ELIST[x].append(y)
DIS = [[-1, -1, -1] for i in range(N + 1)]
DIS[S][0] = 0
from collections import deque
S = deque([S])
i = 1
while S:
	NEWS = deque()
	while S:
		x = S.pop()
		for to in ELIST[x]:
			if DIS[to][i % 3] == -1:
				DIS[to][i % 3] = i
				NEWS.append(to)
	i += 1
	S = NEWS
print(DIS[G][0] // 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 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)
(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)


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[t][0])


(N, M) = map(int, input().split())
G = [[] for i in range(3 * N)]
L = [-2 for i in range(3 * N)]
for i in range(0, M):
	(u, v) = map(int, input().split())
	G[N * 0 + u - 1].append(N * 1 + v - 1)
	G[N * 1 + u - 1].append(N * 2 + v - 1)
	G[N * 2 + u - 1].append(N * 0 + v - 1)
(S, T) = map(int, input().split())
S = S - 1
T = T - 1
L[S] = 0
Now = [S]
while Now:
	x = Now.pop(0)
	for i in range(len(G[x])):
		g = G[x]
		if L[g[i]] < 0:
			L[g[i]] = L[x] + 1
			Now.append(g[i])
print(L[T] // 3)


import sys
from collections import deque
read = sys.stdin.read
(N, M, *uv, S, T) = map(int, read().split())
graph = [[] for _ in range(N + 1)]
for (u, v) in zip(*[iter(uv)] * 2):
	graph[u].append(v)
INF = 10 ** 15
dist = [[INF] * (N + 1) for _ in range(3)]
stack = deque([(0, S)])
while stack:
	(cost, v) = stack.popleft()
	if dist[cost % 3][v] != INF:
		continue
	dist[cost % 3][v] = cost
	for i in graph[v]:
		stack.append((cost + 1, i))
if dist[0][T] == INF:
	print(-1)
else:
	print(dist[0][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())


import sys
from collections import deque
input = sys.stdin.readline
(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n + 1)]
for (a, b) in ab:
	graph[a].append(b)
(s, t) = map(int, input().split())
visited = [[-1, -1, -1] for i in range(n + 1)]
que = deque([(s, 0, 0)])
while que:
	(x, mod, cnt) = que.popleft()
	visited[x][mod] = cnt
	if x == t and mod == 0:
		break
	for y in graph[x]:
		if visited[y][(mod + 1) % 3] == -1:
			que.append((y, (mod + 1) % 3, cnt + 1))
			visited[y][(mod + 1) % 3] = cnt + 1
print(visited[t][0] // 3)


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
(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)


from collections import deque
import sys
input = sys.stdin.readline
(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())
queue = deque()
queue.append((S, 0))
visited = [[False] * 3 for _ in range(N + 1)]
while queue:
	(u, d) = queue.popleft()
	if visited[u][d % 3]:
		continue
	visited[u][d % 3] = True
	if d % 3 == 0 and u == T:
		print(d // 3)
		exit()
	for v in G[u]:
		queue.append((v, d + 1))
print(-1)


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()


(N, M) = map(int, input().split())
a = [[] for i in range(N + 1)]
for i in range(M):
	(u, v) = map(int, input().split())
	a[u].append(v)
(S, T) = 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:
			for v in a[u]:
				if v == T and count % 3 == 0:
					return count // 3
				if not m[v][count % 3]:
					m[v][count % 3] = True
					c2.append(v)
		c = c2
	return -1
print(main())


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

def search(vs, S, T):
	queue = [(S, 0)]
	dists = [[-1] * (N + 1) for _ in range(3)]
	while queue:
		(n, d) = queue.pop(0)
		d += 1
		dr = d % 3
		dists_tmp = dists[dr]
		for n2 in vs[n]:
			if dr == 0 and n2 == T:
				return d // 3
			if dists_tmp[n2] < 0:
				dists_tmp[n2] = d
				queue.append((n2, d))
	return -1
print(search(vs, S, T))


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)


from collections import deque
(n, m) = map(int, input().split())
F = [set() for _ in range(3 * n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u = (u - 1) * 3
	v = (v - 1) * 3
	F[u].add(v + 1)
	F[u + 1].add(v + 2)
	F[u + 2].add(v)
(s, t) = map(int, input().split())
s = (s - 1) * 3
t = (t - 1) * 3
dist = [-1] * (3 * n)
dist[s] = 0
dq = deque([s])
while dq:
	v = dq.popleft()
	for nv in F[v]:
		if dist[nv] != -1:
			continue
		dist[nv] = dist[v] + 1
		dq.append(nv)
		if nv == t:
			break
	else:
		continue
	break
print(dist[t] // 3)


(n, m) = map(int, input().split())
f = [[] for i in range(3 * n)]
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	f[u].append(v + n)
	f[u + n].append(v + 2 * n)
	f[u + 2 * n].append(v)
(s, t) = map(int, input().split())
s -= 1
t -= 1
stack = [s]
stack_new = []
used = [-1 for i in range(3 * n)]
time = 0
while len(stack) > 0:
	now = stack.pop()
	if used[now] == -1:
		used[now] = time
		if now == t:
			print(time // 3)
			exit()
		stack_new += f[now]
	if len(stack) == 0:
		stack = stack_new
		stack_new = []
		time += 1
print(-1)


def main():
	(n, m) = map(int, input().split())
	ab = [list(map(int, input().split())) for _ in [0] * m]
	g = [[] for _ in [0] * n]
	[g[a - 1].append(b - 1) for (a, b) in ab]
	(s, t) = map(int, input().split())
	visit = [[False] * 3 for _ in [0] * n]
	s -= 1
	t -= 1
	visit[s][0] = True
	cnt = 0
	q = [s]
	while q:
		qq = []
		cnt += 1
		c = cnt % 3
		for i in q:
			for j in g[i]:
				if visit[j][c] == False:
					visit[j][c] = True
					qq.append(j)
		q = qq
		if visit[t][0]:
			print(cnt // 3)
			break
	else:
		print(-1)
main()


import collections
(N, M) = map(int, input().split())
G = [[] for i in range(3 * N + 1)]
for i 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())

def bfs(s):
	que = collections.deque()
	que.append(s)
	d = [-1 for _ in range(3 * N + 1)]
	d[s] = 0
	while 0 < len(que):
		p = que.popleft()
		if T == p:
			return d[p]
		for pp in G[p]:
			if d[pp] == -1:
				que.append(pp)
				d[pp] = d[p] + 1
	return -1
ans = bfs(S)
if -1 == ans:
	print(-1)
else:
	print(ans // 3)


from collections import deque
import sys
(n, m) = map(int, input().split())
g = [[] for _ in range(3 * n)]
for _ in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	u -= 1
	v -= 1
	g[u].append(n + v)
	g[u + n].append(v + 2 * n)
	g[u + 2 * n].append(v)
(s, t) = map(int, input().split())
s -= 1
t -= 1
vit = set([s])
ans = [-3] * 3 * n
q = deque([s])
ans[s] = 0
while q:
	a = q.popleft()
	for b in g[a]:
		if b in vit:
			continue
		vit.add(b)
		ans[b] = ans[a] + 1
		q.append(b)
print(ans[t] // 3)


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
	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()


from heapq import heappush, heappop

class Dijkstra:

	def __init__(self, N):
		self.N = N
		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
		self.prev = prev = [-1] * N
		dist[s] = 0
		n_visited = 1
		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 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()


from collections import deque

def read_tuple():
	return map(int, input().split())
(N, M) = read_tuple()
E = [[] for i in range(N + 1)]
for i in range(M):
	(u, v) = read_tuple()
	E[u].append(v)
(S, T) = read_tuple()
dst = [[-1, -1, -1] for i in range(N + 1)]
dst[S][0] = 0
Q = deque([(S, 0)])
while len(Q):
	(v, c) = Q.popleft()
	for u in E[v]:
		k = (c + 1) % 3
		if dst[u][k] == -1:
			dst[u][k] = c + 1
			Q.append((u, c + 1))
print(dst[T][0] // 3 if dst[T][0] != -1 else -1)


from collections import deque
(N, M) = map(int, input().split())
INF = 1001001001
dist = [[INF for _ in range(3)] for _ in range(N)]
G = [[] for _ in range(N)]
for i in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	G[u].append(v)
(S, T) = map(int, input().split())
S -= 1
T -= 1
q = deque()
q.append((S, 0))
dist[S][0] = 0
while q:
	(k, l) = q.popleft()
	for i in G[k]:
		nl = (l + 1) % 3
		if dist[i][nl] == INF:
			dist[i][nl] = dist[k][l] + 1
			q.append((i, nl))
ans = dist[T][0]
if ans == INF:
	ans = -1
else:
	ans //= 3
print(ans)


(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())
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)


from collections import deque
(n, m) = map(int, input().split())
w = [set() for _ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	w[u].add(v)
(s, t) = map(int, input().split())
l = [[-1, -1, -1] for _ in range(n + 1)]
d = deque()
d.append((s, 0, 0))
while d:
	(i, q, r) = d.popleft()
	for _w in w[i]:
		if _w == t and r == 2:
			print((q + 1) // 3)
			exit()
		if l[_w][(r + 1) % 3] == -1:
			l[_w][(r + 1) % 3] = q + 1
			d.append((_w, q + 1, (r + 1) % 3))
print(-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())
	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))
	ans = d[t][0]
	print(ans // 3 if ans != INF else -1)

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
(N, M) = map(int, input().split())
Edge = [[] for _ in range(3 * N)]
for _ in range(M):
	(u, v) = map(int, sys.stdin.readline().split())
	u -= 1
	v -= 1
	Edge[u].append(N + v)
	Edge[N + u].append(2 * N + v)
	Edge[2 * N + u].append(v)
(S, T) = map(int, input().split())
S -= 1
T -= 1
Q = deque([S])
visited = set([S])
dist = [-3] * (3 * N)
dist[S] = 0
while Q:
	vn = Q.pop()
	for vf in Edge[vn]:
		if vf in visited:
			continue
		visited.add(vf)
		dist[vf] = dist[vn] + 1
		Q.appendleft(vf)
print(dist[T] // 3)


from collections import defaultdict, deque
(N, M) = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
	(u, v) = map(int, input().split())
	G[u - 1, 0].append((v - 1, 1))
	G[u - 1, 1].append((v - 1, 2))
	G[u - 1, 2].append((v - 1, 0))
(S, T) = map(int, input().split())
dist = defaultdict(lambda : -1)
que = deque([(S - 1, 0)])
dist[S - 1, 0] = 0
while que:
	v = que.popleft()
	d = dist[v]
	for nv in G[v]:
		if dist[nv] >= 0:
			continue
		dist[nv] = d + 1
		que.append(nv)
print(dist[T - 1, 0] // 3)


(N, M) = map(int, input().split())
from collections import defaultdict, deque
graph = defaultdict(list)
for i in range(M):
	(u, v) = map(int, input().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) = map(int, input().split())
S -= 1
T -= 1
dist = [-1] * (3 * N)
dist[S] = 0
q = deque([S])
while q:
	v = q.popleft()
	d = dist[v]
	Vs = graph[v]
	for u in Vs:
		if dist[u] == -1:
			q.append(u)
			dist[u] = d + 1
if dist[T] != float('inf') and dist[T] % 3 == 0:
	print(dist[T] // 3)
else:
	print(-1)


from collections import deque
(N, M) = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
(S, T) = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for (u, v) in edges:
	graph[u].append(v)
INF = 10 ** 9 + 7
dp = [[INF] * (N + 1) for _ in range(3)]
dp[0][S] = 0
q = deque()
q.append((S, 0))
while q:
	(v, t) = q.popleft()
	u = (t + 1) % 3
	d = dp[t][v]
	if t == 2:
		d += 1
	for w in graph[v]:
		if dp[u][w] != INF:
			continue
		dp[u][w] = d
		q.append((w, u))
print(dp[0][T] if dp[0][T] < INF else -1)


import heapq
(N, M) = map(int, input().split())
L = [[] for i in range(3 * N)]
for i in range(M):
	(u, v) = 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) = 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)


from collections import Counter, deque
import sys
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()


import sys
import heapq
import math
input = sys.stdin.readline
(N, M) = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(M)]
(S, T) = map(int, input().split())
g = [[] for _ in range(3 * N)]
for (a, b) in uv:
	g[a - 1].append(b - 1 + N)
	g[a - 1 + N].append(b - 1 + 2 * N)
	g[a - 1 + 2 * N].append(b - 1)
hq = [(0, S - 1)]
costs = [math.inf] * 3 * N
while len(hq) > 0:
	(c, u) = heapq.heappop(hq)
	if u == T - 1:
		print(c // 3)
		sys.exit()
	costs[u] = c
	for v in g[u]:
		if costs[v] > c + 1:
			heapq.heappush(hq, (c + 1, v))
		costs[v] = min(costs[v], c + 1)
print(-1)


import collections
(n, m) = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)
(s, t) = map(int, input().split())
check = [[0] * 3 for _ in range(n + 1)]
check[s][0] = 1
q = collections.deque()
q.append([s, 0])
ans = 0
while len(q) != 0:
	(v, c) = q.popleft()
	if v == t and c % 3 == 0:
		ans = c // 3
		break
	for i in g[v]:
		if check[i][(c + 1) % 3] == 0:
			q.append([i, c + 1])
			check[i][(c + 1) % 3] = 1
if ans == 0:
	print(-1)
else:
	print(ans)


from collections import deque
import sys
(n, m) = list(map(int, input().split()))
edges = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	edges[u].append(v)
(s, t) = list(map(int, input().split()))
visited = [[] for _ in range(n + 1)]
q = deque()
q.append((s, 0))
while q:
	(node, cnt) = q.popleft()
	if cnt % 3 in visited[node]:
		continue
	if node == t and cnt % 3 == 0:
		print(cnt // 3)
		sys.exit()
	else:
		visited[node].append(cnt % 3)
		for e in edges[node]:
			q.append((e, cnt + 1))
print(-1)


import sys
from collections import defaultdict, deque
input = sys.stdin.readline
(N, M) = 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) = 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 collections import deque
(n, m) = map(int, input().split())
g = [[] * 1 for i in range(n * 3)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a * 3 + 0].append(b * 3 + 1)
	g[a * 3 + 1].append(b * 3 + 2)
	g[a * 3 + 2].append(b * 3 + 0)
(s, t) = map(int, input().split())
s -= 1
t -= 1
d = [-1 for i in range(n * 3)]
q = deque([])
q.append(s * 3 + 0)
d[s * 3 + 0] = 0
while q:
	v = q.popleft()
	for to in g[v]:
		if d[to] == -1:
			d[to] = d[v] + 1
			q.append(to)
if d[t * 3 + 0] == -1:
	print(-1)
else:
	print(d[t * 3 + 0] // 3)


from collections import *
(n, m, *t) = map(int, open(0).read().split())
(*w, s, t) = [t - 1 for t in t]
e = [[] for _ in range(n)]
for (u, v) in zip(w[::2], w[1::2]):
	e[u].append(v)
INF = 10 ** 18
f = [[INF] * 3 for _ in range(n)]
f[s][0] = 0
q = deque([(s, 0)])
while q:
	(v, m) = q.popleft()
	if v == t and m == 0:
		print(f[v][0] // 3)
		break
	for w in e[v]:
		if f[w][-~m % 3] < INF:
			continue
		f[w][-~m % 3] = f[v][m] + 1
		q.append((w, -~m % 3))
else:
	print(-1)


from collections import deque
(N, M) = map(int, input().split())
G = dict()
for i in range(1, 3 * N + 1):
	G[i] = dict()
for _ in range(M):
	(u, v) = map(int, input().split())
	G[u][N + v] = 1
	G[N + u][2 * N + v] = 1
	G[2 * N + u][v] = 1
(S, T) = map(int, input().split())
dist_S = [3 * N + 1] * (3 * N + 1)
dist_S[S] = 0
queue = deque([S])
while len(queue) > 0:
	p = queue.popleft()
	for q in G[p].keys():
		if dist_S[p] + 1 < dist_S[q]:
			dist_S[q] = dist_S[p] + 1
			queue.append(q)
if dist_S[T] < 3 * N + 1:
	print(dist_S[T] // 3)
else:
	print(-1)


import heapq

def sol(inp=input):
	s = 3
	(n, m) = map(int, inp().split())
	G = {(i + 1, j): set() for i in range(n) for j in range(s)}
	for _ in range(m):
		(u, v) = map(int, inp().split())
		for i in range(s):
			G[u, i].add((v, (i + 1) % s))
	(s, t) = map(int, inp().split())
	visited = {(s, 0)}
	que = []
	heapq.heappush(que, (0, (s, 0)))
	while len(que) > 0:
		(step, u) = heapq.heappop(que)
		for v in G[u]:
			if v not in visited:
				visited.add(v)
				heapq.heappush(que, (step + 1, v))
			if v == (t, 0):
				return (step + 1) // 3
	return -1
print(sol())


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)


from collections import deque
INF = -1
(N, M) = [int(e) for e in input().split(' ')]
to = [[] for _ in range(N)]
for i in range(M):
	(u, v) = [int(e) for e in input().split(' ')]
	to[u - 1].append(v - 1)
(S, T) = [int(e) - 1 for e in input().split(' ')]
dist = [[INF for i in range(3)] for j in range(N)]
q = deque([])
q.append([S, 0])
dist[S][0] = 0
while q:
	(v, l) = q.popleft()
	for v_to in to[v]:
		nl = (l + 1) % 3
		if dist[v_to][nl] != INF:
			continue
		dist[v_to][nl] = dist[v][l] + 1
		q.append([v_to, nl])
ans = dist[T][0]
if ans == INF:
	ans = -1
else:
	ans = ans // 3
print(ans)


(N, M) = map(int, input().split())
uv = {}
for i in range(M):
	(u, v) = map(int, input().split())
	if not u in uv:
		uv[u] = [v]
	else:
		uv[u].append(v)
(S, T) = map(int, input().split())
b = [[False] * (10 ** 5 + 1) for i in range(3)]
us = [S]
b[-1][S] = True
cnt = 0
while us:
	cnt += 1
	for i in range(3):
		tmpus = []
		for u in us:
			if u in uv:
				for v in uv[u]:
					if b[i][v] is False:
						b[i][v] = True
						tmpus.append(v)
		us = tmpus
	if T in us:
		print(cnt)
		break
if not T in us:
	print(-1)


import sys
readline = sys.stdin.buffer.readline
from collections import deque
(N, M) = map(int, input().split())
UV = [list(map(int, input().split())) for _ in range(M)]
(S, T) = map(int, input().split())
INF = 10 ** 15
if M == 0:
	print(-1)
	exit()
graph = [[] for _ in range(3 * M + 1)]
for (u, v) in UV:
	graph[u].append(v + M)
	graph[u + M].append(v + 2 * M)
	graph[u + 2 * M].append(v)
queue = deque([S])
dist = [INF] * (3 * M + 1)
dist[S] = 0
while queue:
	q = queue.popleft()
	for g in graph[q]:
		if dist[g] > dist[q] + 1:
			dist[g] = dist[q] + 1
			queue.append(g)
print(dist[T] // 3 if dist[T] != INF else -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)


from collections import deque
(n, m) = map(int, input().split())
g = [[] for _ in range(3 * n)]
v = [-1 for _ in range(3 * n)]
for i in range(m):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	g[x].append(y + n)
	g[x + n].append(y + 2 * n)
	g[x + 2 * n].append(y)
(s, t) = map(int, input().split())
(s, t) = (s - 1, t - 1)

def bfs(x, y):
	q = deque()
	q.append(x)
	v[x] = 0
	while q:
		p = q.popleft()
		for nb in g[p]:
			if v[nb] == -1:
				q.append(nb)
				v[nb] = v[p] + 1
				if nb == t:
					return v[t] // 3
	return -1
print(bfs(s, t))


(N, M) = map(int, input().split())
E = [[] for _ in range(N + 1)]
for _ in range(M):
	(u, v) = map(int, input().split())
	E[u].append(v)
Closed = [[False] * (N + 1) for _ in range(3)]
(S, T) = map(int, input().split())
st = [(S, 0)]
Closed[0][S] = True
ans = 0
while len(st):
	st_new = []
	for (v, n) in st:
		if v == T and n == 0:
			print(ans // 3)
			exit()
		n1 = (n + 1) % 3
		Cl = Closed[n1]
		for u in E[v]:
			if not Cl[u]:
				st_new.append((u, n1))
				Cl[u] = True
	st = st_new
	ans += 1
print(-1)


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
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)


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()))
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)


from collections import deque
(n, m) = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
(s, t) = 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)


(n, m) = map(int, input().split())
lst = [[] for i in range(3 * n + 1)]
dist = [-1 for i in range(3 * n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	lst[u].append(v + n)
	lst[u + n].append(v + 2 * n)
	lst[u + 2 * n].append(v)
(s, t) = map(int, input().split())
next = lst[s]
next_next = []
not_empty = True
cost = 1
while not_empty:
	not_empty = False
	for i in next:
		if dist[i] == -1:
			dist[i] = cost
			next_next.extend(lst[i])
			not_empty = True
	next = next_next.copy()
	next_next = []
	cost += 1
if dist[t] != -1:
	print(dist[t] // 3)
else:
	print(-1)


import collections
(N, M) = map(int, input().split())
edge = collections.defaultdict(list)
for _ in range(M):
	(u, v) = map(int, input().split())
	edge[u - 1].append(v - 1)
(S, T) = map(int, input().split())
dp = [[-3 for _ in range(3)] for _ in range(N)]
dp[S - 1][0] = 0
q = collections.deque()
q.append((S - 1, 0))
while q:
	(p, step) = q.popleft()
	next_step = (step + 1) % 3
	for e in edge[p]:
		if dp[e][next_step] == -3:
			dp[e][next_step] = dp[p][step] + 1
			q.append((e, next_step))
			if e == T - 1 and next_step == 0:
				break
print(dp[T - 1][0] // 3)


from collections import deque
import sys
readline = sys.stdin.readline
(N, M) = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
	(u, v) = map(int, readline().split())
	G[u - 1].append(v - 1)
(S, T) = map(int, readline().split())
S -= 1
T -= 1
INF = 10 ** 9
U = [[INF] * N for i in range(3)]
U[0][S] = 0
que = deque([(S, 0)])
while que:
	(v, t) = que.popleft()
	u = (t + 1) % 3
	d = U[t][v]
	if t == 2:
		d += 1
	Uu = U[u]
	for w in G[v]:
		if Uu[w] != INF:
			continue
		que.append((w, u))
		Uu[w] = d
print(U[0][T] if U[0][T] < INF else -1)


(N, M) = [int(i) for i in input().split()]
UVm = [[int(i) for i in input().split()] for _ in range(M)]
(S, T) = [int(i) for i in input().split()]
graphs = [[] for _ in range(3 * N)]
dists = [-1 for _ in range(3 * N)]
for uv in UVm:
	u = uv[0] - 1
	v = uv[1] - 1
	graphs[u].append(v + N)
	graphs[u + N].append(v + 2 * N)
	graphs[u + 2 * N].append(v)
from collections import deque
que = deque()
que.append(S - 1)
dists[S - 1] = 0
while len(que) > 0:
	nex = que.popleft()
	for edge in graphs[nex]:
		if dists[edge] != -1:
			continue
		que.append(edge)
		dists[edge] = dists[nex] + 1
print(dists[T - 1] // 3)


(n, m) = map(int, input().split())
data = [[] for i in range(3 * n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	data[u].append(v + n)
	data[u + n].append(v + 2 * n)
	data[u + 2 * n].append(v)
(s, t) = 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)


from collections import deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
INF = 10 ** 9
to = [[] for _ in range(n)]
dist = [[INF] * n for _ in range(3)]
for _ in range(m):
	(u, v) = map(int, input().split())
	to[u - 1].append(v - 1)
(s, t) = map(int, input().split())
s -= 1
t -= 1
dist[0][s] = 0
que = deque([(s, 0)])
while que:
	(u, prv) = que.popleft()
	d = dist[prv][u]
	cur = (prv + 1) % 3
	if prv == 2:
		d += 1
	for v in to[u]:
		if dist[cur][v] != INF:
			continue
		que.append((v, cur))
		dist[cur][v] = d
print(dist[0][t] if dist[0][t] < INF else -1)


(n, m) = map(int, input().split())
if m == 0:
	print(-1)
	exit()
es = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	es[u].append(v)
(s, t) = 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 es[u]:
			if dist[v][r] == INF:
				dist[v][r] = d
				qq.append(v)
	q = qq
d = dist[t][0]
print(-1 if d == INF else d // 3)


from collections import *
from itertools import *
from bisect import *
from heapq import *
import math
from fractions import gcd
import sys
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)


from collections import deque
f = lambda : 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)


from collections import deque
(n, m) = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
	(u, v) = map(int, input().split())
	graph[u].append(v)
(s, t) = 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)


from collections import *
(n, m) = map(int, input().split())
e = [[] for _ in range(3 * (n + 1))]
d = [-3] * (3 * (n + 1))
for _ in range(m):
	(a, b) = map(int, input().split())
	e[a] += [b + n]
	e[a + n] += [b + 2 * n]
	e[a + 2 * n] += [b]
(s, t) = map(int, input().split())
q = deque([s])
d[s] = 0
while q:
	now = q.popleft()
	for to in e[now]:
		if d[to] != -3:
			continue
		d[to] = d[now] + 1
		q.append(to)
print(d[t] // 3)


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)


from collections import deque
(n, m) = map(int, input().split())
if m == 0:
	print(-1)
	exit()
path = [[] for _ in range(3 * n)]
for i in range(m):
	(u, v) = map(int, input().split())
	path[3 * (u - 1)].append(3 * (v - 1) + 1)
	path[3 * (u - 1) + 1].append(3 * (v - 1) + 2)
	path[3 * (u - 1) + 2].append(3 * (v - 1))
(s, t) = map(int, input().split())
s -= 1
t -= 1
visited = [0] * (3 * m)
q = deque([3 * s])
visited[3 * s] = 1
while q:
	x = q.popleft()
	if x % 3 == 0 and x // 3 == t:
		print(visited[x] // 3)
		exit()
	for i in path[x]:
		if visited[i] == 0:
			visited[i] = visited[x] + 1
			q.append(i)
print(-1)


from collections import deque
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(lambda x: int(x) - 1, input().split())
	g[u].append(v)
(s, t) = map(lambda x: int(x) - 1, input().split())
d = [[-1, -1, -1] for _ in range(n)]
m = 0
p = 0
d[s][0] = 0
queue = deque([(s, 0)])
while queue:
	(i, p0) = queue.popleft()
	p1 = (p0 + 1) % 3
	for j in g[i]:
		if d[j][p1] >= 0:
			continue
		d[j][p1] = d[i][p0] + 1
		if j == t and p1 == 0:
			print(d[j][p1] // 3)
			quit()
		queue.append((j, p1))
print(-1)


import sys
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 9)
(n, m) = map(int, input().split())
edges = [[] for i in range(3 + 3 * n)]
o = inputs()
(s, T) = map(int, o.pop().split())
for i in o:
	(_, __) = map(int, i.split())
	_ *= 3
	__ *= 3
	edges[_].append(__ + 1)
	edges[_ + 1].append(__ + 2)
	edges[_ + 2].append(__)
from collections import deque
dq = deque([])
dq.append((3 * s, 0))
T *= 3
seen = set()
seen.add(3 * s)
while dq:
	(now, c) = dq.popleft()
	if now == T:
		print(c // 3)
		exit()
	for t in edges[now]:
		if t not in seen:
			dq.append((t, c + 1))
			seen.add(t)
print('-1')


(N, M) = map(int, input().split())
import time
start_t = time.time()
path = [[] for _ in range(N + 3)]
for _ in range(M):
	(u, v) = map(int, input().split())
	path[u].append(v)
(S, T) = map(int, input().split())
import collections
q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N + 3)]
vis[S][0] = 1
q.append([S, 0])
while len(q):
	(now, cnt) = q.popleft()
	step = cnt % 3
	for x in path[now]:
		if vis[x][(step + 1) % 3] < 0:
			vis[x][(step + 1) % 3] = cnt
			q.append((x, cnt + 1))
if vis[T][0] == -1:
	print(-1)
else:
	print(vis[T][0] // 3 + 1)


from collections import deque
inf = float('inf')
(n, m) = map(int, input().split())
es = [[] for _ in range(n * 3)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	es[u].append(v + n)
	es[u + n].append(v + n * 2)
	es[u + n * 2].append(v)
(s, t) = map(int, input().split())
s -= 1
t -= 1
dq = deque()
dq.append(s)
can = False
dist = [inf] * (n * 3)
dist[s] = 0
while dq:
	v = dq.popleft()
	if v == t:
		can = True
		break
	for nv in es[v]:
		if dist[nv] == inf:
			dq.append(nv)
			dist[nv] = dist[v] + 1
if not can:
	print(-1)
else:
	print(dist[t] // 3)


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 defaultdict, deque
(n, m) = list(map(int, input().split()))
graph = defaultdict(list)
for i in range(m):
	(u, v) = list(map(int, input().split()))
	graph[u].append(v + n)
	graph[u + n].append(v + 2 * n)
	graph[u + 2 * n].append(v)
(s, t) = list(map(int, input().split()))
dist = [-1 for i in range(3 * n + 10)]

def bfs():
	que = deque([s])
	dist[s] = 0
	while len(que) > 0:
		cur = que.popleft()
		for to in graph[cur]:
			if dist[to] == -1:
				dist[to] = dist[cur] + 1
				que.append(to)
bfs()
print(dist[t] // 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)


(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)


(n, m) = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
(s, t) = 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)
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


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)


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:
				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 collections import deque
(N, M) = map(int, input().split())
es = [[] for _ in range(3 * N)]
for _ in range(M):
	(u, v) = 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) = 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)
				exit()
			q.append(nxt)
print(-1)


import sys
input = sys.stdin.readline
from queue import *
(N, M) = map(int, input().split())
N *= 3
es = [[] for i in range(N)]
for i in range(M):
	(u, v) = map(lambda x: (int(x) - 1) * 3, input().split())
	es[u].append(v + 1)
	es[u + 1].append(v + 2)
	es[u + 2].append(v)
(S, T) = map(lambda x: (int(x) - 1) * 3, input().split())
dist = [-1 for i in range(N)]
dist[S] = 0
q = Queue()
q.put(S)
while not q.empty():
	v = q.get()
	for u in es[v]:
		if dist[u] == -1:
			dist[u] = dist[v] + 1
			q.put(u)
if dist[T] != -1:
	print(dist[T] // 3)
else:
	print(-1)


from collections import deque
(n, m) = map(int, input().split())
l = [list() for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	l[a].append(b)
(s, t) = map(int, input().split())
reach = [[-1, -1, -1] for _ in range(n + 1)]
reach[s][0] = 0
bfs = deque()
bfs.append((s, 0))
while bfs:
	(cur, dis) = bfs.popleft()
	for x in l[cur]:
		if reach[x][(dis + 1) % 3] < 0:
			bfs.append((x, dis + 1))
			reach[x][(dis + 1) % 3] = dis + 1
ans = reach[t][0]
if ans > 2:
	ans //= 3
print(ans)


(n, m) = map(int, input().split())
s = [[] for i in range(n + 1)]
t = [[0, 0, 0] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	s[a].append(b)
(c, d) = map(int, input().split())
t[c][0] = 0
do = 0
p = [c]
while t[d][0] == 0 and len(p) != 0:
	do += 1
	q = []
	for i in p:
		for j in s[i]:
			if t[j][do % 3] == 0:
				t[j][do % 3] = do
				q.append(j)
	p = q[:]
print(t[d][0] // 3 if t[d][0] > 0 else -1)


import sys
input = sys.stdin.readline
from collections import deque
mod = 10 ** 9 + 7
(n, m) = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = [int(x) for x in input().split()]
	g[u - 1].append(v - 1)
(s, t) = [int(x) for x in input().split()]
d = [[-1, -1, -1] for _ in range(n)]

def bfs(u):
	queue = deque([[u, 0]])
	d[u][0] = 0
	while queue:
		(v, d_) = queue.popleft()
		for i in g[v]:
			if d[i][(d_ + 1) % 3] < 0:
				d[i][(d_ + 1) % 3] = d_ + 1
				queue.append([i, d_ + 1])
	return d
d = bfs(s - 1)
print(d[t - 1][0] // 3)


from heapq import heappop, heappush
(N, M) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
(S, T) = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for (u, v) in X:
	graph[u].append(v)
INF = 10 ** 9 + 7
d = [[INF] * 3 for _ in range(N + 1)]
d[S][0] = 0
pq = []
heappush(pq, (0, S))
while pq:
	(_, u) = heappop(pq)
	for v in graph[u]:
		for i in range(3):
			if d[v][(i + 1) % 3] > d[u][i] + 1:
				d[v][(i + 1) % 3] = d[u][i] + 1
				heappush(pq, (d[v][(i + 1) % 3], v))
if d[T][0] == INF:
	print(-1)
else:
	print(d[T][0] // 3)


from collections import deque
(N, M) = map(int, input().split())
edge = [[] for _ in range(3 * N)]
for i in range(M):
	(u, v) = map(int, input().split())
	for i in range(3):
		edge[i * N + u - 1].append((i + 1) % 3 * N + (v - 1))
(S, T) = map(int, input().split())
S -= 1
T -= 1
distance = [10 ** 9 for _ in range(3 * N)]
distance[S] = 0
queue = deque([S])
while queue:
	u = queue.popleft()
	for next in edge[u]:
		if distance[u] + 1 < distance[next]:
			distance[next] = distance[u] + 1
			queue.append(next)
if distance[T] < 10 ** 9:
	print(distance[T] // 3)
else:
	print(-1)


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)


(n, m) = map(int, input().split())
to = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	to[u - 1].append(v - 1)
(s, t) = 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)
			exit()
		nextq += to[v]
	if phase == 0:
		cnt += 1
	phase = (phase + 1) % 3
	q = nextq
print(-1)


(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)


(N, M) = map(int, input().split())
from collections import defaultdict, deque
graph = defaultdict(list)
for i in range(M):
	(u, v) = map(int, input().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) = map(int, input().split())
S -= 1
T -= 1
dist = [-1] * (3 * N)
dist[S] = 0
que = deque([S])
while len(que) != 0:
	q = que.popleft()
	cost = dist[q]
	for v in graph[q]:
		if dist[v] == -1:
			dist[v] = cost + 1
			que.append(v)
if dist[T] % 3 == 0:
	print(dist[T] // 3)
else:
	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 sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
S = [[] for i in range(N)]
for i in range(M):
	(u, v) = map(int, input().split())
	S[u - 1].append(v - 1)
(St, T) = map(int, input().split())
D = [[float('inf')] * 3 for i in range(N)]
D[St - 1][0] = 0
queue = [St - 1]
i = 0
while queue != []:
	i += 1
	hoge = []
	for q in queue:
		for s in S[q]:
			if D[s][i % 3] > i:
				D[s][i % 3] = i
				if not s in hoge:
					hoge.append(s)
	queue = hoge[:]
	if D[T - 1][0] != float('inf'):
		break
if D[T - 1][0] == float('inf'):
	print(-1)
else:
	print(D[T - 1][0] // 3)


import sys
input = sys.stdin.readline
inpl = lambda : list(map(int, input().split()))
(N, M) = inpl()
uv = [set() for _ in range(3 * N)]
vu = [set() for _ in range(3 * N)]
for _ in range(M):
	(u, v) = inpl()
	for k in range(3):
		uv[u - 1 + k * N].add(v - 1 + (k + 1) % 3 * N)
		vu[v - 1 + (k + 1) % 3 * N].add(u - 1 + k * N)
(S, T) = inpl()
S -= 1
T -= 1
cur = set({S})
for i in range(3 * N):
	if i % 3 == 0 and T in cur:
		print(i // 3)
		break
	elif len(cur) == 0:
		print(-1)
		break
	prev = cur
	cur = set()
	for u in prev:
		for fr in vu[u]:
			uv[fr].remove(u)
		cur |= uv[u]
else:
	print(-1)


from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
g = [[] for _ in range(N)]
gr = [[] for _ in range(N)]
for _ in range(M):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	gr[v - 1].append(u - 1)
(S, T) = map(int, input().split())
f = [[-1, -1, -1] for _ in range(N)]
f[S - 1][0] = 0
q = deque([[S - 1, 0]])
while q:
	(d, s) = q.popleft()
	s += 1
	for sd in g[d]:
		if f[sd][s % 3] == -1:
			f[sd][s % 3] = s // 3
			q.append([sd, s])
print(f[T - 1][0])


from collections import defaultdict as dd
from collections import deque
(N, M) = map(int, input().split())
e = dd(list)
inf = 10 ** 9
for _ in range(M):
	(u, v) = map(int, input().split())
	e[u].append(v + N)
	e[u + N].append(v + 2 * N)
	e[u + 2 * N].append(v)
(S, T) = map(int, input().split())
S += 2 * N
T += 2 * N
stopped = [inf] * (3 * (N + 1))
Q = deque()
Q.append(S)
stopped[S] = 0
while len(Q) != 0:
	p = Q.popleft()
	if stopped[p] >= stopped[T]:
		break
	for q in e[p]:
		if stopped[q] > stopped[p] + 1:
			Q.append(q)
			stopped[q] = stopped[p] + 1
if stopped[T] == inf:
	print(-1)
else:
	print(stopped[T] // 3)


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
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
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()])

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()


from collections import deque
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
G = [[] for i in range(3 * N)]
for i in range(M):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	G[3 * u + 0].append(3 * v + 1)
	G[3 * u + 1].append(3 * v + 2)
	G[3 * u + 2].append(3 * v + 0)
(S, T) = map(int, input().split())
(S, T) = (S - 1, T - 1)
INF = float('inf')
d = [INF] * (3 * N)
d[3 * S] = 0
que = deque([3 * S])
while que:
	u = que.popleft()
	for w in G[u]:
		if d[w] == INF:
			d[w] = d[u] + 1
			que.append(w)
ans = d[3 * T]
if ans == INF:
	print(-1)
else:
	print(ans // 3)


from collections import deque
(N, M) = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
(S, T) = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for (u, v) in X:
	graph[u].append(v)
INF = 10 ** 9 + 7
ctr = [[INF] * (N + 1) for _ in range(3)]
ctr[0][S] = 0
stack = deque()
stack.append((0, S))
while stack:
	(i, u) = stack.popleft()
	j = (i + 1) % 3
	for v in graph[u]:
		if ctr[j][v] > ctr[i][u] + 1:
			ctr[j][v] = ctr[i][u] + 1
			stack.append((j, v))
if ctr[0][T] < INF:
	print(ctr[0][T] // 3)
else:
	print(-1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
from collections import defaultdict
branch = defaultdict(set)
for i in range(m):
	(u, v) = map(int, input().split())
	branch[u - 1] |= {v - 1}
(s, t) = map(int, input().split())
s -= 1
t -= 1
dist = [[float('inf')] * 3 for i in range(n)]
check = {(s, 0)}
dist[s][0] = 0
while len(check) > 0:
	(now, nowd) = check.pop()
	for nex in branch[now]:
		if dist[nex][(nowd + 1) % 3] > dist[now][nowd] + 1:
			dist[nex][(nowd + 1) % 3] = dist[now][nowd] + 1
			check |= {(nex, (nowd + 1) % 3)}
if dist[t][0] > 10 ** 18:
	print(-1)
else:
	print(dist[t][0] // 3)


from collections import deque
(N, M) = map(int, input().split())
a = [[[] for j in range(N)] for i in range(3)]
for i in range(M):
	(u, v) = map(lambda x: int(x) - 1, input().split())
	a[0][u].append((1, v))
	a[1][u].append((2, v))
	a[2][u].append((0, v))
(S, T) = map(lambda x: int(x) - 1, input().split())
r = [[-3 for j in range(N)] for i in range(3)]
q = deque()
q.append((0, S))
r[0][S] = 0
while q:
	(ui, uj) = q.popleft()
	for (vi, vj) in a[ui][uj]:
		if r[vi][vj] == -3:
			r[vi][vj] = r[ui][uj] + 1
			q.append((vi, vj))
print(r[0][T] // 3)


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)


from collections import defaultdict, deque
(N, M) = map(int, input().split())
E = defaultdict(list)
for _ in range(M):
	(u, v) = map(int, input().split())
	E[u].append(v + N)
	E[u + N].append(v + 2 * N)
	E[u + 2 * N].append(v)
(S, T) = map(int, input().split())
R = [-1 for _ in range(3 * N)]
R[S - 1] = 0
q = deque()
q.append(S)
while q:
	n = q.popleft()
	if n == T:
		break
	for t in E[n]:
		if R[t - 1] < 0:
			R[t - 1] = R[n - 1] + 1
			q.append(t)
print(-1 if R[T - 1] < 0 else R[T - 1] // 3)


def i1():
	return int(input())

def i2():
	return [int(i) for i in input().split()]
e = [[] for i in range(3 * 10 ** 5 + 10)]
[n, m] = i2()
for i in range(m):
	[u, v] = i2()
	u -= 1
	v -= 1
	e[3 * u].append(3 * v + 1)
	e[3 * u + 1].append(3 * v + 2)
	e[3 * u + 2].append(3 * v)
[s, t] = i2()
s -= 1
t -= 1
from collections import deque
d = [-1 for i in range(3 * 10 ** 5 + 10)]

def bfs(v):
	d[v] = 0
	q = deque([v])
	while len(q):
		v = q.popleft()
		for i in e[v]:
			if d[i] < 0:
				d[i] = d[v] + 1
				q.append(i)
	if d[3 * t] > -1:
		return d[3 * t] // 3
	return d[3 * t]
print(bfs(3 * s))


from collections import deque
(N, M) = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	adj[a].append(b)
(S, T) = map(int, input().split())
S -= 1
T -= 1
INF = float('inf')
dist = [[INF] * 3 for _ in range(N)]
q = deque([(S, 0)])
dist[S][0] = 0
while q:
	(n, d) = q.popleft()
	for v in adj[n]:
		nd = (d + 1) % 3
		if dist[v][nd] != INF:
			continue
		dist[v][nd] = dist[n][d] + 1
		q.append((v, nd))
if dist[T][0] == INF:
	print(-1)
else:
	print(dist[T][0] // 3)


import copy
(n, m) = map(int, input().split())
graph = [[] for _ in range(n * 3)]
for i in range(m):
	(u, v) = map(int, input().split())
	for j in range(3):
		graph[n * j + u - 1].append((n * (j + 1) + v - 1) % (3 * n))
(s, t) = map(int, input().split())
wait = [s - 1]
cnt = 0
done = [0] * (3 * n)
while wait:
	cnt += 1
	now = copy.copy(wait)
	wait = []
	for i in now:
		for j in graph[i]:
			if not done[j]:
				done[j] = 1
				wait.append(j)
			if j == t - 1:
				print(cnt // 3)
				quit()
print(-1)


import sys
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
g = [[] for _ in range(3 * n)]
for i 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)
from collections import deque
q = deque()
visit = [-1] * (3 * n)
q.append(s)
visit[s] = 0
while q:
	u = q.popleft()
	for v in g[u]:
		if visit[v] == -1:
			visit[v] = visit[u] + 1
			q.append(v)
if visit[t] == -1:
	print(-1)
else:
	print(visit[t] // 3)


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()


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()


(N, M) = [int(c) for c in input().split()]
path = [[] for _ in range(N)]
for i in range(M):
	(u, v) = [int(c) for c in input().split()]
	path[u - 1].append(v - 1)
(S, T) = [int(c) - 1 for c in input().split()]
reach = [[-1 for _ in range(N)] for _ in range(3)]
reach[0][S] = 0
queue = {S}
time = 1
for _ in range(4 * N):
	queue_new = set()
	for q in queue:
		for v in path[q]:
			if reach[time % 3][v] == -1:
				reach[time % 3][v] = time
				queue_new.add(v)
	queue = queue_new
	time += 1
if reach[0][T] == -1:
	print(-1)
else:
	print(reach[0][T] // 3)


from collections import deque as dq
(n, m) = list(map(int, input().split()))
graph = [[] for i in range(n)]
for i in range(m):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	graph[a].append(b)
(s, t) = list(map(int, input().split()))
s -= 1
t -= 1
check = [[-1, -1, -1] for i in range(n)]
que = dq()
que.appendleft([s, 0])
check[s][0] = 0
while que:
	(v, l) = que.pop()
	for i in graph[v]:
		if check[i][(l + 1) % 3] == -1:
			que.appendleft([i, (l + 1) % 3])
			check[i][(l + 1) % 3] = check[v][l] + 1
if check[t][0] == -1:
	print(-1)
else:
	print(check[t][0] // 3)


(N, M) = map(int, input().split())
L1 = [[] for k in range(3 * (N + 1))]
for k in range(M):
	(u, v) = map(int, input().split())
	L1[3 * u].append(3 * v + 1)
	L1[3 * u + 1].append(3 * v + 2)
	L1[3 * u + 2].append(3 * v)
(S, T) = map(int, input().split())
S = 3 * S
T = 3 * T
t = 0
sumi = [None for k in range(3 * (N + 1))]
sumi[T] = -1
now = [S]
flg = 0
while len(now) != 0:
	t += 1
	pre = []
	for n in now:
		pre.extend(L1[n])
	now = []
	for p in pre:
		if sumi[p] == None:
			sumi[p] = t
			now.append(p)
		elif sumi[p] == -1:
			flg = 1
	if flg == 1:
		print(t // 3)
		flg = 2
		break
if flg == 0:
	print(-1)


from collections import deque
(N, M) = map(int, input().split())
dis = [[-1, -1, -1] for _ in range(N + 1)]
Tree = [[] for _ in range(N + 1)]
for i in range(M):
	(ui, vi) = map(int, input().split())
	Tree[ui].append(vi)
(S, T) = map(int, input().split())
d = deque([(S, 0)])
dis[S][0] = 0
while d:
	(x, z) = d.popleft()
	for y in Tree[x]:
		if dis[y][(z + 1) % 3] == -1:
			dis[y][(z + 1) % 3] = dis[x][z] + 1
			d.append((y, (z + 1) % 3))
if dis[T][0] == -1:
	print(-1)
else:
	print(dis[T][0] // 3)


import heapq
(N, M) = map(int, input().split())
G = [set() for i in range(N)]
for i in range(M):
	(u, v) = map(int, input().split())
	G[u - 1].add(v - 1)
(S, T) = map(int, input().split())
S -= 1
T -= 1
dist = [[10 ** 10 for i in range(3)] for i in range(N)]
dist[S][0] = 0
q = []
heapq.heappush(q, (dist[S][0], S, 0))
while len(q) > 0:
	(d, r, j) = heapq.heappop(q)
	if dist[r][j] < d:
		continue
	for p in G[r]:
		if dist[p][(j + 1) % 3] > dist[r][j] + 1:
			dist[p][(j + 1) % 3] = dist[r][j] + 1
			heapq.heappush(q, (dist[p][(j + 1) % 3], p, (j + 1) % 3))
if dist[T][0] == 10 ** 10:
	print(-1)
else:
	print(dist[T][0] // 3)


(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
gg = [[] for _ in range(3 * n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	gg[a].append(n + b)
	gg[n + a].append(2 * n + b)
	gg[2 * n + a].append(b)
(s, t) = map(int, input().split())
(s, t) = (s - 1, t - 1)
from collections import deque
todo = deque([s])
seen = [-1] * (3 * n)
seen[s] = 0
while todo:
	v = todo.popleft()
	for l in gg[v]:
		if seen[l] == -1:
			todo.append(l)
			seen[l] = seen[v] + 1
			if l == t:
				print(seen[l] // 3)
				exit()
if seen[t] > 0:
	print(seen[t] // 3)
else:
	print(-1)


(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)


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
(N, M) = map(int, input().split())
edges = [[] for _ in range(N + 1)]
for _ in range(M):
	(u, v) = map(int, input().split())
	edges[u].append(v)
visited = set()
(S, T) = map(int, input().split())
que = deque([(S, 0)])
while que:
	(cur, step) = que.popleft()
	rest = step % 3
	if cur == T and rest == 0:
		print(step // 3)
		exit()
	if (cur, rest) in visited:
		continue
	else:
		visited.add((cur, rest))
		for nx in edges[cur]:
			que.append((nx, step + 1))
print(-1)


import sys
from collections import deque
input = sys.stdin.readline
(n, m) = map(int, input().split())
G = [[] for _ in range(3 * (n + 1))]
for _ in range(m):
	(u, v) = 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) = 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)


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) = map(int, input().split())
m = [[] for _ in range(N + 1)]
for _ in range(M):
	(u, v) = map(int, input().split())
	m[u].append(v)
(S, T) = map(int, input().split())
l = [[-1, -1, -1] for _ in range(N + 1)]
q = deque()
q.append((S, 0, 0))
while len(q):
	(i, n, mod) = q.popleft()
	for j in m[i]:
		if j == T and mod == 2:
			print((n + 1) // 3)
			exit()
		if l[j][(mod + 1) % 3] != -1:
			continue
		l[j][(mod + 1) % 3] = n + 1
		q.append((j, n + 1, (mod + 1) % 3))
print(-1)


(N, M) = map(int, input().split())
G = [[] for i in range(N + 1)]
for i in range(M):
	(u, v) = map(int, input().split())
	G[u].append(v)
(s, t) = map(int, input().split())
d = [-1] * (N + 1)
S = set()
S.add(s)
d[s] = 0
x = 1
while len(S) > 0:
	Q1 = set()
	for u in S:
		for v in G[u]:
			Q1.add(v)
	Q2 = set()
	for u in Q1:
		for v in G[u]:
			Q2.add(v)
	Q3 = set()
	for u in Q2:
		for v in G[u]:
			if d[v] < 0:
				d[v] = x
				Q3.add(v)
	x += 1
	S = Q3
print(d[t])


from collections import deque

def inpl():
	return list(map(int, input().split()))
(N, M) = inpl()
UV = [inpl() for i in range(M)]
(S, T) = inpl()
S -= 1
T -= 1
ans = [[-1, -1, -1] for i in range(N)]
uv = [[] for i in range(N)]
for (u, v) in UV:
	u -= 1
	v -= 1
	uv[u].append(v)
ans[S][0] = 0
que = deque()
que.append((S, 0))
t = 0
while que:
	(v, t) = que.popleft()
	nt = (t + 1) % 3
	for nv in uv[v]:
		if ans[nv][nt] != -1:
			continue
		elif nv == T and nt == 0:
			ans[nv][nt] = (ans[v][t] + 1) // 3
			break
		ans[nv][nt] = ans[v][t] + 1
		que.append((nv, nt))
print(ans[T][0])


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)


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()


(N, M) = map(int, input().split())
nodes = [[] for i in range(N)]
for i in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	nodes[u].append(v)
(s, t) = map(int, input().split())
s -= 1
t -= 1
num = s
step = 0
q = [[num, step]]
check = [[False for i in range(N)] for j in range(3)]
ok = False
while len(q) > 0:
	(num, step) = q.pop(0)
	tmp = step % 3
	if tmp == 0 and num == t:
		print(step // 3)
		ok = True
		break
	for next in nodes[num]:
		if not check[tmp][next]:
			check[tmp][next] = True
			q.append([next, step + 1])
if not ok:
	print(-1)


(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)


from collections import deque
(n, m) = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	edges[u].append(v)
(s, t) = map(int, input().split())
s -= 1
t -= 1
from_s = [[-1] * 3 for _ in range(n)]
d_s = deque()
d_s.append((s, 0))
from_s[s][0] = 0
while d_s:
	(p, count) = d_s.popleft()
	next_count = (count + 1) % 3
	for c in edges[p]:
		if from_s[c][next_count] != -1:
			continue
		from_s[c][next_count] = from_s[p][count] + 1
		d_s.append((c, next_count))
if from_s[t] == -1:
	print(-1)
else:
	print(from_s[t][0] // 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
		elif 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 queue
(N, M) = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(M)]
(S, T) = list(map(int, input().split()))
V = [[0, 0, 0] for _ in range(N + 1)]
R = {}
for (u, v) in uv:
	if u not in R:
		R[u] = [v]
	else:
		R[u].append(v)
q = queue.Queue()
put = q.put
get = q.get
put([S, 0, 2])
ans = -1
while not q.empty():
	t = get()
	if t[0] == T and t[2] == 2:
		ans = t[1]
		break
	k = (t[2] + 1) % 3
	m = t[1]
	if t[2] == 2:
		m += 1
	if t[0] not in R:
		continue
	for i in R[t[0]]:
		if V[i][k] == 0:
			V[i][k] = 1
			put([i, m, k])
print(ans)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for i in range(M):
	(u, v) = map(int, input().split())
	graph[u].append(v)
(S, T) = map(int, input().split())
visited = []
for i in range(N + 1):
	visited.append([False] * 3)
queue = [S]
t = 0
while queue:
	new_queue = set()
	for u in queue:
		if u == T and t % 3 == 0:
			print(t // 3)
			sys.exit(0)
		visited[u][t % 3] = True
		for v in graph[u]:
			if not visited[v][(t + 1) % 3]:
				new_queue.add(v)
	queue = list(new_queue)
	t += 1
print(-1)


import sys
input = sys.stdin.readline
from collections import deque
(n, m) = map(int, input().split())
Edges = [[] for _ in range(3 * n)]
for _ in range(m):
	(u, v) = map(lambda x: int(x) - 1, input().split())
	Edges[u].append(v + n)
	Edges[u + n].append(v + 2 * n)
	Edges[u + 2 * n].append(v)
(s, t) = map(lambda x: int(x) - 1, input().split())
q = deque()
q.append(s)
Dist = [-1] * (3 * n)
Dist[s] = 0
while q:
	fr = q.popleft()
	for to in Edges[fr]:
		if Dist[to] == -1:
			Dist[to] = Dist[fr] + 1
			q.append(to)
print(Dist[t] // 3)


import sys
input = sys.stdin.readline
(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)


(N, M) = [int(i) for i in input().split()]
E = [[] for _ in range(3 * N)]
for _ in range(M):
	(u, v) = [int(i) - 1 for i in input().split()]
	E[3 * u].append(3 * v + 1)
	E[3 * u + 1].append(3 * v + 2)
	E[3 * u + 2].append(3 * v)
(S, T) = [3 * (int(i) - 1) for i in input().split()]
from collections import deque
Q = deque()
Q.append((S, 0))
visited = [False] * (3 * N)
visited[S] = True
ans = -1
while Q:
	(a, d) = Q.popleft()
	if a == T:
		ans = d
		break
	for b in E[a]:
		if not visited[b]:
			Q.append((b, d + 1))
			visited[b] = True
if ans % 3 == 0:
	print(ans // 3)
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, v) = (3 * (u - 1), 3 * (v - 1))
	graph[u].append(v + 1)
	graph[u + 1].append(v + 2)
	graph[u + 2].append(v)
(s, t) = map(int, input().split())
(s, t) = (3 * (s - 1), 3 * (t - 1))
dist = [10 ** 9] * 3 * N
dist[s] = 0
d = deque([s])
while d:
	node = d.popleft()
	children = graph[node]
	for child in children:
		if dist[child] > dist[node] + 1:
			d.append(child)
			dist[child] = dist[node] + 1
if dist[t] < 10 ** 9:
	print(dist[t] // 3)
else:
	print(-1)


from heapq import heappop, heappush
(N, M) = list(map(int, input().split()))
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)
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 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)


(N, M) = map(int, input().split())
to = [[] for _ in range(N)]
dist = [[0 for _ in range(3)] for _ in range(100005)]
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] = float('inf')
q = [[sv, 0]]
dist[sv][0] = 0
while len(q) != 0:
	v = q[0][0]
	l = q[0][1]
	q.pop(0)
	for u in to[v]:
		nl = (l + 1) % 3
		if dist[u][nl] != float('inf'):
			continue
		dist[u][nl] = dist[v][l] + 1
		q.append([u, nl])
ans = dist[tv][0]
if ans == float('inf'):
	ans = -1
else:
	ans //= 3
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))


def dist_bfs(N, E, start):
	d = [-1] * N
	d[start] = 0
	q = [start]
	while q:
		qq = []
		for i in q:
			di = d[i]
			for j in E[i]:
				if d[j] != -1:
					continue
				d[j] = di + 1
				q.append(j)
		q = qq
	return d
(N, M) = map(int, input().split())
UV = [list(map(int, input().split())) for _ in [0] * M]
(S, T) = map(int, input().split())
S -= 1
T -= 1
E = [[] for _ in [0] * 3 * N]
for (u, v) in UV:
	u -= 1
	v -= 1
	for i in range(3):
		v = (v + N) % (3 * N)
		E[u + i * N].append(v)
print(dist_bfs(3 * N, E, S)[T] // 3)


from collections import deque
(N, M) = map(int, input().split())
node = [[10 ** 9] * 3 for i in range(N)]
KENPA = 3
side = [[] for i in range(N)]
for i in range(M):
	(u, v) = map(int, input().split())
	side[u - 1].append(v - 1)
(S, T) = map(int, input().split())
node[S - 1][2] = 0
queue = deque([[S - 1, 2]])
while queue:
	(x, y) = queue.popleft()
	y2 = (y + 1) % KENPA
	for i in side[x]:
		if node[i][y2] > node[x][y] + 1:
			node[i][y2] = node[x][y] + 1
			queue.append([i, y2])
if node[T - 1][2] == 10 ** 9:
	print(-1)
else:
	print(node[T - 1][2] // 3)


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, *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
		elif 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)


from collections import deque
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	g[u - 1].append(v - 1)
(S, T) = map(int, input().split())
S -= 1
T -= 1
INF = 10 ** 9
U = [[INF] * n for i in range(3)]
U[0][S] = 0
que = deque([(0, S)])
while que:
	(t, v) = que.popleft()
	u = (t + 1) % 3
	if t == 2:
		U[t][v] += 1
	for w in g[v]:
		if U[u][w] != INF:
			continue
		que.append((u, w))
		U[u][w] = U[t][v]
print(U[0][T] if U[0][T] < INF else -1)


from collections import deque
(N, M) = map(int, input().split())
vec = [[] for _ in range(N)]
for _ in range(M):
	(u, v) = map(int, input().split())
	vec[u - 1].append(v - 1)
(S, T) = map(int, input().split())
(S, T) = (S - 1, T - 1)
visited = [[False] * N for _ in range(3)]
visited[0][S] = True
queue = deque([(S, 0)])
while queue:
	(q, cost) = queue.popleft()
	p = (cost + 1) % 3
	for i in vec[q]:
		if p == 0 and i == T:
			print((cost + 1) // 3)
			exit()
		if not visited[p][i]:
			visited[p][i] = True
			queue.append((i, cost + 1))
print(-1)


from collections import deque
(n, m) = map(int, input().split())
g = [[] for i in range(3 * n)]
for i in range(m):
	(a, b) = map(int, input().split())
	g[3 * (a - 1)].append(3 * (b - 1) + 1)
	g[3 * (a - 1) + 1].append(3 * (b - 1) + 2)
	g[3 * (a - 1) + 2].append(3 * (b - 1))
(s, t) = map(int, input().split())
s -= 1
t -= 1
s *= 3
t *= 3
q = deque([[s, 0]])
v = [0] * (3 * n)
while q:
	p = q.popleft()
	v[p[0]] = 1
	for j3 in g[p[0]]:
		if j3 == t:
			print((p[1] + 1) // 3)
			exit()
		if v[j3] == 0:
			v[j3] = 1
			q.append([j3, p[1] + 1])
print(-1)


import sys

def MI():
	return map(int, sys.stdin.readline().rstrip().split())
(N, M) = MI()
G = {}
for i in range(1, N + 1):
	G[i, 0] = []
	G[i, 1] = []
	G[i, 2] = []
for _ in range(M):
	(u, v) = MI()
	G[u, 0].append((v, 1))
	G[u, 1].append((v, 2))
	G[u, 2].append((v, 0))
(S, T) = MI()
flag = [[-1] * 3 for i in range(N + 1)]
from collections import deque
q = deque([(S, 0, 0)])
while q:
	(n, m, r) = q.pop()
	for (d, e) in G[n, m]:
		if flag[d][e] != -1:
			continue
		else:
			flag[d][e] = r + 1
			q.appendleft((d, e, r + 1))
print(flag[T][0] // 3)


from collections import deque
(N, M) = list(map(int, input().split()))
graph = [deque() for i in range(N * 3)]
visited = [False] * (N * 3)
for i in range(M):
	(u, v) = list(map(int, input().split()))
	(u, v) = ((u - 1) * 3, (v - 1) * 3)
	graph[u].append(v + 1)
	graph[u + 1].append(v + 2)
	graph[u + 2].append(v)
(S, T) = list(map(int, input().split()))
(S, T) = ((S - 1) * 3, (T - 1) * 3)
q = deque([(S, 0)])
visited[S] = True
ans = -1
while q:
	(u, cost) = q.popleft()
	if u == T:
		ans = cost // 3
		break
	else:
		for v in graph[u]:
			if not visited[v]:
				visited[v] = True
				q.append((v, cost + 1))
print(ans)


(n, m) = map(int, input().split())
pst = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	pst[a].append(b)
(s, t) = map(int, input().split())
s -= 1
t -= 1
cnt = [[0, 0, 0] for _ in range(n)]
cnt[s][0] = 1
now = [s]
time = 0
while now:
	time += 1
	last = now
	now = []
	for x in last:
		for y in pst[x]:
			if cnt[y][time % 3] == 0:
				cnt[y][time % 3] = 1
				now.append(y)
	if cnt[t][0] == 1:
		print(time // 3)
		break
else:
	print(-1)


from collections import defaultdict, deque
(n, m) = list(map(int, input().split()))
graph = defaultdict(set)
for i in range(m):
	(u, v) = list(map(int, input().split()))
	graph[u].add(v)
(s, t) = list(map(int, input().split()))
dist = [[-1 for i in range(3)] for i in range(10 ** 5 + 10)]

def bfs():
	que = deque([(s, 0, 0)])
	while len(que) > 0:
		p = que.popleft()
		if dist[p[0]][p[2]] != -1:
			continue
		dist[p[0]][p[2]] = p[1]
		for nx in graph[p[0]]:
			que.append((nx, p[1] + 1, (p[2] + 1) % 3))
bfs()
print(dist[t][0] // 3)


from collections import deque
import sys
inputs = sys.stdin.readline
(N, M) = map(int, input().split())
UV = [tuple(map(lambda x: int(x) - 1, inputs().split())) for i in range(M)]
(S, T) = map(lambda x: int(x) - 1, input().split())
es = [[] for i in range(3 * N)]
for (u, v) in UV:
	es[u].append(v + N)
	es[u + N].append(v + 2 * N)
	es[u + 2 * N].append(v)
q = deque([S])
INF = float('inf')
dist = [INF] * (3 * N)
dist[S] = 0
while q:
	v = q.popleft()
	for to in es[v]:
		if dist[to] != INF:
			continue
		dist[to] = dist[v] + 1
		if to == T:
			print(dist[to] // 3)
			exit()
		q.append(to)
print(-1)


from collections import deque
(n, m) = map(int, input().split())
path = [set() for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	path[u].add(v)
(s, t) = map(int, input().split())
que = deque([(s - 1, 0)])
d = [[float('inf')] * n for _ in range(3)]
d[0][s - 1] = 0
while que:
	(p, i) = que.popleft()
	j = (i + 1) % 3
	for to in path[p]:
		if d[j][to] == float('inf'):
			d[j][to] = d[i][p] + 1
			que.append((to, j))
if d[0][t - 1] == float('inf'):
	d[0][t - 1] = -3
print(d[0][t - 1] // 3)


def main():
	(N, M) = map(int, input().split())
	INF = 2 * 31 - 1
	to = [[] for _ in range(N)]
	for _ in range(M):
		(u, v) = map(int, input().split())
		to[u - 1].append(v - 1)
	dist = [[INF, INF, INF] for _ in range(N)]
	(S, T) = map(int, input().split())
	queue = []
	for pos in to[S - 1]:
		queue.append([pos, 1])
		dist[pos][1] = 1
	while queue:
		(pos, l) = queue.pop(0)
		next_positions = to[pos]
		for next_pos in next_positions:
			nl = (l + 1) % 3
			if dist[next_pos][nl] != INF:
				continue
			dist[next_pos][nl] = dist[pos][l] + 1
			queue.append([next_pos, nl])
	ans = dist[T - 1][0]
	if ans == INF:
		print(-1)
	else:
		print(ans // 3)
main()


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)


(N, M) = map(int, input().split())
E = {}
for v in range(1, N * 3 + 1):
	E[v] = []
for _ in range(M):
	(u, v) = map(int, input().split())
	E[u].append(v + N)
	E[u + N].append(v + 2 * N)
	E[u + 2 * N].append(v)
(S, T) = map(int, input().split())
dist = [-1 for _ in range(3 * N)]
dist[S - 1] = 0
q = []
q.append(S)
while q:
	n = q.pop(0)
	if n == T:
		break
	for t in E[n]:
		if dist[t - 1] < 0:
			dist[t - 1] = dist[n - 1] + 1
			q.append(t)
print(-1 if dist[T - 1] < 0 else dist[T - 1] // 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)
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(ans)


(N, M) = map(int, input().split())
G = [[] for _ in range(3 * N)]
L = [-3 for _ in range(3 * N)]
for _ in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	G[3 * u + 0].append(3 * v + 1)
	G[3 * u + 1].append(3 * v + 2)
	G[3 * u + 2].append(3 * v + 0)
(s, t) = map(int, input().split())
S = 3 * (s - 1)
T = 3 * (t - 1)
L[S] = 0
Frontier = [S]
while Frontier:
	v = Frontier.pop(0)
	for i in G[v]:
		if L[i] < 0:
			Frontier.append(i)
			L[i] = L[v] + 1
print(L[T] // 3)


from heapq import heappop, heappush
(N, M) = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	graph[a].append(b)
(S, T) = map(lambda x: int(x) - 1, input().split())
ans = -1
visited = set()
q = [(0, S)]
ans = -1
while q:
	(c, v) = heappop(q)
	key = (c % 3, v)
	if key in visited:
		continue
	visited.add(key)
	if v == T and c % 3 == 0:
		ans = c // 3
		break
	c += 1
	d = c % 3
	for u in graph[v]:
		new_key = (d, u)
		if new_key in visited:
			continue
		heappush(q, (c, u))
print(ans)


(N, M) = map(int, input().split())
UV = [list(map(int, input().split())) for _ in range(M)]
(S, T) = map(int, input().split())
if 0 == M:
	print(-1)
	exit()
graph = [set() for _ in range(N)]
for (u, v) in UV:
	graph[u - 1] |= {v - 1}
INF = 10 ** 12
depths = [[INF, INF, INF] for _ in range(N)]

def bfs(start, end):
	depth = 0
	nodes = {start}
	while nodes:
		if 0 == depth % 3 and end in nodes:
			return depth // 3
		next_nodes = set()
		for node in nodes:
			if depths[node][depth % 3] <= depth:
				continue
			depths[node][depth % 3] = depth
			next_nodes |= graph[node]
		nodes = next_nodes
		depth += 1
	return -1
print(bfs(S - 1, T - 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)


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 queue import Queue
import sys
(N, M) = map(int, input().split())
edges = [[] for _ in range(3 * N)]
flag = [0] * (3 * N)
for _ in range(M):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	edges[u % (3 * N)].append((v + N) % (3 * N))
	edges[(u + N) % (3 * N)].append((v + 2 * N) % (3 * N))
	edges[(u + 2 * N) % (3 * N)].append(v % (3 * N))
(S, T) = map(int, input().split())
q = Queue()
q.put([0, S - 1])
while not q.empty():
	p = q.get()
	if p[1] == T - 1:
		print(p[0] // 3)
		sys.exit()
	for i in edges[p[1]]:
		if flag[i] == 0:
			flag[i] = 1
			q.put([p[0] + 1, i])
print(-1)


from collections import deque
(N, M) = map(int, input().split())
E = [list() for _ in range(N + 1)]
for _ in range(M):
	(u, v) = map(int, input().split())
	E[u].append(v)
(S, T) = map(int, input().split())
Visited = [[False] * (N + 1) for _ in range(3)]
Visited[0][S] = True
queue = deque()
queue.append((S, 0))
while queue:
	(cur, path) = queue.popleft()
	for neighbor in E[cur]:
		if Visited[(path + 1) % 3][neighbor] == False:
			queue.append((neighbor, path + 1))
			Visited[(path + 1) % 3][neighbor] = path + 1
ans = Visited[0][T]
if ans == False:
	print(-1)
elif ans > 2:
	ans //= 3
	print(ans)
else:
	print(ans)


from collections import deque
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
	(a, b) = map(int, input().split())
	edge[a].append(b)
(S, T) = map(int, input().split())
path = [[-1] * 3 for _ in range(N + 1)]
path[S][0] = 0
node = deque([(S, 0)])
while node:
	(s, d) = node.popleft()
	dist = path[s][d]
	d = (d + 1) % 3
	for t in edge[s]:
		if path[t][d] != -1:
			continue
		path[t][d] = dist + 1
		node.append((t, d))
ans = path[T][0] // 3
print(ans)


from collections import *
(n, m, *w, s, t) = map(int, open(0).read().split())
e = [[] for _ in range(n + 1)]
for (u, v) in zip(w[::2], w[1::2]):
	e[u].append(v)
f = [[-3] * 3 for _ in range(n + 1)]
f[s][0] = 0
q = deque([(s, 0)])
while q:
	(v, m) = q.popleft()
	for w in e[v]:
		if f[w][-~m % 3] < 0:
			f[w][-~m % 3] = f[v][m] + 1
			q += [(w, -~m % 3)]
print(f[t][0] // 3)


(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)


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)


from collections import deque
(N, M) = map(int, input().split())
K = [[] for _ in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	K[a - 1].append(b - 1)
(S, T) = map(int, input().split())
used = [[0] * 3 for _ in range(N)]
q = deque([[S - 1, 0, 0]])
used[S - 1][0] = 1
ans = [[-3] * 3 for _ in range(N)]
while len(q) > 0:
	(u, v, c) = q.popleft()
	v_n = (v + 1) % 3
	for j in K[u]:
		if used[j][v_n] == 0:
			used[j][v_n] = 1
			ans[j][v_n] = c + 1
			q.append([j, v_n, c + 1])
print(ans[T - 1][0] // 3)


from collections import deque
(N, M) = map(int, input().split())
graph = [[] for _ in range(3 * N)]
for _ in range(M):
	(u, v) = map(lambda x: int(x) - 1, input().split())
	graph[3 * u] += [3 * v + 1]
	graph[3 * u + 1] += [3 * v + 2]
	graph[3 * u + 2] += [3 * v]
(S, T) = map(lambda x: int(x) - 1, input().split())

def bfs(s):
	q = deque([s])
	dist = [float('inf')] * (3 * N)
	dist[s] = 0
	while q:
		u = q.popleft()
		for v in graph[u]:
			if dist[v] == float('inf'):
				q += [v]
				dist[v] = dist[u] + 1
	return dist
d = bfs(3 * S)
if d[3 * T] == float('inf'):
	print(-1)
else:
	print(d[3 * T] // 3)


from collections import defaultdict, deque
(N, M) = map(int, input().split())
e = defaultdict(list)
for i in range(M):
	(u, v) = map(int, input().split())
	e[u].append(v)
(S, T) = map(int, input().split())
q = deque([[S, 0]])
dist = [[-3] * 3 for _ in range(N + 1)]
dist[S][0] = 0
while q:
	(u, c) = q.popleft()
	for v in e[u]:
		step = (c + 1) % 3
		if dist[v][step] < 0:
			dist[v][step] = c + 1
			q.append([v, c + 1])
print(dist[T][0] // 3)


(N, M) = map(int, input().split())
adj = {}
for _ in range(M):
	(u, v) = [int(i) - 1 for i in input().split()]
	if u in adj:
		adj[u].append(v)
	else:
		adj[u] = [v]
(S, T) = [int(i) - 1 for i in input().split()]
INF = -1
dist = [[INF] * 3 for _ in range(N)]
q = [(S, 0)]
dist[S][0] = 0
while len(q) > 0:
	(u, nl) = q.pop(0)
	if u not in adj:
		continue
	for v in adj[u]:
		ml = (nl + 1) % 3
		if dist[v][ml] != INF:
			continue
		dist[v][ml] = dist[u][nl] + 1
		q.append((v, ml))
ans = dist[T][0]
if ans == INF:
	print(-1)
else:
	print(ans // 3)


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
(N, M) = map(int, input().split())
link = [[] for _ in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	link[a - 1].append(b - 1)
(s, t) = map(lambda x: int(x) - 1, input().split())
INF = 10 ** 10
dist = [[INF] * 3 for _ in range(N)]
dist[s][0] = 0
que = deque([[s, 0]])
while len(que):
	(pv, pl) = que.popleft()
	for nv in link[pv]:
		nl = (pl + 1) % 3
		if dist[nv][nl] != INF:
			continue
		dist[nv][nl] = dist[pv][pl] + 1
		que.append([nv, nl])
ans = dist[t][0]
if ans == INF:
	ans = -1
else:
	ans //= 3
print(ans)


from collections import deque
(N, M) = map(int, input().split())
X = [[] for i in range(N * 3)]
for i in range(M):
	(x, y) = map(int, input().split())
	X[x - 1].append(y + N - 1)
	X[x + N - 1].append(y + N * 2 - 1)
	X[x + N * 2 - 1].append(y - 1)
(S, T) = map(int, input().split())
S -= 1
T -= 1
Q = deque([S])
D = [999999] * N * 3
D[S] = 0
while Q:
	x = Q.popleft()
	for c in X[x]:
		if D[c] == 999999:
			D[c] = D[x] + 1
			Q.append(c)
print(-1 if D[T] == 999999 else D[T] // 3)


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
			elif 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)


from collections import deque
(n, m) = list(map(int, input().split()))
g = [[] for _ in range(10 * (n + 1) + 3)]
for _ in range(m):
	(u, v) = list(map(int, input().split()))
	g[10 * u].append(10 * v + 1)
	g[10 * u + 1].append(10 * v + 2)
	g[10 * u + 2].append(10 * v)
(s, t) = list(map(int, input().split()))
inf = 10 ** 10
q = deque([10 * s])
d = [inf] * (10 * (n + 1) + 3)
d[10 * s] = 0
while len(q) > 0:
	u = deque.pop(q)
	res = u % 10
	for i in range(3):
		nres = (res + i) % 3
		for v in g[u]:
			if d[v] < inf:
				continue
			d[v] = min(d[v], d[u] + 1)
			deque.appendleft(q, v)
if d[10 * t] == inf:
	print(-1)
else:
	print(d[10 * t] // 3)


import sys
import itertools
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
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)


(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 itertools import count
(N, M) = map(int, input().split())
adj = [list() for _ in range(N)]
for _ in range(M):
	(u, v) = map(int, input().split())
	adj[u - 1].append(v - 1)
(S, T) = map(int, input().split())
(S, T) = (S - 1, T - 1)
visited = [False] * (N * 3)
visited[S] = True
q = [S]
for step in count(1):
	offset = N * (step % 3)
	nq = []
	for u in q:
		for v in adj[u]:
			if not visited[v + offset]:
				nq.append(v)
				visited[v + offset] = True
	q = nq
	if visited[T] or not q:
		break
if visited[T]:
	print(step // 3)
else:
	print(-1)


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
		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))


from collections import deque
(n, m) = map(int, input().split())
if m == 0:
	print(-1)
	exit()
edge = [[] for i in range(3 * n)]
for i in range(m):
	(u, v) = map(int, input().split())
	edge[3 * (u - 1)].append(3 * (v - 1) + 1)
	edge[3 * (u - 1) + 1].append(3 * (v - 1) + 2)
	edge[3 * (u - 1) + 2].append(3 * (v - 1))
(s, t) = map(int, input().split())
s -= 1
t -= 1
visited = [0 for i in range(3 * m)]

def bfs(edge, visited, s, t):
	q = deque([3 * s])
	visited[3 * s] = 1
	cnt = 0
	while q:
		x = q.popleft()
		if x % 3 == 0 and x // 3 == t:
			return visited[x] // 3
		for i in edge[x]:
			newx = i
			if visited[newx] == 0:
				visited[newx] = visited[x] + 1
				q.append(newx)
	return -1
print(bfs(edge, visited, s, t))


(n, m) = map(int, input().split())
u = {i: [] for i in range(1, n + 1)}
for i in range(m):
	(ui, vi) = map(int, input().split())
	u[ui].append(vi)
(s, t) = map(int, input().split())
current = [s]
dist = {s: 0}
for i in range(n):
	for j in range(3):
		next = set()
		for uj in current:
			for vj in u[uj]:
				next.add(vj)
		current = next
	current = []
	for vj in next:
		if vj not in dist:
			dist[vj] = i + 1
			current.append(vj)
	if len(current) == 0:
		break
print(-1 if t not in dist else dist[t])


import heapq
(n, m) = [int(i) for i in input().split()]
U = [[int(i) for i in input().split()] for j in range(m)]
(s, t) = [int(i) for i in input().split()]
E = [[] for i in range(n + 1)]
for (u, v) in U:
	E[u].append(v)
visited = [[False] * 3 for i in range(n + 1)]
V = []
heapq.heappush(V, (0, s))
while V:
	(c, v) = heapq.heappop(V)
	if v == t and c % 3 == 0:
		print(c // 3)
		exit()
	if visited[v][c % 3]:
		continue
	visited[v][c % 3] = True
	for to in E[v]:
		heapq.heappush(V, (c + 1, to))
print(-1)


from collections import defaultdict, deque
(N, M) = map(int, input().split())
dic = defaultdict(list)
for i in range(M):
	(u, v) = map(int, input().split())
	dic[u - 1] += [v - 1]
(S, T) = map(int, input().split())
S -= 1
T -= 1
dist = [[float('inf')] * 3 for i in range(N)]
dist[S][0] = 0
q = deque([(S, 0)])
flag = False
cnt = 0
while q:
	cnt += 1
	(e, m) = q.popleft()
	n = (m + 1) % 3
	for p in dic[e]:
		if p == T:
			flag = True
		if dist[p][n] > dist[e][m] + 1:
			dist[p][n] = dist[e][m] + 1
			q += [(p, n)]
if flag:
	ans = dist[T][0] if dist[T][0] != float('inf') else -1
	print(ans // 3)
else:
	print(-1)


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())
	G[3 * (u - 1)].append(3 * (v - 1) + 1)
	G[3 * (u - 1) + 1].append(3 * (v - 1) + 2)
	G[3 * (u - 1) + 2].append(3 * (v - 1))
(S, T) = map(int, input().split())
dist = [-1] * (3 * N)
dist[3 * (S - 1)] = 0
q = deque([3 * (S - 1)])
while q:
	v = q.popleft()
	d = dist[v]
	Vs = G[v]
	for u in Vs:
		if dist[u] == -1:
			q.append(u)
			dist[u] = d + 1
ans = dist[3 * (T - 1)]
print(-1 if ans == -1 else ans // 3)


(n, m) = map(int, input().split())
edge = [[] for i in range(n + 1)]
for i in range(m):
	(a, b) = map(int, input().split())
	edge[a].append(b)
c = [[0] * (n + 1) for i in range(3)]
(s, t) = map(int, input().split())
c[2][s] = 1
q = [s]

def ken(a):
	tl = []
	for i in q:
		for j in edge[i]:
			if not c[a][j]:
				tl.append(j)
				c[a][j] = 1
	return tl
for i in range(n):
	q = ken(0)
	q = ken(1)
	q = ken(2)
	if c[2][t] == 1:
		print(i + 1)
		break
else:
	print(-1)


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())


(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(-1)