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 deque
N, M = map(int, input().split())

X = [[] for i in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    X[x-1].append(y-1)

S, T = map(int, input().split())
S -= 1
T -= 1
Q0 = deque([S])
Q1 = deque([])
Q2 = deque([])
D0 = [999999] * N
D1 = [999999] * N
D2 = [999999] * N

D0[S] = 0
while Q0 or Q1 or Q2:
    while Q0:
        x = Q0.popleft()
        for c in X[x]:
            if D1[c] == 999999:
                D1[c] = D0[x]+1
                Q1.append(c)
    while Q1:
        x = Q1.popleft()
        for c in X[x]:
            if D2[c] == 999999:
                D2[c] = D1[x]+1
                Q2.append(c)
    while Q2:
        x = Q2.popleft()
        for c in X[x]:
            if D0[c] == 999999:
                D0[c] = D2[x]+1
                Q0.append(c)
print(-1 if D0[T] == 999999 else D0[T]//3)

Solution (Python):
import sys
from collections import deque


input = sys.stdin.readline
n, m = map(int, input().split())
info = tuple(map(int, input().split()) for i in range(m))
s, t = map(int, input().split())

graph = [[] for i in range(n)]
for i, j in info:
    graph[i-1].append(j-1)

q = deque()
q.append((s - 1, 0))
INF = 10 ** 10
visited = [10 ** 10] * n
visited_1 = [10 ** 10] * n
visited_2 = [10 ** 10] * n
visited[s - 1] = 0
while q:
    pos, times = q.popleft()
    for i in graph[pos]:
        if (times + 1) % 3 == 1 and times + 1 < visited_1[i]:
            visited_1[i] = times + 1
            q.append((i, times + 1))

        elif (times + 1) % 3 == 2 and times + 1 < visited_2[i]:
            visited_2[i] = times + 1
            q.append((i, times + 1))
            
        elif (times + 1) % 3 == 0 and times + 1 < visited[i]:
            visited[i] = times + 1
            q.append((i, times + 1))

if visited[t - 1] == 10 ** 10:
    print(-1)
else:
    print(visited[t-1]//3)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    g[u - 1].append(v - 1)
s, t = map(int, input().split())
s -= 1
t -= 1
done = [[-1] * n for _ in range(3)]
done[2][s] = 0
que = deque([s])
while que:
    d = que.popleft()
    for node1 in g[d]:
        if done[0][node1] != -1:
            continue
        done[0][node1] = 1
        for node2 in g[node1]:
            if done[1][node2] != -1:
                continue
            done[1][node2] = 1
            for node3 in g[node2]:
                if done[2][node3] != -1:
                    continue
                que.append(node3)
                done[2][node3] = done[2][d] + 1
print(done[2][t])

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N, M = map( int, input().split())
    E = [[] for _ in range(N)]
    for _ 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
    d = deque([s])
    V = [10**9]*(N*3)
    V[s] = 0
    while d:
        u = d.popleft()
        r, v = u//N,u%N
        c = V[u]
        if r == 0 and v == t:
            print(c//3)
            return
        r = (r+1)%3
        for z in E[v]:
            if c+1 < V[r*N+z]:
                V[r*N+z] = c+1
                d.append(r*N+z)
    print(-1)
if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, UV, S, T):
    G = defaultdict(list)
    for u, v in UV:
        G[u-1].append(v-1)
    
    S -= 1
    T -= 1
    
    d = [defaultdict(lambda: sys.maxsize) for _ in range(N)]
    q = deque([(S, 0, 0)])
    while q:
        u, md, cd = q.popleft()
        if md not in d[u]:
            d[u][md] = min(d[u][md], cd)
            nd = (md+1) % 3
            for v in G[u]:
                q.append((v, nd, cd+1))

    if 0 in d[T]:
        return math.ceil(d[T][0] / 3)
    return -1


def main():
    N, M = read_int_n()
    UV = [read_int_n() for _ in range(M)]
    S, T = read_int_n()
    print(slv(N, M, UV, S, T))


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    s = S()
    d = defaultdict(int)
    for i in s:
        d[i] += 1
    for i in d.keys():
        if d[i] != 2:
            print("No")
            quit()
    print("Yes")
    return


def B():
    n = I()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        k = p[i-1:i+2]
        k.sort()
        if k[1] == p[i]:
            ans += 1
    print(ans)
    return


def C():
    n = I()
    d = LI()
    d.sort()
    print(d[n//2]-d[n//2-1])
    return


def D():
    n,k = LI()
    fact = [1]*100001
    for i in range(1,100001):
        fact[i] = fact[i-1]*i%mod
    inv = [1]*100001
    inv[-1] = pow(fact[-1],mod-2,mod)
    for i in range(1,100001)[::-1]:
        inv[i-1] = inv[i]*i%mod

    for i in range(1,k+1):
        if n-k+1 < i:
            print(0)
        else:
            ans = fact[n-k+1]*inv[i]*inv[n-k+1-i]%mod
            ans *= fact[k-1]*inv[k-i]*inv[i-1]%mod
            ans %= mod
            print(ans)
    return


def E():
    ma = 100000000
    def dijkstra(s):
        d = defaultdict(lambda : ma)
        q = [(0,s,0)]
        d[(s,0)] = 0
        while q:
            dx,x,t = heappop(q)
            t = (t+1)%3
            k = t == 1
            for y in v[x]:
                if dx+k < d[(y,t)]:
                    d[(y,t)] = dx+k
                    heappush(q,(d[(y,t)],y,t))
        res = d[(g,0)]
        if res == ma:
            res = -1
        return res

    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
    s,g = LI()
    s -= 1
    g -= 1
    print(dijkstra(s))
    return


def F():
    n = I()

    return



if __name__ == "__main__":
    E()

Solution (Python):



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

uv = [[int(i)-1 for i in input().split()] for _ in range(m)]
for u,v in uv: g[u].append(v)

s,t = [int(i)-1 for i in input().split()]




from collections import deque





memo = [[-3]*3 for _ in range(n)] 
q = deque()


q.append((s,0)) 
memo[s][0] = 0 



while q: 
    (v,d) = q.popleft() 
    
    for cv in g[v]:
        
        if memo[cv][(d+1)%3] >= 0: continue
        
        memo[cv][(d+1)%3] = d+1
        q.append((cv,d+1))
        
        
    

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

Solution (Python):
import sys
from queue import Queue

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, m = na()
g = []
for i in range(n):
    g.append([])
for i in range(m):
    u, v = na()
    g[u-1].append(v-1)

s, t = na()
s -= 1;
t -= 1

ds = [[9999999999] * n for i in range(3)]
ds[0][s] = 0

q = Queue()
q.put((0, s))
while not q.empty():
    r, cur = q.get_nowait()
    nr = (r+1) % 3
    for e in g[cur]:
        
        if ds[nr][e] > ds[r][cur] + 1:
            ds[nr][e] = ds[r][cur] + 1
            q.put((nr, e))
if ds[0][t] < 99999999:
    print(ds[0][t]//3)
else:
    print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    n,m = map(int,input().split())

    edge = [[] for i in range(n+1)]
    for i in range(m):
        u,v = map(int,input().split())
        edge[u].append(v)

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

    fi = [True]*(n+1)
    se = [True]*(n+1)
    th = [True]*(n+1)
    th[s] = False

    now = [s]
    tank = []
    cnt = 0

    while len(now) != 0:
        cnt += 1
        tank = []
        tank2 = []
        tank3 = []
        for e in now:
            for a in edge[e]:
                if fi[a]:
                    fi[a] = False
                    tank2.append(a)

        for e in tank2:

            for a in edge[e]:
                if se[a]:
                    se[a] = False
                    tank3.append(a)
        
        for e in tank3:
            for a in edge[e]:
                if th[a]:
                    th[a] = False
                    tank.append(a)
                if a == t:
                    print(cnt)
                    exit()

        now = tank
    print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    E[u].append(v)
Closed = [[False]*(N+1) for _ in range(3)]
S, T = map(int, input().split())
st = [(S, 0)]
Closed[0][S] = True
ans = 0
while len(st):
    st_new = []
    for v, n in st:
        if v==T and n==0:
            print(ans // 3)
            exit()
        n1 = (n+1)%3
        Cl = Closed[n1]
        for u in E[v]:
            if not Cl[u]:
                st_new.append((u, n1))
                Cl[u] = True
    st = st_new
    ans += 1

print(-1)

Solution (Python):

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

saki = [[] for i in range(n+1)]
for i in range(m):
    saki[A[i][0]].append(A[i][1])

F = [[-1,-1,-1] for i in range(n+1)]



def idou(x, y):
    
    if F[x][y%3] == -1:
        F[x][y%3] = y
        
        for item in saki[x]:
            
            if F[item][(y+1)%3] == -1:
                
                mada[(y+1)%3].append([item,y+1])
    

mada = [[] for i in range(3)]
a=0
b=0
c=0

idou(s,0)

while a<len(mada[0]) or b<len(mada[1]) or c<len(mada[2]):
    while a<len(mada[0]):
        
        idou(mada[0][a][0], mada[0][a][1])
        a += 1
    while b<len(mada[1]):
        
        idou(mada[1][b][0], mada[1][b][1])
        b += 1
    while c<len(mada[2]):
        
        idou(mada[2][c][0], mada[2][c][1])
        c += 1

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

Solution (Python):
from collections import deque
import sys
readline = sys.stdin.readline
N, M = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, readline().split())
    G[u-1].append(v-1)
S, T = map(int, readline().split())
S -= 1; T -= 1

INF = 10**9
U = [[INF]*N for i in range(3)]
U[0][S] = 0
que = deque([(S, 0)])
while que:
    v, t = que.popleft()
    u = (t+1) % 3
    d = U[t][v]
    if t == 2:
        d += 1
    Uu = U[u]
    for w in G[v]:
        if Uu[w] != INF:
            continue
        que.append((w, u))
        Uu[w] = d
print(U[0][T] if U[0][T] < INF else -1)

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

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

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))


def dijkstra(g, src, dst):
    import heapq

    min_cost = [[float('inf')] * 3 for _ in range(len(g))]

    node_heap = []
    heapq.heappush(node_heap, (0, 0, src))
    while node_heap:
        cost, hop, node = heapq.heappop(node_heap)
        if min_cost[node][hop] <= cost:
            continue
        min_cost[node][hop] = cost

        for _, d, c in g.edges(node):
            dc = min_cost[node][hop] + c
            dh = (hop + 1) % 3
            heapq.heappush(node_heap, (dc, dh, d))
    ret = min_cost[dst][0] // 3
    if isnan(ret):
        return -1
    return ret



def solve(N: int, M: int, u: "List[int]", v: "List[int]", S: int, T: int):
    es = [(cu - 1, cv - 1, 1) for cu, cv in zip(u, v)]
    g = DGraph(N, es)

    S = S - 1
    T = T - 1
    cost = dijkstra(g, S, T)
    return cost


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    u = [int()] * (M)  
    v = [int()] * (M)  
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  
    T = int(next(tokens))  
    result = solve(N, M, u, v, S, T)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import sys
readline = sys.stdin.readline
N, M = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, readline().split())
    G[u-1].append(v-1)
S, T = map(int, readline().split())
S -= 1; T -= 1

INF = 10**9
U = [[INF]*N for i in range(3)]
U[0][S] = 0
que = deque([(S, 0)])
while que:
    v, t = que.popleft()
    u = (t+1) % 3
    d = U[t][v]
    if t == 2:
        d += 1
    Uu = U[u]
    for w in G[v]:
        if Uu[w] != INF:
            continue
        que.append((w, u))
        Uu[w] = d
print(U[0][T] if U[0][T] < INF else -1)

Solution (Python):
from collections import deque
n,m =  map(int,input().split())
l = [list() for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    l[a].append(b)
s,t = map(int,input().split())

reach = [[-1,-1,-1] for _ in range(n+1)]
reach[s][0] = 0
bfs = deque()
bfs.append((s,0))
while bfs:
    cur,dis = bfs.popleft()
    for x in l[cur]:
        if reach[x][(dis+1)%3] < 0:
            bfs.append((x,dis+1))
            reach[x][(dis+1)%3] = dis+1
ans = reach[t][0]
if ans > 2:
  ans //= 3
print(ans)

Solution (Python):
import sys
from heapq import heappop, heappush

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
lines = sys.stdin.readlines()
for line in lines[:-1]:
    u, v = list(map(int, line.split()))
    u -= 1
    v -= 1
    links[u].add(v)
s, t = list(map(int, lines[-1].split()))
s -= 1
t -= 1

q = [(0, s)]
visited = set()
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 links[v]:
        new_key = (d, u)
        if new_key in visited:
            continue
        heappush(q, (c, u))

print(ans)