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

inf=10**9
import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """    
    class Edge():
        
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        
        self.G = [[] for _ in range(V)] 
        self. _E = 0 
        self._V = V 
    
    
    def E(self):
        return self._E
    
    
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s):
        
        
        que = [] 
        d = [inf] * self.V()
        prev = [None]*self.V() 
        d[s] = 0
        heapq.heappush(que,(0,s)) 
        
        while len(que)!=0:
            
            cost,v = heapq.heappop(que)
            
            
            if d[v] < cost:
                continue
                
            
            for i in range(len(self.G[v])):
                e = self.G[v][i] 
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost 
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) 

        return d




import sys
input = sys.stdin.readline

N,M=map(int,input().split())
djk = Dijkstra(N*3)

for i in range(M):
    u,v=map(int,input().split())
    u-=1
    v-=1
    djk.add(u,N+v,1)
    djk.add(N+u,2*N+v,1)
    djk.add(2*N+u,v,1)
S,T=map(int,input().split())

d = djk.shortest_path(S-1)
ans=d[T-1]//3
if ans==inf//3:
    ans=-1
print(ans)

Solution (Python):
from heapq import heappop, heappush

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

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

ans = -1
visited = set()  
q = [(0, S)]
while q:
    c, v = heappop(q)  
    key = (c % 3, v)
    if key in visited:
        continue
    visited.add(key)  
    if v == T and c % 3 == 0:
        ans = c//3
        break
    c += 1  
    d = c % 3  
    for u in graph[v]:
        new_key = (d, u)
        if new_key in visited:
            continue
        heappush(q, (c, u))

print(ans)

Solution (Python):
from heapq import heappop, heappush

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
S, T = map(lambda x: int(x)-1, input().split())

ans = -1
visited = set()
q = [(0, S)]
ans = -1
while q:
    c, v = heappop(q)  
    key = (c % 3, v)
    if key in visited:
        continue
    visited.add(key)
    if v == T and c % 3 == 0:
        ans = c//3
        break
    c += 1
    d = c % 3
    for u in graph[v]:
        new_key = (d, u)
        if new_key in visited:
            continue
        heappush(q, (c, u))

print(ans)

Solution (Python):
from collections import deque

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

graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  graph[u-1].append(v-1)

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


is_visited = [[False]*N for i in range(3)]
is_visited[0][s] = True

d = deque([s])
ans = 0
while d:
  ans += 1
  for step in [1, 2, 0]:
    diff = 0
    if d:
      len_d = len(d)
      for i in range(len_d):
        node = d.popleft()
        children = graph[node]
        for child in children:
          if step == 0:
            if child == t:
              d = []
              diff = 1
              break
          
          if not is_visited[step][child]:
            is_visited[step][child] = True
            diff += 1
            d.append(child)
          
        else:
          continue
        break
    
    else:
      ans = -1
      break
  
  if not diff:
    ans = -1
    break

print(ans)

Solution (Python):
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Solution (Python):
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

next_dict = {}

for i in range(1,n*3 + 1):
    next_dict[i] = []

for i in range(m):
    u,v = uv[i]
    for j in range(3):
        next_dict[u + (j * n)].append((v + ((j+1)%3 * n )))

from collections import deque
d = deque()
d.append(s)

length = [-1] * (3*n + 1)
length[s] = 0

while(True):
    if(len(d) == 0):
        break

    num = d.popleft()
    for i in next_dict[num]:
        if( length[i] == -1 ):
            d.append(i)
            length[i] = length[num] + 1

    if(length[t] != -1):
        break

print(length[t] // 3)

Solution (Python):
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

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

Solution (Python):
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

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

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

def dijkstra(graph,N,s):
    distance = {(i + 1, j): 1e7 for i in range(N) for j in range(3)}
    distance[s]=0
    q=[]
    heapq.heappush(q,(distance[s],s))
    while len(q)>0:
        cost,v=heapq.heappop(q)
        if cost>distance[v]:
            continue
        else:
            for w in graph[v]:
                if distance[w]>distance[v]+1:
                    distance[w]=distance[v]+1
                    heapq.heappush(q,(distance[w],w))
    return distance


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))
    distance=dijkstra(graph,N,(S,0))
    d=distance[(T,0)]
    if d%3==0:
        print(d//3)
    else:
        print(-1)

Solution (Python):
from collections import deque

N,M=map(int,input().split())
a=[[[] for j in range(N)] for i in range(3)] 
for i in range(M):
    u,v=map(lambda x:int(x)-1,input().split())
    a[0][u].append((1,v))
    a[1][u].append((2,v))
    a[2][u].append((0,v))
S,T=map(lambda x:int(x)-1,input().split())


r=[[-3 for j in range(N)] for i in range(3)]
q=deque()
q.append((0,S));r[0][S]=0
while q:
    ui,uj=q.popleft()
    for vi,vj in a[ui][uj]:
        if r[vi][vj]==-3:
            r[vi][vj]=r[ui][uj]+1
            q.append((vi,vj))

print(r[0][T]//3)

Solution (Python):
import sys
from collections import deque



read = sys.stdin.read
N, M, *uv, S, T = map(int, read().split())

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 15

dist = [[INF] * (N + 1) for _ in range(3)]
stack = deque([(0, S)])

while stack:
    cost, v = stack.popleft()
    r = cost % 3
    if dist[r][v] != INF:
        continue
    if r == 0 and v == T:
        print(cost // 3)
        exit()

    dist[r][v] = cost
    for i in graph[v]:
        stack.append((cost + 1, i))
else:
    print(-1)

Solution (Python):
import sys
from collections import deque



read = sys.stdin.read
N, M, *uv, S, T = map(int, read().split())

graph = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(uv)] * 2):
    graph[u].append(v)

INF = 10 ** 15

dist = [[INF] * (N + 1) for _ in range(3)]
stack = deque([(0, S)])

while stack:
    cost, v = stack.popleft()
    if dist[cost % 3][v] != INF:
        continue

    dist[cost % 3][v] = cost
    for i in graph[v]:
        stack.append((cost + 1, i))

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

Solution (Python):
from collections import deque

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

Solution (Python):
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
L = [[] for i in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    L[a].append(b)


S, T = map(int, input().split())
dist = [[10**9 for i in range(N + 1)] for j in range(3)]
dist[0][S] = 0

Q = []
for i in L[S]:
    Q.append([i, S, 0])

for i in range(10 ** 7):
    if len(Q) == i:
        break
    if dist[(Q[i][2] + 1) % 3][Q[i][0]] == 10**9:
        dist[(Q[i][2] + 1) % 3][Q[i][0]] = dist[(Q[i][2]) % 3][Q[i][1]] + 1
        for j in L[Q[i][0]]:
            if dist[(Q[i][2] + 2) % 3][j] == 10**9:
                Q.append([j, Q[i][0], Q[i][2] + 1])
if dist[0][T] % 3 == 0:
    print(dist[0][T] // 3)
else:
    print(-1)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
G = [[[] for j in range(3)] for i in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    for i in range(3):
        G[u][i].append((v, (i+1) % 3))
S, T = map(int, input().split())


visited = [[-1] * 3 for _ in range(N+1)]

que = deque([(S, 0, 0)])
visited[S][0] = 0

while que:
    ci, l, d = que.popleft()

    for ni, nl in G[ci][l]:
        if visited[ni][nl] == -1:
            que.append((ni, nl, d+1))
            visited[ni][nl] = d+1

print(visited[T][0]//3)

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+1)]
for i,j in edge:
    c[i].append(N+j)
    c[N+i].append(N+N+j)
    c[N+N+i].append(j)
S,T=map(int, input().split())
from collections import deque
d=[inf]*(N*3+1)
d[S]=0
q=deque([S])
x=1
while q:
    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
print(d[T]//3 if d[T]<inf else -1)

Solution (Python):
def solve():
    N, M = map(int, input().split())
    edges = [[] for _ in range(N*3+1)]
    for i in range(M):
        u, v = map(int, input().split())
        u2, u3 = u+N, u+2*N
        v2, v3 = v+N, v+2*N
        edges[u].append(v2)
        edges[u2].append(v3)
        edges[u3].append(v)
    S, T = map(int, input().split())
    
    dist = [10**15 for _ in range(N*3+1)]
    dist[S] = 0
    que = [S]
    while que:
        que_tmp = []
        for parent in que:
            for child in edges[parent]:
                if dist[child] != 10**15:
                    continue
                que_tmp.append(child)
                dist[child] = dist[parent] + 1
        que = que_tmp
    
    if dist[T] != 10**15:
        print(dist[T]//3)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
n,m=map(int,input().split())
l=[[] for i in range(n+1)]
lb=[[] for i in range(n+1)]
d0={}
d1={}
d2={}
for i in range(n):
  d1[i+1],d2[i+1],d0[i+1]=0,0,0
for i in range(m):
  a,b=map(int,input().split())
  l[a].append(b)
  lb[b].append(a)
s,t=map(int,input().split())
q0=deque([t])
q1=deque([])
q2=deque([])
bool1=True
now=0
ans=-1
while q0 or q1 or q2:
  if now%3==0:
    while q0:
      a=q0.popleft()
      d=lb[a]
      for i in d:
        if d1[i]==1:
          pass
        else:
          d1[i]=1
          q1.append(i)
  elif now%3==1:
    while q1:
      a=q1.popleft()
      d=lb[a]
      for i in d:
        if d2[i]==1:
          pass
        else:
          d2[i]=1
          q2.append(i)
  elif now%3==2:
    while q2:
      a=q2.popleft()
      d=lb[a]
      for i in d:
        if i==s and bool1:
          ans=(now+1)//3
          bool1=False
        if d0[i]==1:
          pass
        else:
          d0[i]=1
          q0.append(i)
  now=now+1
print(ans)

Solution (Python):
from heapq import heappop, heappush

N, M = map(int, input().split())
INF = 10**10

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

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

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

minDist = [INF] * (3 * N)
que = [(0, S)]

while que:
    dist, now = heappop(que)

    if minDist[now] <= dist:
        continue
    minDist[now] = dist

    dist += 1

    for to in edges[now]:
        if minDist[to] > dist:
            heappush(que, (dist, to))

ans = minDist[T]

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

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n,m=map(int,input().split())
    N=3*n
    E=[[] for _ in range(N)]
    for _ in range(m):
        u,v=map(int,input().split())
        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=map(int,input().split())
    s-=1; t-=1
    S=3*s; T=3*t
    dist=[INF]*N
    dist[S]=0
    Q=deque([S])
    while(Q):
        v=Q.popleft()
        for nv in E[v]:
            if(dist[nv]!=INF): continue
            dist[nv]=dist[v]+1
            Q.append(nv)

    print(dist[T]//3 if(dist[T]!=INF) else -1)
resolve()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter, defaultdict
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
import queue
import bisect
MOD = 10**9 + 7
from logging import getLogger, StreamHandler, DEBUG, WARNING
logger = getLogger(__name__)
handler = StreamHandler()
handler.setLevel(DEBUG)
logger.setLevel(DEBUG)


logger.addHandler(handler)
def main():
    INF = 10 ** 7
    n, m = getList()
    kempa = [[] for i in range(3 * n)]
    costs = [INF for i in range(3 * n)]
    for _ in range(m):
        u, v = getList()
        kempa[3 * u - 3].append(3 * v - 2)
        kempa[3 * u - 2].append(3 * v - 1)
        kempa[3 * u - 1].append(3 * v - 3)

    
    s, t = getList()
    deq = deque()
    deq.append(3 * s - 3)
    costs[3 * s - 3] = 0
    while(deq):
        tmp = deq.popleft()
        tcost = costs[tmp]
        for nxt in kempa[tmp]:
            if costs[nxt] > tcost + 1:
                deq.append(nxt)
                costs[nxt] = tcost + 1
    
    
    if costs[t * 3 - 3] == INF:
        print(-1)
    else:
        print(costs[t * 3 - 3] // 3)

if __name__ == "__main__":
    main()

Solution (Python):
import heapq
from collections import deque

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

dic = {}

for i in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []

    dic[u].append(v)


far = [[float("inf")] * 3 for i in range(N)]
nend = [ [True] * 3 for i in range(N) ]

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

q = deque([])
q.append([0,S])

while len(q) > 0:

    now = q.popleft()

    nd = now[0]
    np = now[1]
    nend[np][nd % 3] = False

    far[np][nd % 3] = min(far[np][nd % 3],nd)

    if np in dic:
        for i in dic[np]:

            if nend[i][(nd + 1) % 3] and far[i][(nd+1)%3] > far[np][nd%3] + 1:
                q.append([nd + 1 , i])
                nend[i][(nd+1)%3] = False

if far[T][0] == float("inf"):
    print (-1)
else:
    print (far[T][0] // 3)

Solution (Python):
from heapq import heappush, heappop
inf = float('inf')
mod = 10**9 + 7



class Dijkstra:
    def __init__(self, to:list, start:int):
        self.N = len(to)
        self.to = [s[:] for s in to]
        self.start = start
        self.dist = [inf] * self.N
        self.dist[start] = 0
        
        self.cnt = [0] * self.N
        self.cnt[start] = 1
        self.pq = [(self.dist[start], start)]

    
    def update(self) -> None:
        while self.pq:
            _, v = heappop(self.pq)
            for nv, w in self.to[v]:
                if self.dist[nv] > self.dist[v] + w:
                    self.dist[nv] = self.dist[v] + w
                    heappush(self.pq, (self.dist[nv], nv))
                if self.dist[nv] == self.dist[v] + w:
                    self.cnt[nv] += self.cnt[v]
                    self.cnt[nv] %= mod

N, M = map(int,input().split())
to = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int,input().split())
    u -= 1; v -= 1
    for i in range(3):
        nu = 3*u + i
        nv = 3*v + (i + 1) % 3
        to[nu].append((nv, 1))
S, T = map(int,input().split())
S -= 1; T -= 1

DI = Dijkstra(to, 3*S)
DI.update()

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

Solution (Python):
import sys
INF = 10 ** 9
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = [s]
flg = False
already = set()
dist = [INF for i in range(3 * n)]
dist[s] = 0
while que:
    cur= que[0]
    que.pop(0)
    for i in graph[cur]:
        if i not in already:
            if i == t:
                res = dist[cur] + 1
                que.clear()
                flg = True
                break
            que.append(i)
            dist[i] = dist[cur] + 1
            already.add(i)
if not flg:
    res = -1
else:
    res //= 3

print(res)

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

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

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

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, n: int, start: int, INF: int = float('inf')) -> list:
    
    dist = [INF] * n
    num = [0] * n

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        _, v_from = heappop(heap)
        for v_to in graph[v_from]:
            dist_cand = dist[v_from] + 1
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist
    


INF = 10**10
dist = dijkstra(graph1, n * 3, s, INF=INF)
if dist[t] == INF:
    print(-1)
else:
    print(dist[t] // 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, n: int, start: int, INF: int = float('inf')) -> list:
    
    dist = [INF] * n
    num = [0] * n

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        _, v_from = heappop(heap)
        for v_to in graph[v_from]:
            dist_cand = dist[v_from] + 1
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    return dist
    


INF = 10**10
dist = dijkstra(graph1, n * 3, s, INF=INF)
if dist[t] == INF:
    print(-1)
else:
    print(dist[t] // 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, n: int, start: int, INF: int = float('inf')) -> list:
    
    dist = [INF] * n
    num = [0] * n

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        _, v_from = heappop(heap)
        for v_to in graph[v_from]:
            dist_cand = dist[v_from] + 1
            if dist_cand < dist[v_to]:
                dist[v_to] = dist_cand
                heappush(heap, (dist[v_to], v_to))
    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 sys

sys.setrecursionlimit(4100000)

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

already_reach = [-1]*(N+1)
already_reach_1st = [-1]*(N+1)
already_reach_2nd = [-1]*(N+1)
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split(' '))
    graph[u].append(v)
S,T = map(int,input().split(' '))

next_list = []
def search(S_list,current_count=0):
    next_list = []
    for s in S_list:
        for i1 in graph[s]:
            
            if already_reach_1st[i1] != -1:
                continue
            already_reach_1st[i1] = 0
            for i2 in graph[i1]:
                
                if already_reach_2nd[i2] != -1:
                    continue
                already_reach_2nd[i2] = 0
                for i3 in graph[i2]:
                    if already_reach[i3] == -1: 
                        already_reach[i3] = current_count+1
                        next_list.append(i3)
    if len(next_list) > 0:
        search(next_list,current_count+1)
search([S])
print(already_reach[T])

Solution (Python):
n,m=map(int,input().split())
data=[[] for i in range(3*n+1)]
for i in range(m):
    u,v=map(int,input().split())
    data[u].append(v+n)
    data[u+n].append(v+2*n)
    data[u+2*n].append(v)
s,t=map(int,input().split())
inf=float("inf") 
flag=[inf]*(3*n+1)
flag[s]=0
que=[s]
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==inf:
                flag[v]=flag[u]+1
                h.append(v)
    que=h
if flag[t]==inf:
    print(-1)
else:
    print(flag[t]//3)

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


n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    _from, to = map(int, input().split())
    edges[_from-1].append(to-1)

start, goal = map(int, input().split())

todo = deque([])
seen = [[False] * n for i in range(3)]
seen[0][start-1] = True
for to in edges[start-1]:
    dim = 1
    dist = 1
    todo.append([to, dim, dist])

while todo:
    node, dim, dist = todo.popleft()
    if seen[dim][node]:
        continue
    seen[dim][node] = True
    dim += 1
    if dim == 3:
        dim = 0
    for to in edges[node]:
        if seen[dim][to]:
            continue
        todo.append([to, dim, dist+1])
        if to == goal-1 and dim == 0:
            print((dist+1)//3)
            exit()

print(-1)

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


n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    _from, to = map(int, input().split())
    edges[_from-1].append(to-1)

start, goal = map(int, input().split())

todo = deque([])
seen = [[False] * n for i in range(3)]
seen[0][start-1] = True
for to in edges[start-1]:
    dim = 1
    dist = 1
    todo.append([to, dim, dist])

while todo:
    node, dim, dist = todo.popleft()
    if seen[dim][node]:
        continue
    seen[dim][node] = True
    dim += 1
    if dim == 3:
        dim = 0
    for to in edges[node]:
        if seen[dim][to]:
            continue
        todo.append([to, dim, dist+1])
        if to == goal-1 and dim == 0:
            print((dist+1)//3)
            exit()

print(-1)

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
G = [[] for _ in range(n)]
for x, y in LIR(m):
    G[x - 1] += [y - 1]

dist = [[INF] * n for _ in range(3)]
s, t = LI()
dist[0][s - 1] = 0
dq = deque([(0, s - 1)])
while dq:
    cost, u = dq.popleft()
    for v in G[u]:
        if cost + 1 < dist[(cost + 1) % 3][v]:
            dist[(cost + 1) % 3][v] = cost + 1
            dq += [(cost + 1, v)]


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