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 heapq
inf = float('INF')

def dijkstra(graph, n, s):
    costs = [[inf for j in range(3)] for i in range(n+1)]
    costs[s][0], Q = 0, []
    heapq.heappush(Q, [costs[s][0], 0, s])

    while(Q != []):
        c, num, u = heapq.heappop(Q)
        next_ = (num+1)%3
        if u not in graph:
            continue
        for v, three in graph[u].items():
            if costs[u][num] + 1 < costs[v][next_]:
                heapq.heappush(Q, [costs[u][num] + 1, three[next_], v])
                costs[v][next_] = costs[u][num] + 1
    return costs

N,M = map(int, input().split())
graph = {}
for i in range(M):
    u,v = map(int, input().split())
    if u not in graph:
        graph[u] = {}
    graph[u][v] = {}
    graph[u][v][0] = 0
    graph[u][v][1] = 1
    graph[u][v][2] = 2
S,T = map(int,input().split())

di = dijkstra(graph, N, S)
if di[T][0] == inf:
    print(-1)
else:
    print(di[T][0]//3)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if sss[now][nn] == Max:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])


if co == Max:
    print(-1)
else:
    print(co)

Solution (Python):
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

INF = pow(10, 15)

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

  dd = [[INF, INF, INF] for _ in range(n)]
  visited = [[False, False, False] for _ in range(n)]
  s, t = map(int, input().split())
  s -= 1
  t -= 1
  dd[s] = [0,0,0]
  q = [(0, s)]
  ans = -1
  while q:
    d, v = heappop(q)
    if visited[v][d%3]:
      continue
    visited[v][d%3] = True
    if v == t and d % 3 == 0:
      ans = d // 3
      break
    to_d = d + 1
    for to_v in edges[v]:
      if visited[to_v][to_d % 3]:
        continue
      heappush(q, (to_d, to_v))
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)
S,T = map(int,input().split())
S -=1
T -=1
def dijkstra(v):
    d = [inf] * (3*N)
    d[v] = 0
    hq =[(0,v)]

    while hq:
        u = heappop(hq)[1]
        for v in G[u]:
            if d[v] > d[u] + 1:
                d[v] = d[u] +1
                heappush(hq,(d[u]+1,v))
    return d
dist = dijkstra(S)
if dist[T]==inf:
    print(-1)
else:
    print(dist[T]//3)

Solution (Python):
import sys
from collections import deque
n, m=map(int,input().split())
"""
頂点1~nを1~3nに3倍加する
"""
edges=[[] for i in range(3*n)]
for i in range(m):
    """
    uからvへの枝を
    uからv+n, u+nからv+2n, u+2nからv+3n
    とする
    (枝を3倍加)
    """
    u, v=map(int, input().split())
    u, v=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, t=s-1, t-1
q=deque()
q.append(s)
dist=[-1]*(3*n)
dist[s]=0
"""
結局求めるものは，s~tへの最短距離を3で割ったもの
"""
while len(q)!=0:
    fr=q.popleft()
    for to in edges[fr]:
        
        if dist[to]==-1:
            dist[to]=dist[fr]+1
            q.append(to)
print(dist[t]//3)

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

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

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

graph=[]
for _ in range(N+1):
  graph.append([])

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


table=[]
for i in range(N+1):
  table.append([False]*3)

  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  
  
  
  
  
  nset = set()
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      table[v][t%3]=True
      for vv in graph[v]:
        if not table[vv][(t+1)%3]:
          
          nset.add(vv)
          
          
      
  
  
  vlist = list(nset)
  if len(vlist) == 0:
    print(-1)
    break

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, M = LI()
    graph = []
    from collections import defaultdict
    reversed_graph_dict = defaultdict(list)
    for _ in range(M):
        u, v = LI()
        graph.append([u,v])
        reversed_graph_dict[v].append(u)
    S, T = LI()

    

    import collections
    def bfs(graph, root):
        seen, queue = set([root]), collections.deque([[root, 0],])
        first_step_seen = set([])
        second_step_seen = set([])
        while queue:
            vertex, tries = queue.popleft()
            tries += 1

            
            first_step = graph[vertex]

            second_step = []
            for x in set(first_step) - first_step_seen:
                second_step += graph[x]
            first_step_seen |= set(first_step)

            third_step = []
            for x in set(second_step) - second_step_seen:
                third_step += graph[x]
            second_step_seen |= set(second_step)

            for node in set(third_step):
                if node == S:
                    print(tries)
                    return
                if node not in seen:
                    seen.add(node)
                    queue.append([node, tries])
        print(-1)
        return

    bfs(reversed_graph_dict, T)


main()

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

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M = [int(i) for i in input().split()]


for i in range(M):
    u, v = [int(i) for i in input().split()]
    u -= 1
    v -= 1
    g.add_edge(3*u+0, 3*v+1, 1)
    g.add_edge(3*u+1, 3*v+2, 1)
    g.add_edge(3*u+2, 3*v+0, 1)

S, T = [int(i) for i in input().split()]
d1 = Dijkstra(g, (S-1)*3)
ans = 0
if d1.dist[(T-1)*3] != float("inf"):
    print(d1.dist[(T-1)*3]//3)
else:
    print(-1)

Solution (Python):
from heapq import heappop, heappush
N, M = map(int, input().split())
link = {(i, j) : [] for i in range(1, N+1) for j in range(3)}
for _ in range(M):
    u, v = map(int, input().split())
    link[(u, 0)].append((v, 1))
    link[(u, 1)].append((v, 2))
    link[(u, 2)].append((v, 0))
S, T = map(int, input().split())

''' dijkstra '''
INF = 10 ** 9
vstd = {(i, j): False for i in range(1, N+1) for j in range(3)}
dist = {(i, j): INF for i in range(1, N+1) for j in range(3)}  

pq = []

dist[(S, 0)] = 0
heappush(pq, (0, (S, 0)))
while pq:
    _, u = heappop(pq)
    vstd[u] = True
    for v in link[u]:
        if vstd[v]:
            continue
        if dist[u] + 1 < dist[v]:
            dist[v] = dist[u] + 1
            
            heappush(pq, (dist[v], v))


print(dist[(T, 0)] // 3 if dist[(T, 0)] % 3 == 0 else -1)

Solution (Python):
import sys
import heapq
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[u-1].append([v-1 + N, 1])
    G[u-1 + N].append([v-1 + 2*N, 1])
    G[u-1 + 2*N].append([v-1, 1])

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

INF = 10**10
d = [INF for i in range(3*N)]

que = []
d[S-1] = 0
heapq.heappush(que, [0, S-1])

while not(len(que) == 0):
    q = heapq.heappop(que)
    ver = q[1]
    dis = q[0]
    
    if d[ver] < dis:
        continue

    for i in range(len(G[ver])):
        e = G[ver][i]
        if d[e[0]] > d[ver] + e[1]:
            d[e[0]] = d[ver] + e[1]
            heapq.heappush(que, [d[e[0]], e[0]])

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

Solution (Python):
import sys
import heapq
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[u-1].append([v-1 + N, 1])
    G[u-1 + N].append([v-1 + 2*N, 1])
    G[u-1 + 2*N].append([v-1, 1])

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

INF = 10**10
d = [INF for i in range(3*N)]

que = []
d[S-1] = 0
heapq.heappush(que, [0, S-1])

while not(len(que) == 0):
    q = heapq.heappop(que)
    ver = q[1]
    dis = q[0]
    
    if d[ver] < dis:
        continue

    for i in range(len(G[ver])):
        e = G[ver][i]
        if d[e[0]] > d[ver] + e[1]:
            d[e[0]] = d[ver] + e[1]
            heapq.heappush(que, [d[e[0]], e[0]])

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

Solution (Python):
n, m = map(int, input().split())

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

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

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

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    NextCost = 1
    while heap:
        cost,thisNode = heappop(heap)
        for NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    

inf = float('inf')
dist = dijkstra(graph1, n*3, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t]//3)

Solution (Python):


import heapq

INF = float('inf')

def dijkstra(graph, st):
    n  = len(graph)
    ds = [[INF]*3 for _ in range(n)]
    ds[st][0] = 0
    ds[st][1] = INF
    ds[st][2] = INF
    
    qs = [(0, st, 0)]
    heapq.heapify(qs)

    while len(qs) > 0:
        d, nodeId, mod = heapq.heappop(qs)
        
        if d > ds[nodeId][mod]:
            continue
        
        for destId in graph[nodeId]:
            d2 = d + 1
            mod2 = d2%3

            if ds[destId][mod2] > d2:
                ds[destId][mod2] = d2
                heapq.heappush(qs, (d2, destId, mod2))
                
    return (ds)


def main():
    N, M = map(int, input().split())
    
    V = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        V[u-1].append(v-1)

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

    ds = dijkstra(V, S-1)
    x = ds[T-1][0]

    print(x//3 if x != INF else -1)



if __name__ == '__main__':
    main()

Solution (Python):
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
    g[u].append((1,v+N))
    g[u+N].append((1,v+2*N))
    g[u+2*N].append((1,v))

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
S,T = map(int,input().split())
dij = dijkstra(g,3*N,S-1)
ans = dij[T-1]//3
if ans == float('inf') or ans!=ans:
    ans = -1
print(ans)

Solution (Python):

import sys
import heapq
INF = float("inf")



class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u]+w:
                dist[v] = dist[u]+w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    g1 = Graph(3*N)
    for from_, to_ in zip(u, v):
        g1.add_edge((from_-1, N+to_-1, 1))
        g1.add_edge((N+from_-1, 2*N+to_-1, 1))
        g1.add_edge((2*N+from_-1, to_-1, 1))

    dist1, prev1 = shortestPath(g1, S-1)
    
    
    m = INF
    for i in range(3):
        if dist1[i*N+T-1] % 3 == 0 and m > (dist1[i*N+T-1]//3):
            m = dist1[i*N+T-1]//3
    if m == INF:
        print(-1)
    else:
        print(m)

    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):
N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
D = [[-1, -1, -1] for i in range(N)]
Q = [[-1, -1, -1] for i in range(M)]
if M:
  Q[0] = [S - 1, 0, RD[S - 1] % 3]
o = 0
i = 1
while Q:
  q, d, m = Q[o]
  Q[o] = [-1, -1, -1]
  o = (o + 1) % M
  if q == -1:
    break
  if RD[q] == -1:
    continue
  D[q][m] = d + RD[q]
  if m != 0:
    for adj in E[q]:
      _m = (d + 1 + RD[adj]) % 3
      if D[adj][_m] == -1:
        Q[i] = [adj, d + 1, _m]
        i = (i + 1) % M
P = [d[0] for d in D if d[0] != -1]
if P:
  print(min(P) // 3)
else:
  print(-1)

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import time
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

t = time.time()
N, M = MAP()

uv = [LIST() for _ in range(M)]
S, T = MAP()
S = S-1
T = T-1
graph = defaultdict(list)
flag = False
for u, v in uv:
	if v-1 == T:  
		flag = True
	graph[v-1].append(u-1)
if not flag:
	print(-1)
	sys.exit(0)

q = deque([])
q.append((T, 0, "a"))
sirusi = [[] for _ in range(N)]  
count = 0
while q:
	if count >= 3*N+1:  
		break
	search, step, state = q.popleft()
	
	if state in sirusi[search]:
		continue
	sirusi[search].append(state)
	count += 1
	
	if search == S and state == "a":
		break

	for node in graph[search]:
		if state == "a":
			q.append((node, step+1, "b"))
		elif state == "b":
			q.append((node, step+1, "c"))
		else:
			q.append((node, step+1, "a"))

if "a" in sirusi[S]:
	print(step//3)
else:
	print(-1)

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

Solution (Python):
from heapq import *
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,0])
    G[3*u+1].append([3*v+2,0])
    G[3*u+2].append([3*v+0,1])
S,T=map(int,input().split())
INF=10**9+7
def dijkstra(G,s):

  d=[INF]*(3*N)
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d
d=dijkstra(G,(S-1)*3)
if d[(T-1)*3]==INF:
  print(-1)
else:
  print(d[(T-1)*3])

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
n,m=map(int,input().split())
Edges=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(lambda x: int(x)-1,input().split())
    Edges[u].append(v)
s,t=map(lambda x: int(x)-1,input().split())
q=deque()
q.append((s,0))
Flag=[[False]*n for _ in range(3)]
while q:
    v,dist=q.popleft()
    if Flag[dist%3][v]==True:
        continue
    if dist%3!=0:
        for to in Edges[v]:
            q.append((to,dist+1))
        Flag[dist%3][v]=True
        continue
    elif v==t:
        print(dist//3)
        exit()
    else:
        for to in Edges[v]:
            q.append((to,dist+1))
        Flag[0][v]=True
print(-1)

Solution (Python):
import heapq
N,M = map(int,input().split())
edge = [[[] for i in range(N)] for j in range(3)]

for i in range(M):
	u,v = map(int,input().split())
	u -= 1
	v -= 1
	edge[0][u].append(v)
	edge[1][u].append(v)
	edge[2][u].append(v)
S,T = map(int,input().split())
S -= 1
T -= 1
INF = 10**10
dist = [[0 if i == S and j == 0 else INF for i in range(N)] for j in range(3)]
search = []
searched = [[False for i in range(N)] for j in range(3)]
heapq.heapify(search)
heapq.heappush(search, (0, 0, S))
while len(search) > 0 and dist[0][T] == INF:
	x = heapq.heappop(search)
	d, t, node = x[0], x[1], x[2]
	if searched[t][node]:
		continue
	searched[t][node] = True
	dist[t][node] = d
	for i in edge[t][node]:
		if not searched[(t+1)%3][i]:
			heapq.heappush(search, (d+(t+1)//3, (t+1) % 3, i))
if dist[0][T] < INF:
	print(dist[0][T])
else:
	print(-1)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return


def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return


def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    
    

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    
    

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod


def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge, g):

    dist = defaultdict(lambda: inf)
    dist[(start,0)] = 0
    q = [(dist[(start,0)], start, 0)]
    while q:
        du, u, t = heappop(q)
        for j in edge[u]:
            if t == 2:
                t = -1
            if dist[(j, t + 1)] > du + 1:
                dist[(j, t + 1)] = du + 1
                heappush(q, [dist[(j, t + 1)], j, t + 1])
    return dist

def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = defaultdict(list)
    for x,y in v:
        edge[x].append(y)
    d = dijkstra(n, s, edge, t)
    if d[(t,0)] == inf:
        print(-1)
    else:
        print(d[(t,0)]//3)
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    E()

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

Solution (Python):
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]//3if t[d][0]>0 else -1)

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