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 itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np

Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): 
    n,m = list(map(int,input().split()))
    graph = defaultdict(list)
    uv = [list(map(int,input().split())) for i in range(m)]
    u = [uv[i][0] for i in range(m)]
    v = [uv[i][1] for i in range(m)]
    for i in range(m):
        graph[u[i]].append(v[i]+n)
        graph[u[i]+n].append(v[i]+2*n)
        graph[u[i]+2*n].append(v[i])
    s,t = map(int,input().split())
    dist = [False]*(3*n+1)

    def bfs():
        q = deque([s])
        dist[s] = 0
        while len(q):
            cur = q.popleft()
            if cur == t:
                return dist[cur] // 3
            for to in graph[cur]:
                if dist[to] == False:
                    dist[to] = dist[cur] + 1
                    q.append(to)
        return -1

    print(bfs())

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n,m=map(int,input().split())
if m==0:
  print(-1)
  exit()
path=[[] for _ in range(3*n)]
for i in range(m):
  u,v=map(int,input().split())
  path[3*(u-1)].append(3*(v-1)+1)
  path[3*(u-1)+1].append(3*(v-1)+2)
  path[3*(u-1)+2].append(3*(v-1))
s,t=map(int,input().split())
s-=1
t-=1
visited=[0]*(3*m)
q=deque([3*s])
visited[3*s]=1
while q:
  x=q.popleft()
  if x%3==0 and x//3==t:
    print(visited[x]//3)
    exit()
  for i in path[x]:
    if visited[i]==0:
      visited[i]=visited[x]+1
      q.append(i)
print(-1)

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

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

    S,T = map(int,input().split())
    go =[[0 for _ in range(3)] for _ in range(N)]
    q = deque([(S-1,0)])
    while q:
        now,rest = q.popleft()
        for fol,fr in edge[now][rest]:
            if go[fol][fr] == 0:
                go[fol][fr] = go[now][rest]+1
                q.append((fol,fr))
                
    if go[T-1][0] != 0 and go[T-1][0]%3 == 0:
        print(go[T-1][0]//3)
        exit()
    
    print(-1)

if __name__ == "__main__":
    main()

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

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

    S,T = map(int,input().split())
    q = deque()
    go = [[False for _ in range(3)] for _ in range(N)]
    q.append((S-1,0,1))
    while q:
        now,step,d = q.popleft()
        if step == 3:
            if now == T-1:
                print(d)
                exit()
            step = 0
            d += 1
        if go[now][step]:
            continue
        go[now][step] = True
        for fol in edge[now]:
            q.append((fol,step+1,d))

    print(-1)

if __name__ == "__main__":
    main()

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()

edges = [[] for _ in range(3*N + 4)] 
for _ in range(M):
    u, v = lr()
    u *= 3; v *= 3
    edges[u].append(v+1)
    edges[u+1].append(v+2)
    edges[u+2].append(v)

INF = 10 ** 18

def dijkstra(start):
    dist = [INF] * (3*N+4)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heappop(que)
        if dist[v] < d:
            continue
        for next in edges[v]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

S, T = lr()
dist = dijkstra(S*3)
if dist[T*3] == INF:
    print(-1)
else:
    print(dist[T*3] // 3)

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()

edges = [[] for _ in range(3*N + 4)] 
for _ in range(M):
    u, v = lr()
    u *= 3; v *= 3
    edges[u].append(v+1)
    edges[u+1].append(v+2)
    edges[u+2].append(v)

INF = 10 ** 18

def dijkstra(start):
    dist = [INF] * (3*N+4)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heappop(que)
        if dist[v] < d:
            continue
        for next in edges[v]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

S, T = lr()
dist = dijkstra(S*3)
if dist[T*3] == INF:
    print(-1)
else:
    print(dist[T*3] // 3)

Solution (Python):
import sys
from collections import deque

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)

s, t = map(int, sys.stdin.readline().split())

def main():
    dist = [inf] * (n + 1)
    can_reach = [[False] * 3 for _ in range(n + 1)]
    queue = deque([(0, s)])
    can_reach[s][0] = True
    while queue:
        d, x = queue.popleft()
        if d % 3 == 0:
            dist[x] = min(dist[x], d // 3)
        d += 1
        for y in g[x]:
            if not can_reach[y][d%3]:
                can_reach[y][d%3] = True
                queue.append((d, y))

    return dist[t] if dist[t] != inf else -1

if __name__ == '__main__':
    ans = main()
    print(ans)

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

inf = float('inf')

n, m = map(int, sys.stdin.readline().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)

s, t = map(int, sys.stdin.readline().split())

def main():
    dist = [inf] * (n + 1)
    can_reach = [[False] * 3 for _ in range(n + 1)]
    hq = [(0, s)]
    can_reach[s][0] = True
    while hq:
        d, x = heappop(hq)
        if d % 3 == 0:
            dist[x] = min(dist[x], d // 3)
        d += 1
        for y in g[x]:
            if not can_reach[y][d%3]:
                can_reach[y][d%3] = True
                heappush(hq, (d, y))

    return dist[t] if dist[t] != inf else -1

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
from collections import defaultdict, deque
N, M = map(int, input().split())
dic = defaultdict(list)
for i in range(M):
  u, v = map(int, input().split())
  dic[u-1] += [v-1]
S, T = map(int, input().split())
S -= 1
T -= 1
dist = [[float('inf')]*3 for i in range(N)]
dist[S][0] = 0
q = deque([(S,0)])
flag = False
cnt = 0
while q:
  cnt += 1
  e, m = q.popleft()
  n = (m+1)%3
  for p in dic[e]:
    if p==T:
      flag = True
    if dist[p][n]>dist[e][m]+1:
      dist[p][n] = dist[e][m]+1
      q += [(p,n)]
if flag:
  ans = dist[T][0] if dist[T][0]!=float('inf') else -1
  print(ans//3)
else:
  print(-1)

Solution (Python):
import sys
from collections import deque


data = sys.stdin.readlines()
N, M = map(int, data[0].split())
edge = [[] for _ in range(N)]
for i in range(1, M + 1):
    u, v = map(int, data[i].split())
    u -= 1
    v -= 1
    edge[u].append(v)
S, T = map(lambda x: int(x) - 1, data[M + 1].split())

visited = set()
q = deque()
q.append((0, S))
ans = 10 ** 10
while len(q) > 0:
    c, v = q.popleft()
    key = (c % 3, v)
    if key in visited:
        continue
    visited.add(key)
    if v == T and c % 3 == 0:
        ans = min(ans, c // 3)
    else:
        for e in edge[v]:
            newKey = (c + 1, e)
            q.append(newKey)

if ans == 10 ** 10:
    print(-1)
else:
    print(ans)

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m=map(int,input().split())
G=[[] for i in range(3*n)]
for i in range(m):
    u,v=map(int,input().split())
    u-=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=map(int,input().split())
s-=1; t-=1




def disktra(g,s):
    c=1
    n=len(g)
    dist = [inf]*n
    dist[s] = 0
    hq=[]
    heapq.heappush(hq,(dist[s],s))
    while hq:
        cost,u =heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v in g[u]:
            if dist[v] <= dist[u] +c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq,(dist[v],v))
    return dist

dp=disktra(G,3*s)
print(-1 if dp[3*t]==inf else dp[3*t]//3)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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




def disktra(g,s):
    n=len(g)
    dist = [[inf]*3 for i in range(n)]
    dist[s][0] = 0
    hq=collections.deque(); hq.appendleft((0,s))
    while hq:
        cost,u =hq.pop()
        if dist[u][cost%3] < cost:
            continue
        for v in g[u]:
            if dist[v][(dist[u][cost%3]+1)%3] <= dist[u][cost%3] + 1:
                continue
            dist[v][(dist[u][cost%3]+1)%3] = dist[u][cost%3] + 1
            hq.appendleft((dist[v][(dist[u][cost%3]+1)%3],v))
    return dist

dp=disktra(G,s)
print(-1 if dp[t][0]==inf else dp[t][0]//3)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m = inpm()
    g = [[] for _ in range(n)]
    for _ in range(m):
        u,v = inpm()
        u -= 1
        v -= 1
        g[u].append(v)
    s,t = inpm()
    s -= 1
    t -= 1
    que = deque()
    que.append(s)
    visited1 = [0 for _ in range(n)]
    visited2 = [0 for _ in range(n)]
    visited3 = [0 for _ in range(n)]
    visited3[s] = 1
    cnt = 1
    while True:
        tank1 = deque()
        tank2 = deque()
        tank3 = deque()
        while que:
            start = que.pop()
            for go in g[start]:
                if not visited1[go]:
                    visited1[go] = 1
                    tank1.append(go)
        while tank1:
            start = tank1.pop()
            for go in g[start]:
                if not visited2[go]:
                    visited2[go] = 1
                    tank2.append(go)
        while tank2:
            start = tank2.pop()
            for go in g[start]:
                if not visited3[go]:
                    visited3[go] = 1
                    tank3.append(go)
                if go == t:
                    print(cnt)
                    return
        que = tank3
        cnt += 1
        if que == deque():
            break
    print(-1)
    
if __name__ == "__main__":
    main()

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



G = {}
for i in range(3*N):
  G[i] = []

for i in range(M):
  u,v = list(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 = list(map(int, input().split()))
S,T = S-1, T-1 

q = deque()
visited = [False for i in range(3*N)]
willsearch = [False for i in range(3*N)]
dists = [-1 for i in range(3*N)]
q.append(S)
dists[S] = 0

while len(q) > 0:
  now = q.popleft()
  visited[now] = True
  for nextp in G[now]:
    if visited[nextp] or willsearch[nextp]:
      continue
    willsearch[nextp] = True
    q.append(nextp)
    dists[nextp] = dists[now] + 1
    
if dists[T] > 0:
  print(dists[T] // 3)
else:
  print(-1)

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



G = {}
for i in range(3*N):
  G[i] = []

for i in range(M):
  u,v = list(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 = list(map(int, input().split()))
S,T = S-1, T-1 

q = deque()
visited = [False for i in range(3*N)]
willsearch = [False for i in range(3*N)]
dists = [-1 for i in range(3*N)]
q.append(S)
dists[S] = 0

while len(q) > 0:
  now = q.popleft()
  visited[now] = True
  for nextp in G[now]:
    if visited[nextp] or willsearch[nextp]:
      continue
    willsearch[nextp] = True
    q.append(nextp)
    dists[nextp] = dists[now] + 1
    
if dists[T] > 0:
  print(dists[T] // 3)
else:
  print(-1)

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

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


def dijkstra(graph, start, inf=float('inf')):
    import heapq
    n = len(graph)
    distances = [inf] * n
    distances[start] = 0
    visited = [False] * n

    
    hq = [(0, start)]
    while hq:
        dist, fr = heapq.heappop(hq)
        visited[fr] = True

        for to, cost in graph[fr]:
            new_dist = distances[fr] + cost
            if (visited[to]) or (distances[to] <= new_dist):
                continue

            distances[to] = new_dist
            heapq.heappush(hq, (new_dist, to))

    return distances


distances = dijkstra(G, S)
print(distances[T] // 3 if distances[T] != float('inf') else -1)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(3*N)]
    for i in range(M):
        u,v=map(lambda x: int(x)-1,input().split())
        for k in range(3):
            edge[u*3+k].append(v*3+(k+1)%3)
    S,T=map(lambda x:int(x)-1,input().split())
    que=deque()
    que.append(S*3)
    c=[-1]*(3*N)
    c[S*3]=0
    while que:
        v=que.popleft()
        for nv in edge[v]:
            if c[nv]==-1:
                c[nv]=c[v]+1
                que.append(nv)
    print(c[T*3]//3 if c[T*3]!=-1 else -1)
    

if __name__ == '__main__':
    main()

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


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

    S, T = map(int, input().split())
    S -= 1
    T -= 1
    dist = [[float('inf')] * 3 for _ in range(N)]
    dist[S][0] = 0
    q = deque([])
    q.append((S,0))
    while q:
        v, l = q.popleft()
        nl = (l + 1) % 3
        for nv in edge[v]:
            if dist[nv][nl] != float('inf'):
                continue
            dist[nv][nl] = dist[v][l] + 1
            q.append((nv,nl))
        
    
    if dist[T][0] == float('inf'):
        print(-1)
    else:
        print(dist[T][0] // 3)




if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

import sys 
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
g=[[] for _ in range(N)]
gr=[[] for _ in range(N)]
for _ in range(M):
    u,v=map(int,input().split())
    g[u-1].append(v-1)
    gr[v-1].append(u-1)
S,T=map(int,input().split())


f = [[-1,-1,-1] for _ in range(N)]
f[S-1][0] = 0
q=deque([[S-1,0]])

while q:
    d,s = q.popleft()
    s += 1
    for sd in g[d]:
        if f[sd][s%3]==-1:
            f[sd][s%3] = s//3
            q.append([sd,s])


print(f[T-1][0])

Solution (Python):
def main():
    N, M = map(int, input().split())
    U = [set() for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        U[u - 1].add(v - 1)
    S, T = map(int, input().split())
    S, T = S - 1, T - 1
    V = [False] * N
    V[S] = True
    cur = set([S])
    r = 0
    while cur and T not in cur:
        r += 1
        for _ in range(3):
            nxt = set()
            for c in cur:
                nxt |= U[c]
            cur = nxt
        nxt = set()
        for c in cur:
            if not V[c]:
                V[c] = True
                nxt.add(c)
        cur = nxt
    return r if T in cur else -1

print(main())

Solution (Python):
def main():
    N, M = map(int, input().split())
    d = {}
    for _ 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())
    cur = set([s])
    ne1 = set()
    ne2 = set()
    ne3 = set()
    c = 0
    v3 = set()
    v1 = set()
    v2 = set()
    while len(v3) < N:
        for i in cur:
            if i not in d:
                continue
            for j in d[i]:
                if j not in v1:
                    ne1.add(j)
                    v1.add(j)
        if len(ne1) == 0:
            return -1
        for i in ne1:
            if i not in d:
                continue
            for j in d[i]:
                if j not in v2:
                    ne2.add(j)
                    v2.add(j)
        if len(ne2) == 0:
            return -1
        for i in ne2:
            if i not in d:
                continue
            for j in d[i]:
                if j not in v3:
                    ne3.add(j)
                    v3.add(j)
        if len(ne3) == 0:
            return -1
        c += 1
        if t in ne3:
            return c
        cur = ne3
        ne1 = set()
        ne2 = set()
        ne3 = set()
    return -1
print(main())

Solution (Python):
from collections import deque
n,m=map(int,input().split())
if m==0:
  print(-1)
  exit()
edge=[[] for i in range(3*n)]
for i in range(m):
  u,v=map(int,input().split())
  edge[3*(u-1)].append(3*(v-1)+1)
  edge[3*(u-1)+1].append(3*(v-1)+2)
  edge[3*(u-1)+2].append(3*(v-1))
s,t=map(int,input().split())
s-=1
t-=1
visited=[0 for i in range(3*m)]
def bfs(edge,visited,s,t):
  q=deque([3*s])
  visited[3*s]=1
  cnt=0
  while q:
    x=q.popleft()
    if x%3==0 and x//3==t:
      return visited[x]//3
    for i in edge[x]:
      newx=i
      if visited[newx]==0:
        visited[newx]=visited[x]+1
        q.append(newx)
  return -1
print(bfs(edge,visited,s,t))

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
s,t = map(int,input().split())
visited = [[-1,-1,-1] for i in range(n+1)]
que = deque([(s,0,0)])
while que:
  x,mod,cnt = que.popleft()
  visited[x][mod] = cnt
  if x == t and mod == 0:
    break
  for y in graph[x]:
    if visited[y][(mod+1)%3] == -1:
      que.append((y,(mod+1)%3,cnt+1))
      visited[y][(mod+1)%3] = cnt+1
print(visited[t][0]//3)

Solution (Python):
from collections import  deque

class Graph(): 
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]-1].append(e[1]-1)
            self.deg[e[1]-1] += 1

import sys
input = sys.stdin.readline

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

g = Graph(N,edge)

stack = deque([(S,0)])
used = [[False]*3 for _ in range(N)]

while stack:
    node,depth = stack.popleft()
    if node == T and depth % 3 == 0:
        print(depth//3)
        break
    for adj in g.graph[node]:
        if not used[adj][(depth+1)%3]:
            used[adj][(depth+1)%3] = True
            stack.append((adj,depth+1))
else:
    print(-1)

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

from collections import deque

N, M = map(int, input().split())
UV = [list(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())
INF = 10 ** 15

if M == 0:
  print(-1)
  exit()

graph = [[] for _ in range(3 * M + 1)]
for u, v in UV:
  graph[u].append(v + M)
  graph[u + M].append(v + 2 * M)
  graph[u + 2 * M].append(v)

queue = deque([S])
dist = [INF] * (3 * M + 1)
dist[S] = 0

while queue:
  q = queue.popleft()
  for g in graph[q]:
    if dist[g] > dist[q] + 1:
      dist[g] = dist[q] + 1
      queue.append(g)
print(dist[T] // 3 if dist[T] != INF else -1)

Solution (Python):
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,M = list(map(int,input().split()))

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

    def z(i,j):
        return i + j*N

    for i in range(M):
        u,v = list(map(int,input().split()))
        u,v = u-1,v-1
        e_list[z(u,0)].append(z(v,1)) 
        e_list[z(u,1)].append(z(v,2)) 
        e_list[z(u,2)].append(z(v,0))

    S,T = list(map(int,input().split()))
    S,T = S-1,T-1
    from collections import deque

    vi = z(S,0)  
    INF = float('inf')

    Q = deque([vi])

    checked_list = [False]*3*N
    checked_list[vi]=True

    min_path_list = [INF]*3*N 
    min_path_list[vi] = 0

    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if not checked_list[v1]:
                checked_list[v1]=True
                Q.appendleft(v1)
                min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) 

    if min_path_list[z(T,0)]<10**9:
        print(min_path_list[z(T,0)]//3)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
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())

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = deque([S])
ans[S][0] = 0
while q:
    now = q.popleft()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

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

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
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())

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = deque([S])
ans[S][0] = 0
while q:
    now = q.popleft()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

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

Solution (Python):
import heapq

def main():
    n, m = map(int, input().split())
    uvs = [tuple(map(int, input().split())) for _ in range(m)]
    s, t = map(int, input().split())
    edges = [{} for _ in range(n*3)]
    for u, v in uvs:
        x, y = u-1, v-1
        for i in range(3):
            c = 1 if i == 0 else 0
            z = y + n*((i+1)%3)
            edges[x + n*i][z] = c
    l = dijkstra(edges, s-1, t-1)
    if l is None:
        print(-1)
    else:
        print(l)

def dijkstra(graph, start, end):
    q = []
    heapq.heapify(q)
    visited = set()

    for next_, cost in graph[start].items():
        heapq.heappush(q, (cost, next_))

    while len(q) > 0:
        node_cost, current = heapq.heappop(q)
        if current in visited:
            continue
        if current == end:
            return node_cost

        visited.add(current)
        for next_, path_cost in graph[current].items():
            heapq.heappush(q, (node_cost + path_cost, next_))

    return None

main()

Solution (Python):
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

FIFO=deque()
N,M=LI()
MP=[[[],[],[]] for i in range(N+1)]


for _ in range(M):
    i,j=LI()
    MP[i][0].append((j,1))
    MP[i][1].append((j,2))
    MP[i][2].append((j,0))

S,T=LI()
FIFO.append((S,0,0))
visited = [[False,False,False] for i in range(N+1)]
visited[S][0] = True

res = -1
while FIFO:
    i, rest_i, dist = FIFO.popleft()
    if i == T and rest_i == 0:
        res = dist // 3
        break
    for j, rest_j in MP[i][rest_i]:
        if not visited[j][rest_j]:
            visited[j][rest_j] = True
            FIFO.append((j, rest_j, dist+1))

print(res)

Solution (Python):
import collections
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        edges = [tuple(map(int, input().split())) for _ in range(M)]
        S, T = map(int, input().split())

        edge_map = collections.defaultdict(list)
        for u, v in edges:
            edge_map[u - 1].append(v - 1)

        q = queue.Queue()
        q.put((S - 1, 0))

        INF = 10 ** 5
        dist = [[INF] * 3 for _ in range(N)]
        dist[S - 1][0] = 0
        while not q.empty():
            node, kkp = q.get()

            for next_node in edge_map[node]:
                next_kkp = (kkp + 1) % 3
                if dist[next_node][next_kkp] == INF:
                    dist[next_node][next_kkp] = dist[node][kkp] + 1
                    q.put((next_node, next_kkp))

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



if __name__ == '__main__':
    AtCoder().main()

Solution (Python):




import sys
sys.setrecursionlimit(1000000)
from collections import deque

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

for i in UV:
    G[i[0]-1].append(i[1]-1)

reach = [[-1 for _ in range(N)] for _ in range(3)]
reach[0][S-1] = 0

que = deque()
que.append(S-1)

time = 1
for _ in range(4*N):
    new_que = deque()
    for q in que:
        for v in G[q]:
            if reach[time%3][v] == -1:
                reach[time%3][v] = time
                new_que.append(v)
    que = new_que
    time += 1
if reach[0][T-1] == -1:
    print(-1)
else:
    print(reach[0][T-1]//3)