Problem:
 Score : 500 points    Problem Statement 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 1 4 4
1 2
2 3
3 4
4 1
1 3      Sample Output 1 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.       Sample Input 2 3 3
1 2
2 3
3 1
1 2      Sample Output 2 -1  Any number of ken-ken-pa will bring Ken back to Vertex 1 , so he cannot reach Vertex 2 , though he can pass through it in the middle of a ken-ken-pa.       Sample Input 3 2 0
1 2      Sample Output 3 -1  Vertex S and Vertex T may be disconnected.       Sample Input 4 6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6      Sample Output 4 2

Solution (Python):
from queue import Queue
import heapq
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(x): print(x, file=sys.stderr)



class Graph():
    """
    Graph のテンプレート
    Parameters
    --------
        n (int): グラフのサイズ。
    Options
    --------
        Weighted = False: 重み付きかどうか
        Directed = False: 有向かどうか
        Matrix = False:　グラフの表現を隣接リストにするか隣接行列にするか。デフォルトは隣接リスト。
    Methods
    -------
        add_edge(start,end,(weight))
            start から end に重さ weight の辺を張る。重みなしグラフの場合は weight を省略する。
        dijkstra(start): O((E+V)logV)
            start から各頂点への最短距離を返す。負の辺があると無理。
        bellman_ford(start): O(EV)
            start から各頂点への最短距離を返す。負の辺があってもいけるが遅い。
    """

    def __init__(self, n, Weighted=False, Directed=False, Matrix=False):
        self.sz = n
        self.is_Weighted = Weighted
        self.is_Directed = Directed
        self.is_Matrix = Matrix
        if Matrix:
            if Weighted:
                self.graph = [[float('inf') for _i in range(n)]
                              for _j in range(n)]
            else:
                self.graph = [[0 for _i in range(n)] for _j in range(n)]
        else:
            self.graph = [[] for _i in range(n)]

    def _weighted_add_edge(self, x, y, w):
        if self.is_Matrix:
            self.graph[x][y] = w
        else:
            self.graph[x].append((y, w))

    def _unweighted_add_edge(self, x, y):
        if self.is_Matrix:
            self.graph[x][y] = 1
        else:
            self.graph[x].append(y)

    def add_edge(self, x, y, *w):
        if self.is_Directed:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
            else:
                self._unweighted_add_edge(x, y)
        else:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
                self._weighted_add_edge(y, x, w[0])
            else:
                self._unweighted_add_edge(x, y)
                self._unweighted_add_edge(y, x)

    def __getitem__(self, n):
        return self.graph[n]

    def __setitem__(self, n, v):
        if not self.is_Weighted and not self.is_Matrix:
            self.graph[n] = v

    def __str__(self):
        return str([self.graph[i] for i in range(self.sz)])

    def dijkstra(self, s):
        """
        単一始点最短距離を求める関数。dijkstra(s)でsからの任意の頂点への最短距離を求める。到達できなければfloat('inf')を返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならば bfs を使うか，グラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
        """
        if self.is_Matrix:
            print("隣接リスト形式で入力してください")
            raise TypeError
        d = [float('inf') for _ in range(self.sz)]
        b = [-1 for _ in range(self.sz)]  
        q = []
        d[s] = 0
        heapq.heappush(q, (d[s], s))
        while not len(q) == 0:
            p = heapq.heappop(q)
            v = p[-1]
            if d[v] < p[0]:
                continue
            if self.is_Weighted:
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[u] > d[v] + c:
                        d[u] = d[v] + c
                        b[u] = v
                        heapq.heappush(q, (d[u], u))
            else:
                for e in self.graph[v]:
                    u = e
                    if d[u] > d[v] + 1:
                        d[u] = d[v] + 1
                        b[u] = v
                        heapq.heappush(q, (d[u], u))
        return d

    def bellman_ford(self, s):
        """
        単一始点最短距離を求める関数。bellman_ford(s)でsからの任意の頂点への最短距離を求める。到達できなければ　float('inf')　を返す。負のサイクルがある場合は False のみを返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = [float('inf') for _ in range(self.sz)]
        d[s] = 0
        for i in range(self.sz - 1):
            for v in range(self.sz):
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[v] == float('inf'):
                        continue
                    d[u] = min(d[u], d[v] + c)
        for v in range(self.sz):
            for e in self.graph[v]:
                u = e[0]
                c = e[-1]
                if d[v] == float('inf'):
                    continue
                if d[u] > d[v] + c:
                    return False
        return d

    def warshall_froyd(self):
        d = self.graph
        for i in range(self.sz):
            d[i][i] = 0
        for k in range(self.sz):
            for i in range(self.sz):
                for j in range(self.sz):
                    if d[i][k] != float('inf') and d[k][j] != float('inf'):
                        d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d


def AOJ_ALDS_1_11_A():
    
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        g[u - 1] = list(map(lambda x: x - 1, v))
    
    mat_g = Graph(n, Matrix=True)
    for i in range(n):
        for j in g[i]:
            mat_g[i][j] = 1
    for i in range(n):
        print(*mat_g[i])




def AOJ_ALDS_1_11_B():
    
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        g[u - 1] = list(map(lambda x: x - 1, v))
    d = [-1] * n
    f = [-1] * n
    time = 0

    def dfs(G, v):
        nonlocal time
        time += 1
        d[v] = time
        for nv in G[v]:
            if d[nv] != -1:
                continue
            dfs(G, nv)
        time += 1
        f[v] = time

    for v in range(n):
        if d[v] != -1:
            continue
        dfs(g, v)
    for i in range(n):
        print(i + 1, d[i], f[i])




def AOJ_ALDS_1_11_C():
    """
    各頂点の0からの最短距離を bfs で求める
    """
    q = Queue()
    n = ii()
    dist = [-1 for _ in range(n)]
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        g[u - 1] = list(map(lambda x: x - 1, v))
    q.put(0)
    dist[0] = 0
    while not q.empty():
        v = q.get()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                q.put(nv)
    for i in range(n):
        print(i + 1, dist[i])




def AOJ_GRL_1_A():
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    for i in g.dijkstra(start):
        if i == float('inf'):
            print('INF')
        else:
            print(i)
    




def AOJ_ALDS_1_11_C_kai():
    """
    各頂点の0からの最短距離を dijkstra で求める
    """
    n = ii()
    g = Graph(n, Directed=True)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    dist = g.dijkstra(0)
    for i in range(n):
        if dist[i] == float('inf'):
            print(i + 1, -1)
        else:
            print(i + 1, dist[i])




def AOJ_GRL_1_B():
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.bellman_ford(start)
    if d == False:
        print("NEGATIVE CYCLE")
    else:
        d = list(map(lambda x: x if x != float('inf') else 'INF', d))
        for i in d:
            print(i)




def AOJ_GRL_1_C():
    n, m = mi()
    g = Graph(n, Weighted=True, Directed=True, Matrix=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.warshall_froyd()
    d = [list(map(lambda x: x if x != float('inf') else 'INF', d[i]))
         for i in range(n)]
    for i in range(n):
        if d[i][i] < 0:
            print('NEGATIVE CYCLE')
            sys.exit()
    for i in d:
        print(*i)




def ABC132_E():
    N, M = mi()
    g = Graph(3 * N, Directed=True)
    for i in range(M):
        a, b = mi()
        g.add_edge(a - 1, b + N - 1)
        g.add_edge(a + N - 1, b + 2 * N - 1)
        g.add_edge(a + 2 * N - 1, b - 1)
    S, T = mi()
    ans = g.dijkstra(S - 1)[T - 1]
    if ans == float('inf'):
        print(-1)
    else:
        print(ans // 3)


if __name__ == '__main__':
    
    
    
    
    
    
    
    ABC132_E()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
from collections import deque

INF = -1

nVertices, nEdges = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nEdges):
    u, v = map(int, input().split())
    edges[u].append(v)
s, t = map(int, input().split())

dist = [[INF for _ in range(3)] for _ in range(nVertices + 1)]
dist[s][0] = 0
q = deque()
q.append((s, 0))
while q:
    curVertex, curDist = q.popleft()
    for nextVertex in edges[curVertex]:
        nextDist = curDist + 1
        if dist[nextVertex][nextDist % 3] == INF:
            dist[nextVertex][nextDist % 3] = nextDist
            q.append((nextVertex, nextDist))

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

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right





def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")



if __name__ == "__main__":
    N, M = l_inpl()

    to = [[] for _ in range(N)]

    for _ in range(M):
        u, v = l_inpl()
        u, v = u-1, v-1
        to[u].append(v)

    S, T = l_inpl()
    S, T = S-1, T-1

    dist = [[INF, INF, INF] for _ in range(N)]
    dist[S][0] = 0

    q = deque([])
    q.append([S, 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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        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):
        """
        0-indexedでなくてもよいことに注意
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        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
                    heapq.heappush(q, (vd, uv))

        return d

import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d=1, directed=False, ):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        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):
        """
        0-indexedでなくてもよいことに注意
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        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
                    heapq.heappush(q, (vd, uv))

        return d


graph = Dijkstra()
N, M = map(int, input().split())
for i in range(M):
    u, v = map(int, input().split())
    graph.add(u, v+N, directed=True)
    graph.add(u+N, v+2*N, directed=True)
    graph.add(u+2*N, v, directed=True)


S, T = map(int, input().split())
d = graph.Dijkstra_search(S)
if d[T] == float('inf'):
    print(-1)
else:
    print(d[T] // 3)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
from collections import deque


class Graph:

  def __init__(self, directed=True):
    self.directed = directed
    self.V = set()
    self.E = {}

  def add_edge(self, u, v, weight: float = 1.):
    self.V.add(u)
    self.V.add(v)

    if u not in self.E: self.E[u] = {}
    self.E[u][v] = weight

    if not self.directed:
      if v not in self.E: self.E[v] = {}
      self.E[v][u] = weight


def bfs(graph: Graph, s):
  V, E = graph.V, graph.E

  visited = set()
  pred = {}
  dist = {}
  for v in graph.V: dist[v] = -1

  if not s in E:
    return pred, dist

  visited.add(s)
  dist[s] = 0
  queue = deque()
  queue.append(s)
  while len(queue) > 0:
    u = queue.popleft()
    for v in E[u]:
      if v not in visited:
        pred[v] = u
        dist[v] = dist[u] + 1
        visited.add(v)
        if v in E: queue.append(v)

  return pred, dist


def main():
  graph = Graph()

  N, M = map(int, input().strip().split())
  for _ in range(M):
    u, v = input().strip().split()
    
    graph.add_edge(u + '_0', v + '_1')
    graph.add_edge(u + '_1', v + '_2')
    graph.add_edge(u + '_2', v + '_0')

  s, t = input().strip().split()

  pred, dist = bfs(graph, s + '_0')
  
  key = t + '_0'
  if key in dist:
    distance = dist[key]
    if distance % 3 == 0:
      return (distance // 3)

  return -1


print(main())

Solution (Python):
from heapq import heappush, heappop

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 = [{} for _ in range(3 * N + 1)]
for x, y in zip(A, B):
    G[x][y + N] = 1
    G[x + N][y + 2 * N] = 1
    G[x + 2 * N][y] = 1
INF = 10**18


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp = dijkstra(G, S)
ans = (
    -1 if dp[T] == INF else
    dp[T] // 3
)

print(ans)

Solution (Python):

"""
Created on Mon Jul  1 11:43:19 2019

@author: Yamazaki Kenichi
"""
from collections import deque

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

Ta = [[] for i in range(3*N+1)]
for c in uv:
    Ta[c[0]].append(c[1]+N)
    Ta[c[0]+N].append(c[1]+2*N)
    Ta[c[0]+2*N].append(c[1])

check = [0 for i in range(3*N+1)]

q = deque([S])
check[S] = 1
counta = 0
flg = False
while len(q) > 0:
    for i in range(len(q)):
        nexts = Ta[q.popleft()]
        for next_ in nexts:
            if check[next_] != 1:
                q.append(next_)
                check[next_] = 1
    counta += 1
    if check[T] == 1:
        flg = True
        break
if flg:
    print(counta//3)
else:
    print(-1)

Solution (Python):
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 = {(u, i): set([(v, (i + 1) % 3) for v in E[u]])
     for u in E for i in range(3)}


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

Solution (Python):
import collections
N, M = [int(_) for _ in input().split()]
UV = [[int(_) for _ in input().split()] for _ in range(M)]
s, t = [int(_) for _ in input().split()]
v = [[0] * (N + 1) for _ in range(3)]
v[0][s] = 1
G = collections.defaultdict(set)
for U, V in UV:
    G[U].add(V)
Q = collections.deque([[0, s]])
while Q:
    d, i0 = Q.popleft()
    d += 1
    for i1 in G[i0]:
        if not v[1][i1]:
            v[1][i1] = 1
            for i2 in G[i1]:
                if not v[2][i2]:
                    v[2][i2] = 1
                    for i3 in G[i2]:
                        if i3 == t:
                            print(d)
                            exit()
                        elif not v[0][i3]:
                            v[0][i3] = 1
                            Q += [[d, i3]]
print(-1)

Solution (Python):
import collections
N, M = [int(_) for _ in input().split()]
UV = [[int(_) for _ in input().split()] for _ in range(M)]
s, t = [int(_) for _ in input().split()]
v = [[0] * (N + 1) for _ in range(3)]
v[0][s] = 1
G = collections.defaultdict(set)
for U, V in UV:
    G[U].add(V)
Q = collections.deque([[0, s]])
while Q:
    d, i0 = Q.popleft()
    d += 1
    for i1 in G[i0]:
        if not v[1][i1]:
            v[1][i1] = 1
            for i2 in G[i1]:
                if not v[2][i2]:
                    v[2][i2] = 1
                    for i3 in G[i2]:
                        if i3 == t:
                            print(d)
                            exit()
                        elif not v[0][i3]:
                            v[0][i3] = 1
                            Q += [[d, i3]]
print(-1)

Solution (Python):
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())

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

Solution (Python):
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]*3for _ 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)

Solution (Python):
from collections import*
n,m,*t=map(int,open(0).read().split())
*w,s,t=[t-1for 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]*3for _ 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)

Solution (Python):
from collections import*
n,m,*t=map(int,open(0).read().split())
*w,s,t=[t-1for 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]*3for _ 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)

Solution (Python):
import sys
def p(*a):
  s=" ".join(map(str,a))
  
  sys.stderr.write(s+"\n")

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








V=[ [-1,-1,-1] for _ in range(N+1) ]			
V[S][0]=0


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

while Q:
	sv = Q[0][0]
	sl = Q[0][1]
	Q.popleft()
	
	for tv in G[sv]:
		tl = (sl+1)%3
		b = (V[tv][tl]==-1)									
		
		if b:
			V[tv][tl] = V[sv][sl]+1		
			Q.append([tv,tl])					

ans = V[T][0]
if ans > -1: ans //= 3
print(ans)

Solution (Python):
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()
    if cur==t:
      return dist[cur]//3
    for to in graph[cur]:
      if dist[to] == -1:
        dist[to] = dist[cur]+1
        que.append(to)
  return -1

print(bfs())

Solution (Python):
import sys
def p(*a):
  s=" ".join(map(str,a))
  
  sys.stderr.write(s+"\n")

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







V=[ [-1,-1,-1] for _ in range(N+1) ]			
V[S][0]=0


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

while Q:
	FM = Q.popleft()
	
	fm = FM[0]
	l =  FM[1]
	
	for to in G[fm]:
		nl = (l+1)%3
		b = (V[to][nl]==-1)							
		
		if b:
			V[to][nl] = V[fm][l]+1		
			Q.append([to,nl])			

ans = V[T][0]
if ans > -1: ans //= 3
print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)