Problem:
 Score : 500 points    Problem Statement Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G . G consists of N vertices numbered 1 to N , and M edges. The i -th edge points from Vertex u_i to Vertex v_i .  First, Ken stands on Vertex S . He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.  Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T . Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.      Constraints  2 \leq N \leq 10^5  0 \leq M \leq \min(10^5, N (N-1))  1 \leq u_i, v_i \leq N(1 \leq i \leq M)  u_i \neq v_i (1 \leq i \leq M)  If i \neq j , (u_i, v_i) \neq (u_j, v_j) .  1 \leq S, T \leq N  S \neq T         Input Input is given from Standard Input in the following format:  N  M  u_1  v_1  :  u_M  v_M  S  T       Output If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1 .
If he can, print the minimum number of ken-ken-pa needed to reach vertex T .        Sample Input 1 4 4
1 2
2 3
3 4
4 1
1 3      Sample Output 1 2  Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.       Sample Input 2 3 3
1 2
2 3
3 1
1 2      Sample Output 2 -1  Any number of ken-ken-pa will bring Ken back to Vertex 1 , so he cannot reach Vertex 2 , though he can pass through it in the middle of a ken-ken-pa.       Sample Input 3 2 0
1 2      Sample Output 3 -1  Vertex S and Vertex T may be disconnected.       Sample Input 4 6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6      Sample Output 4 2

Solution (Python):
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
o=inputs()
s,T=map(int,o.pop().split())
for i in o:
    _,__=map(int,i.split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=set()
seen.add(3*s)
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if t not  in seen:
            dq.append((t,c+1))
            seen.add(t)
print("-1")

Solution (Python):
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
o=inputs()
s,T=map(int,o.pop().split())
for i in o:
    _,__=map(int,i.split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=[0]*(3*n+3)
seen[3*s]=1
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if seen[t]==0:
            dq.append((t,c+1))
            seen[t]=1
print("-1")

Solution (Python):
from collections import deque

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

graph = [[] for _ 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

q = deque([(S, 0)])
visited = [[0]*3 for _ in range(N)]
visited[S][0] = 1

flg = True
res = -1
while q and flg:
    v = q.popleft()
    for n_v in graph[v[0]]:
        n_dist = v[1] + 1
        if n_v == T and n_dist % 3 == 0:
            res = n_dist // 3
            flg = False
            break
        if not visited[n_v][n_dist % 3]:
            visited[n_v][n_dist % 3] = 1
            q.append((n_v, n_dist))

print(res)

Solution (Python):
from collections import deque


def nearlist(N):  
    NEAR = [set() for _ in range(3 * N)]
    for a, b in uv:
        a, b = 3 * (a - 1), 3 * (b - 1)
        NEAR[a].add(b + 1)
        NEAR[a + 1].add(b + 2)
        NEAR[a + 2].add(b)
    return NEAR


def bfs(S, T, N):  
    S, T = 3 * (S - 1), 3 * (T - 1)
    dist, flag = [-3] * (3 * N), [0] * (3 * N)  
    dist[S], flag[S] = 0, 1
    que = deque([S])

    while que:
        q = que.popleft()
        for i in near[q]:  
            if flag[i]:  
                continue
            dist[i], flag[i] = dist[q] + 1, 1
            que.append(i)
    return dist[T] // 3


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


near = nearlist(n)
print(bfs(s, t, n))

Solution (Python):
from collections import deque


def nearlist(N):  
    NEAR = [set() for _ in range(3 * N)]
    for a, b in uv:
        a, b = 3 * (a - 1), 3 * (b - 1)
        NEAR[a].add(b + 1)
        NEAR[a + 1].add(b + 2)
        NEAR[a + 2].add(b)
    return NEAR


def bfs(S, T, N):  
    S, T = 3 * (S - 1), 3 * (T - 1)
    dist, flag = [-3] * (3 * N), [0] * (3 * N)  
    dist[S], flag[S], que = 0, 1, deque([S])

    while que:
        q = que.popleft()
        for i in near[q]:  
            if flag[i]:  
                continue
            dist[i] = dist[q] + 1
            flag[i] = 1
            que.append(i)
    return dist[T] // 3


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


near = nearlist(n)
ans = bfs(s, t, n)
print(ans)

Solution (Python):
from collections import deque


def nearlist(N, LIST):  
    NEAR = [set() for _ in range(3 * N)]
    for a, b in LIST:
        a, b = 3 * (a - 1), 3 * (b - 1)
        NEAR[a].add(b + 1)
        NEAR[a + 1].add(b + 2)
        NEAR[a + 2].add(b)
    return NEAR


def bfs(S, T, N):  
    S, T = 3 * (S - 1), 3 * (T - 1)
    dist, flag = [-3] * (3 * N), [0] * (3 * N)  
    dist[S], flag[S], que = 0, 1, deque([S])

    while que:
        q = que.popleft()
        for i in near[q]:  
            if flag[i]:  
                continue
            dist[i] = dist[q] + 1
            flag[i] = 1
            que.append(i)
    return dist[T] // 3


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


near = nearlist(n, uv)
ans = bfs(s, t, n)
print(ans)

Solution (Python):
from collections import deque


def nearlist(N, LIST):  
    NEAR = [set() for _ in range(3 * N)]
    for a, b in LIST:
        a, b = 3 * (a - 1), 3 * (b - 1)
        NEAR[a].add(b + 1)
        NEAR[a + 1].add(b + 2)
        NEAR[a + 2].add(b)
    return NEAR


def bfs(S, T, N):  
    S, T = 3 * (S - 1), 3 * (T - 1)
    dist = [-3] * (3 * N)  
    dist[S] = 0
    que, flag = deque([S]), set([S])

    while que:
        q = que.popleft()
        for i in near[q]:  
            if i in flag:  
                continue
            dist[i] = dist[q] + 1
            que.append(i), flag.add(i)
    return dist[T] // 3


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


near = nearlist(n, uv)
ans = bfs(s, t, n)
print(ans)

Solution (Python):
from collections import deque

def main():

  n,m=map(int,input().split())
  INF=10**9
  d=[[INF]*3 for i in range(n)]
  to=[[] for i in range(n)]
  for i in range(m):
    u,v=map(lambda x:int(x)-1,input().split())
    to[u].append(v)
  s,t=map(lambda x:int(x)-1,input().split())

  
  
  d[s][0]=0
  cnt=0
  q=deque([(s,cnt)])
  while q:
    u,c=q.popleft()
    for v in to[u]:
      nc=(c+1)%3
      if d[v][nc]!=INF: continue;
      d[v][nc]=d[u][c]+1
      q.append((v,nc))
      
  
  ans=d[t][0]
  print(ans//3 if ans!=INF else -1)

  
if __name__=='__main__':
  main()

Solution (Python):
from collections import deque
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v)

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

from_s = [[-1]*3 for _ in range(n)]
d_s = deque()
d_s.append((s, 0))
from_s[s][0] = 0
while d_s:
    p, count = d_s.popleft()
    next_count = (count + 1) % 3
    for c in edges[p]:
        if from_s[c][next_count] != -1:
            continue
        from_s[c][next_count] = from_s[p][count] + 1
        d_s.append((c, next_count))
if from_s[t] == -1:
    print(-1)
else:
    print(from_s[t][0]//3)

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

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

from collections import deque

q = deque([(S, 0)])
v = [[-1] * 3 for i in range(N+1)]

while q:
    a, t = q.popleft()
    b = t % 3
    if v[a][b] != -1:
        continue
    v[a][b] = t
    t += 1
    for x in to[a]:
        q.append((x, t))
    


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

Solution (Python):

from collections import deque
import sys
def main(N, M, G, S, T):
    INF = 10**10
    q = deque([S])
    dist = [INF] * (3 * N)
    dist[S] = 0
    while q:
        v = q.popleft()
        for to in G[v]:
            if dist[to] < INF: continue
            dist[to] = dist[v] + 1
            q.append(to)
    print(dist[T] // 3 if dist[T] < INF else -1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N * 3)]
    for _ in range(M):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1
        G[x].append(y + N)
        G[x + N].append(y + N + N)
        G[x + N + N].append(y)
    S, T = map(lambda x: int(x) - 1, input().split())
    main(N, M, G, S, T)

Solution (Python):

from heapq import heappush, heappop
import sys
def main(N, M, G, S, T):
    INF = 10**10
    dp = [[INF for _ in range(N)] for __ in range(3)]
    dp[0][S] = 0
    q = [(0, S)]
    while q:
        d, v = heappop(q)
        for to in G[v]:
            if d + 1 >= dp[(d + 1) % 3][to]: continue
            dp[(d + 1) % 3][to] = d + 1
            heappush(q, (d + 1, to))
    print(dp[0][T] // 3 if dp[0][T] < INF else -1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1
        G[x].append(y)
    S, T = map(lambda x: int(x) - 1, input().split())
    main(N, M, G, S, T)

Solution (Python):

from heapq import heappush, heappop
import sys
def main(N, M, G, S, T):
    INF = 10**10
    dp = [[INF for _ in range(N)] for __ in range(3)]
    dp[0][S] = 0
    q = [(0, S)]
    while q:
        d, v = heappop(q)
        for to in G[v]:
            if d + 1 >= dp[(d + 1) % 3][to]: continue
            dp[(d + 1) % 3][to] = d + 1
            q.append((d + 1, to))
    print(dp[0][T] // 3 if dp[0][T] < INF else -1)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        x, y = x - 1, y - 1
        G[x].append(y)
    S, T = map(lambda x: int(x) - 1, input().split())
    main(N, M, G, S, T)

Solution (Python):

from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]

for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
S=(S,0)
T=(T,0)

q=deque()
q.append(S)
F=set()
res=-1
while q:
    node,r=q.popleft()
    if (node,r%3) in F:
        continue
    if (node,r%3) == T:
        res=r//3
        break
    F.add((node,r%3))
    for next_node in G[node]:
        if (next_node,(r+1)%3) in F:
            continue
        q.append((next_node,r+1))
print(res)

Solution (Python):
import sys
import heapq
import math

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

g = [[] for _ in range(3*N)]
for a, b in uv:
    g[a-1].append(b-1+N)
    g[a-1+N].append(b-1+2*N)
    g[a - 1 + 2 * N].append(b - 1)


hq = [(0, S-1)]
costs = [math.inf] * 3 * N
while len(hq) > 0:
    c, u = heapq.heappop(hq)
    if u == T - 1:
        print(c // 3)
        sys.exit()
    costs[u] = c
    for v in g[u]:
        if costs[v] > c+1:
            heapq.heappush(hq, (c + 1, v))
        costs[v] = min(costs[v], c+1)

print(-1)

Solution (Python):


import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M = map(int, readline().split())
graph = [[] for _ in range(3*N+1)]
for _ in range(M):
    x,y = map(int,readline().split())
    graph[x].append(y+N)
    graph[x+N].append(y+2*N)
    graph[x+2*N].append(y)
S,G = map(int,readline().split())
dist = [-1]*(N*3+1)
dist[S] = 0
root = S
q = deque([root])

def bfs(q):
    while q:
        x = q.popleft()
        for nx in graph[x]:
            if dist[nx] != -1:
                continue
            dist[nx] = dist[x] + 1
            q.append(nx)
            
bfs(q)
if dist[G] == -1:
    print(-1)
else:
    print(dist[G] // 3)

Solution (Python):


import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M = map(int, readline().split())
graph = [[[] for _ in range(3)] for _ in range(N+1)]
for i in range(M):
    x,y = map(int,readline().split())
    graph[x][0].append((y,1))
    graph[x][1].append((y,2))
    graph[x][2].append((y,0))
S,G = map(int,readline().split())
dist = [[-1]*3 for _ in range(N+1)]
dist[S][0] = 0
root = (S,0)

q = deque([root])
def bfs(q):
    while q:
        x,t = q.popleft()
        for nx,nt in graph[x][t]:
            if dist[nx][nt] != -1:
                continue
            dist[nx][nt] = dist[x][t] + 1
            q.append((nx,nt))
            
bfs(q)
if dist[G][0] == -1:
    print(-1)
else:
    print(dist[G][0] // 3)

Solution (Python):
from collections import deque
INF = float("inf")

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






G = [[] for _ in range(3 * N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = 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, T = S - 1, T - 1

ans = [INF] * (3 * N)
ans[S] = 0
dq = deque([S])


while dq:
    now = dq.popleft()
    for next in G[now]:
        if ans[next] != INF:
            continue
        ans[next] = ans[now] + 1
        dq.append(next)


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

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


INF = 10**18


def bfs(N, v0, goal, edge):

    dp = [[-1 for _ in range(3)] for _ in range(N)]
    dp[v0][0] = 0
    q = deque()
    q.append((v0, 0))

    while q:
        v, cnt = q.popleft()

        if cnt == 2:
            nx_cnt = 0
        else:
            nx_cnt = cnt + 1

        for nv in edge[v]:
            if dp[nv][nx_cnt] == -1:
                q.append((nv, nx_cnt))
                if cnt == 0:
                    dp[nv][nx_cnt] = dp[v][cnt] + 1
                else:
                    dp[nv][nx_cnt] = dp[v][cnt]
        

    return dp[goal][0]


def main():

    N, M = in_nn()
    edge = [[] for _ in range(N)]

    for i in range(M):
        u, v = in_nn()
        u, v = u - 1, v - 1
        edge[u].append(v)

    S, T = in_nn()
    S, T = S - 1, T - 1
    ans = bfs(N, S, T, edge)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


import queue

N, M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
adj = [[] for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())    
    u -= 1
    v -= 1
    adj[u].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1

dist = [[INF,INF,INF] for _ in range(N+1)]
 
q = queue.Queue()
q.put((S, 0))
dist[S][0] = 0
while not q.empty():
    u, l = q.get()
    for v in adj[u]:
        nl = (l + 1) % 3
        if dist[v][nl] != INF:
            continue
        dist[v][nl] = dist[u][l] + 1
        q.put((v, nl))
d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


import queue

N, M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
adj = [[] for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())    
    u -= 1
    v -= 1
    adj[u].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1

dist = [[INF,INF,INF] for _ in range(N+1)]
 
d = 0
q = [S]
while q:
  d += 1
  r = d % 3
  qq = []
  for u in q:
    for v in adj[u]:
      if dist[v][r] == INF:
        dist[v][r] = d
        qq.append(v)
  q = qq
 
d = dist[T][0]
answer = -1 if d == INF else d // 3
print(answer)

Solution (Python):
from collections import deque
n, m = map(int, input().split())

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

dist = [[-3] * 3 for _ in range(n+1)]
dist[s][0] = 0

q = deque([(s, 0)])

while q:
    now, c = q.popleft()
    ne = (c+1) % 3
    for node in graph[now]:
        if dist[node][ne] != -3:
            continue
        dist[node][ne] = dist[now][c] + 1
        q.append((node, ne))

print(dist[t][0] // 3)

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
n,m = ma()
G = [[]for i in range(3*n)]
for i in range(m):
    u,v = ma();u-=1;v-=1
    G[3*u].append(3*v+1)
    G[3*u+1].append(3*v+2)
    G[3*u+2].append(3*v)
s,t = ma()
s=(s-1)*3
t=(t-1)*3
visited=[False]*(3*n)
INF=10**9
dist = [INF]*(3*n)
que = collections.deque()
que.append(s)
visited[s]=True
dist[s]=0
while que:
    prev = que.popleft()
    for nex in G[prev]:
        if not visited[nex]:
            visited[nex]=True
            dist[nex]=dist[prev]+1
            que.append(nex)
if dist[t]==INF:
    print(-1)
else:
    print(dist[t]//3)

Solution (Python):
"""
これは、3の倍数かつ最小ステップでTにたどりつけ、という問題。
拡張ダイクストラを使えばよい。
"""
from collections import deque
N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split())
    edges[u].append(v)
visited = set()
S,T = map(int,input().split())
que = deque([(S,0)])
while que:
    cur,step = que.popleft()
    rest = step%3
    if cur == T and rest == 0:
        print(step//3)
        exit()
    if (cur,rest) in visited:
        continue
    else:
        visited.add((cur,rest))
        for nx in edges[cur]:
            que.append((nx,step+1))
print(-1)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
w = [set() for _ in range(n + 1)]
for _ in range(m):
  u, v = map(int, input().split())
  w[u].add(v)
s, t = map(int, input().split())

memo = [[-1,-1,-1] for _ in range(n+1)]

d = deque()
d.append((s,0,0))
while d:
    i,q,r = d.popleft()
    for nx in w[i]:
        if nx ==t and r ==2:
            print((q+1)//3)
            exit()
        if memo[nx][(r+1)%3] == -1:
            memo[nx][(r+1)%3] = q+1
            d.append((nx,q+1,(r+1)%3))
print(-1)

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

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

seen = [[False] * 3 for i in range(N)]

while q:
  v,cost,step = q.popleft()
  if seen[v][step]:
    continue
  seen[v][step] = True
  if step == 0:
    if v == T:
      print(cost)
      break
    cost += 1
    step = 3
  for u in graph[v]:
    q.append([u, cost, step - 1])
else:
  print(-1)

Solution (Python):
import collections

n, m = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
flag = [False for i in range(n + 1)]
s, t = map(int, input().split())

queue = collections.deque([s])
count = 0
while True:
    for i in range(2):
        temp = set()
        while queue:
            test = queue.popleft()
            for j in graph[test]:
                if j not in temp:
                    temp.add(j)
        for j in temp:
            queue.append(j)
    temp = set()
    while queue:
        test = queue.popleft()
        for i in graph[test]:
            if flag[i] == True:
                continue
            else:
                if i not in temp:
                    temp.add(i)
                    flag[i] = True
    count += 1
    if flag[t] == True:
        print(count)
        break
    if len(temp) == 0:
        print(-1)
        break
    for i in temp:
        queue.append(i)

Solution (Python):





from collections import deque

n, m = map(int, input().split())
g = [set([]) for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].add(b)

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


q = deque()
level = [[-1]*n for i in range(3)]
q.append((s, 0))
level[0][s] = 0
while len(q)>0:
    cur, lvl = q.popleft()
    nxtl = lvl + 1
    nxthp = nxtl%3
    for i in g[cur]:
        if level[nxthp][i]==-1:
            
            level[nxthp][i] = nxtl
            q.append((i, nxtl))
print(level[0][t]//3)

Solution (Python):





from collections import deque

n, m = map(int, input().split())
g = [set([]) for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].add(b)

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


q = deque()
level = [[-1]*n for i in range(3)]
q.append((s, 0))
level[0][s] = 0
while len(q)>0:
    cur, hp = q.popleft()
    lvl = level[hp][cur]
    for i in g[cur]:
        if level[(hp+1)%3][i]==-1:
            
            level[(hp+1)%3][i] = lvl + 1
            q.append((i, (hp+1)%3))
print(level[0][t]//3)

Solution (Python):
from collections import deque
n, m = map(int, input().split())
w = [set() for _ in range(n + 1)]
for _ in range(m):
  u, v = map(int, input().split())
  w[u].add(v)
s, t = map(int, input().split())
l = [[-1, -1, -1] for _ in range(n + 1)] 

d = deque()
d.append((s, 0, 0))
while d: 
  i, q, r = d.popleft() 
  for _w in w[i]:
    if _w == t and r == 2: 
      print((q + 1) // 3)
      exit()
    if l[_w][(r + 1) % 3] == -1: 
      l[_w][(r + 1) % 3] = q + 1
      d.append((_w, q + 1, (r + 1) % 3))
print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
UV = [tuple(map(int,input().split())) for i in range(M)]
S,T = map(int,input().split())
S,T = S-1,T-1

es = [[] for _ in range(N*3)]
for u,v in UV:
    u,v = u-1,v-1
    es[u].append(v+N)
    es[u+N].append(v+N+N)
    es[u+N+N].append(v)

from collections import deque
q = deque([S])
INF = float('inf')
dist = [INF] * (N*3)
dist[S] = 0
while q:
    v = q.popleft()
    for to in es[v]:
        if dist[to] <= dist[v]+1: continue
        dist[to] = dist[v]+1
        q.append(to)
        if to==T:
            print(dist[to] // 3)
            exit()
print(-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readlines
from collections import deque
def main():
    lines = input()
    n, m = list(map(int, lines[0].split()))
    
    edges=[[] for i in range(n)]
    for i in range(m):
        u,v=list(map(int,lines[i+1].split()))
        edges[u-1].append(v-1)

    s,t=list(map(int,lines[m+1].split()))
    inf=100000000000
    score=[[inf]*3 for i in range(n)]
    now=deque()
    now.append((s-1, 0))
    score[s-1][0]=0
    def bfs():
        if now:
            u, mod = now.popleft()
            time = score[u][mod]
            mod = (mod+1)%3
            for v in edges[u]:
                if score[v][mod] == inf:
                    score[v][mod] = time+1
                    now.append((v, mod))

            bfs()

    bfs()
    ans = score[t-1][0]
    if ans == inf:
        print(-1)
    else:
        print(score[t-1][0]//3)
main()

Solution (Python):
import sys
from collections import deque

input = sys.stdin.buffer.readline
int1 = lambda x: int(x) - 1

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

S, T = map(int1, input().split())
S *= 3
T *= 3


d = deque([S])
distance = [0] * (3 * N)
while d:
    v = d.popleft()
    dist_v = distance[v]
    if v == T:
        print(dist_v // 3)
        exit()
    for x in G[v]:
        if not distance[x]:
            d.append(x)
            distance[x] = dist_v + 1
print(-1)

Solution (Python):
from collections import*
n,m=map(int,input().split())
e=[[]for _ in range(3*(n+1))]
d=[-3]*(3*(n+1))
for _ in range(m):
  a,b=map(int,input().split())
  e[a]+=[b+n]
  e[a+n]+=[b+2*n]
  e[a+2*n]+=[b]
s,t=map(int,input().split())
q=deque([s])
d[s]=0
while q:
  now=q.popleft()
  for to in e[now]:
    if d[to]!=-3:continue
    d[to]=d[now]+1
    q.append(to)
print(d[t]//3)

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_d(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


def main():
    N, M = NMI()
    edges = [NLI() for _ in range(M)]
    S, T = NMI()

    tree = [[] for _ in range(3*N+1)]
    for e in edges:
        tree[e[0]].append(e[1]+N)
        tree[e[0]+N].append(e[1]+2*N)
        tree[e[0]+2*N].append(e[1])

    stack = deque()
    stack.append(S)
    seen = [-1] * (3*N+1)
    seen[S] = 0
    while stack:
        now = stack.popleft()
        now_step = seen[now]
        for goto in tree[now]:
            if seen[goto] >= 0:
                continue

            stack.append(goto)
            seen[goto] = now_step + 1

    print(seen[T]//3)



if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n, m = map(int, input().split())
edges = [[] for i in range(3*n)]
for i in range(m):
    u,v = map(int, input().split())
    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 -= 1
t -= 1
INF = 1<<50
dists = [INF] * (3*n)

q = deque([])
q.append(s)
dists[s] = 0

while len(q)>0:
    v = q.popleft()
    for u in edges[v]:
        if dists[u] != INF: continue
        q.append(u)
        dists[u] = dists[v] + 1

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

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

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

D = [[-1]*3 for _ in range(N)]
D[S][0] = 0
q = [(S, 0)]
while q:
    qq = []
    for p, d in q:
        for np in graph[p]:
            nd = (d+1)%3
            if D[np][nd] == -1:
                D[np][nd] = D[p][d] + 1
                qq.append((np, nd))
    q = qq

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

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    
    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.inf=10**20
            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 +=2

        def shortest_path(self,s):
            
            que = [] 
            d = [self.inf] * 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 

                        
                        

                        heapq.heappush(que,(d[e.to],e.to)) 

            """
            path = []
            pos = g 
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                
                pos = prev[pos]
            path.reverse()
            

            return d
    
    mod=10**9+7
    N,M=MI()
    djk=Dijkstra(3*N)
    for _ in range(M):
        u,v=MI()
        u-=1
        v-=1
        djk.add(u,v+N,1)
        djk.add(u+N,v+2*N,1)
        djk.add(u+2*N,v,1)
    S,T=MI()
    S-=1
    T-=1
    D=djk.shortest_path(S)
    ans=D[T] //3
    
    if ans>10**7:
        ans=-1
        
    print(ans)
        
    


main()

Solution (Python):
from collections import deque
N,M = map(int,input().split())
dis = [[-1,-1,-1] for _ in range(N+1)]
Tree = [[] for _ in range(N+1)]
for i in range(M):
    ui,vi = map(int,input().split())
    Tree[ui].append(vi)
S,T = map(int,input().split())
d = deque([(S,0)])
dis[S][0] = 0
while d:
    x,z = d.popleft()
    for y in Tree[x]:
        if dis[y][(z+1)%3] == -1:
            dis[y][(z+1)%3] = dis[x][z] + 1
            d.append((y,(z+1)%3))
if dis[T][0] == -1:
    print(-1)
else:
    print(dis[T][0]//3)