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

inputs=[]
n,m=map(int,input().split())
for i in range(m):
    a=[int(j) for j in input().split()]
    inputs.append((a[0],a[1]+10**5,1))
    inputs.append((a[0]+10**5,a[1]+2*10**5,1))
    inputs.append((a[0]+2*10**5,a[1],1))
S,T=map(int,input().split())

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)

d = Dijkstra(g, S)   
ans=d.shortest_distance(T)

if ans>10**9+7:
    print(-1)
else:
    if ans%3==0:
        print(ans//3)
    else:
        print(-1)

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

Solution (Python):
from collections import deque
def bfs():
  while len(q) > 0:
    p = q.popleft()
    for e in g[p]:
      if d[e] < 0:
        q.append(e)
        d[e] = d[p] + 1
        f[e] = p
      elif d[e] > d[p] + 1:
        d[e] = d[p] + 1
        f[e] = p       

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

d = [-1] * (3 * (n+1))
f = [-1] * (3 * (n+1))
d[3*s] = 0
f[3*s] = 0
q = deque([3*s])
bfs()
c = 0
if f[3*t] == -1:
  print(-1)
  exit()

t = 3 * t
while f[t] > 0:
  c += 1
  t = f[t]
  
print(c // 3)

Solution (Python):
from collections import deque

INF = int(1e9 + 7)


def bfs(g, s, t):
    q = deque()
    q.append((s, 0))
    d = [] * 100000
    for _ in range(100000):
        d.append([INF, INF, INF])
    d[s][0] = 0
    while q:
        v_c, l = q.popleft()
        nl = (l + 1) % 3
        for vt in g[v_c]:
            if d[vt][nl] != INF:
                continue
            d[vt][nl] = d[v_c][l] + 1
            if vt == t and nl == 0:
                return d[vt][nl] // 3
            q.append((vt, nl))
    return -1


n, m = map(int, input().split())
graph = [] * n
for i in range(n):
    graph.append([])
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)
s, t = map(int, input().split())
print(bfs(graph, s - 1, t - 1))

Solution (Python):
from collections import deque
N, M = map(int, input().split())
node_dic = {}

for i in range(3 * N):
    node_dic[i] = []

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

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

ans_array = [-1] * (3 * N)
use_array = [0] * (3 * N)

edge_queue = deque()
ans_array[(S-1)*3] = 0
use_array[(S-1)*3] = 1
edge_queue.append((S-1)*3)
while(len(edge_queue)):
    edge = edge_queue.popleft()
    value = ans_array[edge]
    for e in node_dic[edge]:
        if not use_array[e]:
            edge_queue.append(e)
            ans_array[e] = value + 1
            use_array[e] = 1

print(ans_array[(T-1)*3]//3)

Solution (Python):
from collections import deque


def main():
    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[3 * u].append(3 * v + 1)
        edges[3 * u + 1].append(3 * v + 2)
        edges[3 * u + 2].append(3 * v)

    S, T = map(lambda x: (int(x) - 1) * 3, input().split())
    q = deque([(S, 0)])
    nodes = [-1] * (3 * N)

    while q:
        cv, count = q.popleft()

        if cv == T:
            nodes[cv] = count if nodes[cv] == -1 else min(nodes[cv], count)
        else:
            if nodes[cv] == -1 or count < nodes[cv]:
                nodes[cv] = count
                for u in edges[cv]:
                    q.append((u, count + 1))

    print(nodes[T] // 3 if nodes[cv] != -1 else -1)


if __name__ == '__main__':
    main()

Solution (Python):
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([(S, 0)])
dist = [inf] * (N * 3)
dist[S] = 0

while dq:
    v, c = dq.popleft()
    nc = c + 1
    for nv in es[v]:
        if nc < dist[nv]:
            dist[nv] = nc
            if v == T:
                break
            dq.append((nv, nc))

if dist[T] == inf:
    print(-1)
else:
    print(dist[T] // 3)

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

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

def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=0
    w=deque([0,s])
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n*=3
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

if __name__=="__main__":
    sol()

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

def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

if __name__=="__main__":
    sol()

Solution (Python):
from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

if __name__=="__main__":
    sol()

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:
      m[u][count %3] = True
      for v in a[u]:
        if (v == T and count %3 ==0):
          return count//3
        if not(m[v][(count+1) %3]):
          m[v][(count+1) %3]=True
          c2.append(v)
    c = c2
  return -1
print(main())

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

Solution (Python):



""" convenient functions




"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product 

from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from operator import itemgetter


from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) 
def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs

    
    

    
    
    
    
    

    
    
    
    

    
    
"""


r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input







"""






N, M = R()
UV = [R() for _ in range(M)]
S, T = R()
S -= 1
T -= 1
pos = [[] for _ in range(3*N)]
for u, v in UV:
    u -= 1
    v -= 1
    pos[u].append(v+N)
    pos[u+N].append(v+2*N)
    pos[u+2*N].append(v)
    
    
    

task1 = []
task2 = []
task1.extend(pos[S])
arrived = [False] * (3*N)

counter = 0
while task1:
    counter += 1
    if T in task1:
        break
    for i in task1:
        if arrived[i] == True:
            continue
        arrived[i] = True
        task2.extend(pos[i])
    task1 = task2
    task2 = []
else:
    print(-1)
    exit()
counter //= 3
print(counter)




"""memo: how to use defaultdict of list

Dic = defaultdict(list)

Dic[x].append(y)

for k, v in Dic.items():
"""

Solution (Python):

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[(u, 0)].append((v, 1))
        edges[(u, 1)].append((v, 2))
        edges[(u, 2)].append((v, 0))

    s, t = map(int, input().split())

    

    dones = set()
    que = deque()
    que.append(((s, 0), 0))
    while que:
        node, step = que.popleft()

        next_nodes = edges[node]
        
        for n, l in next_nodes:
            if n == t and l == 0:
                print((step + 1) // 3)
                exit()

            if (n, l) not in dones:
                que.append(((n, l), step + 1))
                dones.add((n, l))
    print(-1)


if __name__ == '__main__':
    main()

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

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from heapq import heappush, heappop

def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF ] *n
    visited = [False ] *n

    dist[start] = 0
    que = [(0, start)]

    while que:
        cost, cur = heappop(que)

        if visited[cur]:
            continue

        visited[cur] = True

        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))

    return dist


n, m = li()

graph = [[] for _ in range(3*n)]
for _ in range(m):
    u, v = li_()
    for i in range(3):
        graph[i*n + u].append([(i+1)%3 * n + v, 1])

s, t = li_()
INF = 1<<62
dist = dijkstra(graph, s, INF)

print(-1 if dist[t] == INF else dist[t] // 3)

Solution (Python):
from collections import deque

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

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

for _ in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    connect[u].append(v+N)
    connect[u+N].append(v+2*N)
    connect[u+2*N].append(v)

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

def bfs(s):
    q = deque()
    q.append(s)
    d = [-1 for _ in range(3*N)]
    d[s] = 0
    
    while q:
        v = q.popleft()
        if v == T:
            return d[v]
    
        for u in connect[v]:
            if d[u] == -1:
                q.append(u)
                d[u] = d[v]+1
                
    return -1

ans =  bfs(S)

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

Solution (Python):

import heapq

N, M = map(int, input().split())
MAX = float("inf")

nodes = [[] for i in range(N+1)]

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


d = [
    [MAX for i in range(N)],
    [MAX for i in range(N)],
    [MAX for i in range(N)],
]
d[0][S] = 0
queue = []
heapq.heappush(queue, [0, 0, S])

while queue:
    p, m, n = heapq.heappop(queue)
    if m == 0 and n == T:
        print(int(p/3))
        quit()
    for to in nodes[n]:
        if d[(m+1) % 3][to] > d[m][n] + 1:
            d[(m+1) % 3][to] = d[m][n] + 1
            heapq.heappush(queue, [
                d[(m+1) % 3][to],
                (m+1) % 3,
                to
            ])

print(-1)

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

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

if __name__ == '__main__':
	main()

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

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

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

Solution (Python):
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = 3 * 10 ** 5 + 10
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


N, M = map(int, input().split())
from collections import defaultdict

graph = defaultdict(dict)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u][v + N] = 1
    graph[u + N][v + 2 * N] = 1
    graph[u + 2 * N][v] = 1
S, T = map(int, input().split())
S -= 1
T -= 1
dj = Dijkstra(graph, S)

dist, _ = dj.execute()
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Solution (Python):
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = 3 * 10 ** 5 + 10
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


N, M = map(int, input().split())
from collections import defaultdict

graph = defaultdict(dict)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u][v + N] = 1
    graph[u + N][v + 2 * N] = 1
    graph[u + 2 * N][v] = 1
S, T = map(int, input().split())
S -= 1
T -= 1
dj = Dijkstra(graph, S)

dist, _ = dj.execute()
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Solution (Python):
def e_hopscotch_addict(N, M, Edges, S, T, INF=float('inf')):
    from collections import deque

    graph = [[] for _ in range(N)]
    for u, v in Edges:
        graph[u - 1].append(v - 1)
    start, target = S - 1, T - 1

    
    graph_prime = [[INF] * N for _ in range(3)]
    graph_prime[0][start] = 0  
    queue = deque([(start, 0)])  
    while queue:
        vertex, t = queue.popleft()
        u = (t + 1) % 3
        for to in graph[vertex]:
            if graph_prime[u][to] != INF:
                continue  
            queue.append((to, u))
            graph_prime[u][to] = graph_prime[t][vertex] + 1
    return graph_prime[0][target] // 3 if graph_prime[0][target] != INF else -1

N, M = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
S, T = [int(i) for i in input().split()]
print(e_hopscotch_addict(N, M, Edges, S, T))

Solution (Python):

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)