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

import sys
from collections import defaultdict, deque


class Node:
    def __init__(self, label, index):
        self.label = label
        self.index = index

    def __eq__(self, other):
        return (self.label == other.label) and (self.index == other.index)

    def __str__(self):
        return "(" + ",".join(map(str, [self.label, self.index])) + ")"

    def __repr__(self):
        return self.__str__()


def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    if M == 0:
        print(-1)
        return
    a = defaultdict(list)
    b = defaultdict(list)
    c = defaultdict(list)
    edge = [a, b, c]
    for i in range(M):
        edge[0][u[i]].append(Node(1, v[i]))
        edge[1][u[i]].append(Node(2, v[i]))
        edge[2][u[i]].append(Node(0, v[i]))
    start_node = Node(0, S)
    end_node = Node(0, T)

    class BFSearch:
        def __init__(self):
            self.queue = deque()
            a = [0] * (M + 1)
            b = [0] * (M + 1)
            c = [0] * (M + 1)
            self.steps = [a, b, c]

        def search(self, node):
            self.queue.append(node)
            while self.queue:
                node_now = self.queue.popleft()
                step_now = self.steps[node_now.label][node_now.index]
                next_nodes = edge[node_now.label][node_now.index]
                for next_node in next_nodes:
                    s = self.steps[next_node.label][next_node.index]
                    if s > 0:
                        continue
                    if next_node == end_node:
                        return step_now + 1
                    self.steps[next_node.label][next_node.index] = step_now + 1
                    self.queue.append(next_node)
            return -1

    dfs = BFSearch()
    ans = dfs.search(start_node)
    print(ans // 3 if ans % 3 == 0 else -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))  
    u = [int()] * (M)  
    v = [int()] * (M)  
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  
    T = int(next(tokens))  
    solve(N, M, u, v, S, T)


if __name__ == "__main__":
    main()

Solution (Python):
def f(n, m):
    to = {}
    for _ in range(m):
        u, v = map(int, input().split())
        to.setdefault(u, [])
        to[u] += [v]
    s, t = map(int, input().split())
    vst = [[False] * 3 for _ in range(n + 1)]
    a = [s]
    vst[s][0] = True
    cnt = 0
    while a:
        b = []
        cnt += 1
        j = cnt % 3
        for ak in a:
            if ak not in to: continue
            for i in to[ak]:
                if vst[i][j]: continue
                vst[i][j] = True
                b.append(i)
            if vst[t][0]:
                print(cnt // 3)
                exit()
        a = b
    print(-1)

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

Solution (Python):

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)

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 = True: 有向かどうか
        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=True, 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 _convert_to_maxrix(self):
        if self.is_Matrix:
            return self
        mat_g = self.__class__(
            self.sz,
            Weighted=self.is_Weighted,
            Directed=self.is_Directed,
            Matrix=True)
        if self.is_Weighted:
            for i in range(self.sz):
                for j in self.graph[i]:
                    mat_g.add_edge(i, j[0], j[1])
        else:
            for i in range(self.sz):
                for j in self.graph[i]:
                    mat_g.add_edge(i, j)
        return mat_g

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

    
    
    

    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):
        """
        全頂点間最短距離を求める関数。warshall_froyd()で任意の頂点間の最短距離を求める。到達できなければ　float('inf')　を返す。
        負のサイクルがあるかどうかは自分自身との最短距離 d[i][i] の中に負のものがあるかどうかで分かる。

        Warning
        ----------
            隣接行列形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = self._convert_to_maxrix()
        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():
    """
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A&lang=jp
    """
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    mat_g = g._convert_to_maxrix()
    for i in range(n):
        print(*mat_g[i])



def AOJ_ALDS_1_11_B():
    """
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=jp
    """
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    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 で求める
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
    """
    q = Queue()
    n = ii()
    dist = [-1 for _ in range(n)]
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    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():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp"""
    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 で求める。
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
    """
    n = ii()
    g = Graph(n, Weighted=True)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1, 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():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp"""
    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():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=jp"""
    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():
    """
    頂点3倍するdijkstra法。頂点倍加の典型例として
    https://atcoder.jp/contests/abc132/tasks/abc132_e
    """
    N, M = mi()
    g = Graph(3 * N)
    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)


def ABC079_D():
    """https://atcoder.jp/contests/abc079/tasks/abc079_d"""
    H, W = mi()
    mat = [[] for __ in range(10)]
    for i in range(10):
        mat[i] = lmi()
    g = Graph(10, Matrix=True, Weighted=True)
    g.graph = mat
    cost = g.warshall_froyd()
    field = [[] for _ in range(H)]
    for i in range(H):
        field[i] = lmi()
    ans = 0
    for i in range(H):
        for j in range(W):
            if field[i][j] != -1:
                ans += cost[field[i][j]][1]
    print(ans)


if __name__ == '__main__':
    
    
    
    
    
    
    
    ABC132_E()

Solution (Python):
import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
vertices = [[] for _ in range(n+1)]
jumpValue = [[-1,-1,-1] for _ in range(n+1)]
queue = []
def bfs(arr,jump):
    for node in arr:
        if jumpValue[node][(jump+1)%3]==-1:
            queue.append([node,jump+1])
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    vertices[a].append(b)
s,t = map(int,sys.stdin.readline().split())
queue=deque()
queue.append([s,0])
while(len(queue)>0 ):
    next=queue.popleft()
    if jumpValue[next[0]][next[1]%3] == -1:
        jumpValue[next[0]][next[1]%3] = next[1]
        bfs(vertices[next[0]], next[1])
        if jumpValue[t][0]!=-1:
            break
print(max(jumpValue[t][0]//3,-1))

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

nodes = [[] for _ in range(3 * N)]
 
confilm = [False] * (3 * N)  
 
costs = [-1] * (3 * N)  
 

for _ in range(M) :
    fromNode , toNode = map(int,input().split())
    fromNode -= 1
    toNode -= 1
    fromNode *= 3
    toNode *= 3
 
    nodes[fromNode].append((toNode + 1,1))
    nodes[fromNode + 1].append((toNode + 2,1))
    nodes[fromNode + 2].append((toNode,1))
 
 

startNode , endNode = map(int,input().split())
startNode -= 1
endNode -= 1

startNode *= 3
endNode *= 3
 
costs[startNode] = 0
 
q = [(0,startNode)]
 

while q : 
    nowCost , nowNode = heapq.heappop(q)
 
    if confilm[nowNode] :
        continue
 
    confilm[nowNode] = True
 
    
    for nextNode , cost in nodes[nowNode] :
        
        nextCost = nowCost + cost
        if costs[nextNode] == -1 or nextCost < costs[nextNode] :
            costs[nextNode] = nextCost  
            heapq.heappush(q,(nextCost,nextNode))
 
if costs[endNode] < 0 :
    print(-1)
else :
    print(costs[endNode] // 3)

Solution (Python):
def dijkstra(edge,start,end) :
    import heapq

    minCosts = [float('inf') for _ in range(len(edge))]

    nodeHeap = []
    heapq.heappush(nodeHeap, (0, start))  

    while nodeHeap :
        cost, node = heapq.heappop(nodeHeap)

        if minCosts[node] <= cost :
            continue

        minCosts[node] = cost

        for nextNode , weight in edge[node] :
            newCost = cost + weight
            heapq.heappush(nodeHeap, (newCost, nextNode))
    dist = minCosts[endNode]
    if dist == float('inf') :
        return -1
    return dist

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


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


for _ in range(M) :
    fromNode , toNode = map(int,input().split())
    fromNode -= 1
    toNode -= 1
    fromNode *= 3
    toNode *= 3

    nodes[fromNode].append((toNode + 1,1))
    nodes[fromNode + 1].append((toNode + 2,1))
    nodes[fromNode + 2].append((toNode,1))


startNode , endNode = map(int,input().split())
startNode -= 1
endNode -= 1
startNode *= 3
endNode *= 3

ans = dijkstra(nodes,startNode,endNode)

if ans == -1 :
    print(ans)
else :
    print(ans // 3)

Solution (Python):
def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    a, b = set(), set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        v = set()
        for j in e[i]:
            if j in a: continue
            a.add(j)
            for k in e[j]:
                if k in b: continue
                b.add(k)
                v.update(e[k])
        if t in v:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(v)]
    return -1


print(BC132_E())

Solution (Python):
from collections import*
n, m, *t = map(int, open(0).read().split())       
*w, s, t = [a-1for a in t]         
e = [[]for _ in range(n)]        
for u, v in zip(w[::2], w[1::2]):      
    e[u].append(v)

INF = 10**10
f = [[INF]*3for _ in range(n)]        
f[s][0] = 0        
q = deque([(s, 0)])           
while q:
    vi, j = q.popleft()         
    if vi == t and j == 0:
        print(f[vi][0]//3)
        break
    for ui in e[vi]:           
        if f[ui][(j+1)%3] < INF: continue           
        f[ui][(j+1)%3] = f[vi][j] + 1
        q.append((ui, (j+1)%3))
else:
    print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))

def f(D, S, T):
    close = [[False] * N, [False] * N, [False] * N]
    Q = []
    index = 0
    Q.append((S, 0, 0))

    while len(Q) > index:
        p, c, l = Q[index]
        index += 1
        
        if close[l][p]:
            continue
        
        if l == 0 and p == T:
            return c // 3
        close[l][p] = True

        l, c = (l + 1) % 3, c + 1
        for n in D[p]:
            if close[l][n]:
                continue
            Q.append((n, c, l))
    return -1

if __name__ == "__main__":
    D = {n: set() for n in range(N)}
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        D[u].add(v)

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

    print(f(D, S, T))

Solution (Python):
import sys
input = sys.stdin.readline


		
def main():
	n, m = map(int, input().split())
	
	nn=[ [] for _ in range(n+1)]
	
	for _ in range(m):
		u, v = map(int, input().split())
		nn[u].append(v)
		
	start, goal = map(int, input().split())
	
	arrived = set()
	opened = [start]
	cc=1
	while len(opened) > 0:
		
		
		for i in opened:
			arrived.add(i)
		tt =opened.copy()
		opened=[]
		
		
		for i in range(3):
			temp=set()
			for p in tt:
				for i in nn[p]:
					temp.add(i)
			tt=list(temp)
			
		
		if goal in tt:
			return cc
		cc+=1
		
		for ttt in tt:
			if ttt not in arrived:
				opened.append(ttt)
	return -1
		
		

	
	


if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):

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

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)

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

from collections import deque

def bfs(start, terminal):
    q = deque([(start, 0)])
    color = [[0]*3 for _ in range(N)]
    d = [[-1]*3 for _ in range(N)]
    d[start][0] = 0
    l = 0
    while len(q) > 0:
        u, l = q.popleft()
        nl = (l + 1) % 3
        for v in G[u]:
            if color[v][nl] == 0:
                q.append((v, nl))
                color[v][nl] = 1
                d[v][nl] = d[u][l] + 1
    
    if d[terminal][0] == -1:
        return -1
    else:
        return d[terminal][0] // 3 

print(bfs(S, T))

Solution (Python):
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 = 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, T = S-1, T-1
visit = [False for i in range(3 * N)]
length = [0 for i in range(3 * N)]
def bfs(v):
    Q = []
    Q.append(v)
    visit[v] = True
    while Q:
        v = Q.pop(0)
        for u in graph[v]:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                
bfs(S)

if visit[T]:
    print(int(length[T] //3))
else:
    print(-1)