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):
n, m = map(int, input().split())

lst = [[] for i in range(3*n+1)]
dist = [-1 for i in range(3*n+1)]
for i in range(m):
    u, v = map(int, input().split())
    lst[u].append(v+n)
    lst[u+n].append(v+2*n)
    lst[u+2*n].append(v)

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

next = lst[s]
next_next = []
not_empty = True
cost = 1
while not_empty:
    not_empty = False
    for i in next:
        if dist[i] == -1:
            dist[i] = cost
            next_next.extend(lst[i])
            not_empty = True
    next = next_next.copy()
    next_next = []
    cost += 1

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m = LI()
    aa = [LI() for _ in range(m)]
    s,t = LI()
    e = collections.defaultdict(set)
    for a,b in aa:
        e[a].add(b)

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[(s,0)] = 0
        q = []
        heapq.heappush(q, (0, (s,0)))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True
            uk = (k+1)
            kk = (k+1) % 3

            for uu in e[u[0]]:
                uv = (uu, kk)
                if v[uv]:
                    continue
                if d[uv] > uk:
                    d[uv] = uk
                    heapq.heappush(q, (uk, uv))

        return d

    d = search(s)
    r = d[(t,0)]
    if r == inf:
        return -1

    return r // 3


print(main())

Solution (Python):
from collections import deque

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[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, T = 3 * (S - 1), 3 * (T - 1)


def bfs():
    cnt = 0
    q = deque()
    visited = [False for _ in range(3 * N)]
    q.append(S)
    visited[S] = True
    while len(q) > 0:
        new_q = deque()
        cnt += 1
        while(len(q) > 0):
            u = q.pop()
            for v in G[u]:
                if visited[v]:
                    continue
                if v == T:
                    return cnt // 3

                visited[v] = True
                new_q.append(v)
        q = new_q
    return -1


print(bfs())

Solution (Python):
from collections import deque

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

distance = [10**9 for _ in range(3*N)]
distance[S] = 0

queue = deque([S])
while queue:
    u = queue.popleft()
    for next in edge[u]:
        if distance[u]+1 < distance[next]:
            distance[next] = distance[u]+1
            queue.append(next)
if distance[T] < 10**9:
    print(distance[T]//3)
else:
    print(-1)

Solution (Python):


import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bfs(N: int, nodes: list, src: int) -> list:
    """ 幅優先探索(頂点数, 隣接リスト(0-indexed), 始点) """

    
    res = [[INF] * N for i in range(3)]
    
    que = deque([(0, src)])
    res[0][src] = 0
    
    while len(que) != 0:
        
        k, cur = que.popleft()
        
        for nxtk, nxt in nodes[k][cur]:
            
            if res[k][cur] + 1 < res[nxtk][nxt]:
                res[nxtk][nxt] = res[k][cur] + 1
                
                que.append((nxtk, nxt))
    
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1


nodes2=[[[] for j in range(N)] for i in range(3)]
for i in range(3):
    for u, node in enumerate(nodes):
        for v in node:
            nodes2[i][u].append(((i+1)%3, v))

res=bfs(N, nodes2, S)
if res[0][T]==INF:
    print(-1)
else:
    
    print(res[0][T]//3)

Solution (Python):


import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bfs(N: int, nodes: list, src: int) -> list:
    """ 幅優先探索(頂点数, 隣接リスト(0-indexed), 始点) """

    
    res = [[INF] * N for i in range(3)]
    
    que = deque([(0, 0, src)])
    res[0][src] = 0
    
    while len(que) != 0:
        
        _, k, cur = que.popleft()
        
        for nxtk, nxt in nodes[k][cur]:
            
            if res[k][cur] + 1 < res[nxtk][nxt]:
                res[nxtk][nxt] = res[k][cur] + 1
                
                que.append((res[nxtk][nxt], nxtk, nxt))
    
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1


nodes2=[[[] for j in range(N)] for i in range(3)]
for i in range(3):
    for u, node in enumerate(nodes):
        for v in node:
            nodes2[i][u].append(((i+1)%3, v))

res=bfs(N, nodes2, S)
if res[0][T]==INF:
    print(-1)
else:
    
    print(res[0][T]//3)

Solution (Python):


import sys
from heapq import heappop, heappush

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点) """

    
    res = [[INF] * N for i in range(3)]
    
    que = [(0, 0, src)]
    res[0][src] = 0
    
    while len(que) != 0:
        
        _, k, cur = heappop(que)
        
        for nxtk, nxt in nodes[k][cur]:
            
            if res[k][cur] + 1 < res[nxtk][nxt]:
                res[nxtk][nxt] = res[k][cur] + 1
                
                heappush(que, (res[nxtk][nxt], nxtk, nxt))
    
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1


nodes2=[[[] for j in range(N)] for i in range(3)]
for i in range(3):
    for u, node in enumerate(nodes):
        for v in node:
            nodes2[i][u].append(((i+1)%3, v))

res=dijkstra(N, nodes2, S)
if res[0][T]==INF:
    print(-1)
else:
    
    print(res[0][T]//3)

Solution (Python):
from heapq import *
f_inf = float('inf')

def dijkstra(start,node,edge):
    
    
    
    
    d = [[f_inf, f_inf, f_inf] for _ in [0]*node]
    d[start][0] = 0
    
    q = [(0,start)]

    while(len(q) != 0):
    
      ci,i = heappop(q)
    
      for j in edge[i]:
        nc = ci + 1
        if (d[j][nc%3] > nc):
          d[j][nc%3] = nc
          heappush(q,(nc, j))
    return d

N,M = (int(x) for x in input().split())

E = [[] for _ in [0]*N]

for i in range(M):
  a,b = (int(x) for x in input().split())
  E[a-1].append(b-1)

S,T = (int(x)-1 for x in input().split())
d = dijkstra(S, N, E)
ans = d[T][0]

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

Solution (Python):

import sys
from collections import deque

n, m = map(int, input().split())
g = [[] for _ 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 = 3 * (s - 1)
t = 3 * (t - 1)

depth = dict()
depth[s] = 0
q = deque([s])


while(len(q) != 0):
    v = q.popleft()
    for u in g[v]:
        if u not in depth:
            q.append(u)
            depth[u] = depth[v] + 1

print(depth[t] // 3 if t in depth else -1)

Solution (Python):
from collections import deque

def BFS(path, start, goal):
  que = deque()
  for uv in path[start]:
    que.append(uv)
  visited=[-1 for i in range(3*N)]
  visited[start] = 0
  i = 0
  while que:
    uv = que.popleft()
    
    if visited[uv[1]] == -1:
      visited[uv[1]] = visited[uv[0]] + 1
      for vw in path[uv[1]]:
        que.append(vw)
    if i >3*N:break
  return visited[goal]

N,M = map(int,input().split())
edge = [[] for i in range(3*N)]
for i in range(M):
  u,v = map(int,input().split())
  edge[0*N + u - 1] += [[0*N + u - 1,1*N + v - 1]]
  edge[1*N + u - 1] += [[1*N + u - 1,2*N + v - 1]]
  edge[2*N + u - 1] += [[2*N + u - 1,0*N + v - 1]]
  
S, T = map(int,input().split())
print(BFS(edge, S-1, T-1)//3)

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')







N, M = [int(x) for x in input().split()]


E = defaultdict(lambda: set())

for i in range(M):
    u, v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    E[3 * u].add(3 * v + 1)
    E[3 * u + 1].add(3 * v + 2)
    E[3 * u + 2].add(3 * v)

S, T = [int(x) for x in input().split()]
S = 3 * (S - 1)
T = 3 * (T - 1)


def bfs(e, start, end):
    open = deque([start])
    w = dict()
    w[start] = 0
    while len(open) != 0:
        target = open.popleft()
        for next in E[target]:
            if not next in w:
                open.append(next)
                w[next] = w[target] + 1

    return w[end] // 3 if end in w else -1


print(bfs(E, S, T))

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')







N, M = [int(x) for x in input().split()]


E = defaultdict(lambda: set())

for i in range(M):
    u, v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    E[3 * u].add(3 * v + 1)
    E[3 * u + 1].add(3 * v + 2)
    E[3 * u + 2].add(3 * v)

S, T = [int(x) for x in input().split()]
S = 3 * (S - 1)
T = 3 * (T - 1)


def bfs(e, start, end):
    open = deque([start])
    w = dict()
    w[start] = 0
    while len(open) != 0:
        target = open.popleft()
        for next in E[target]:
            if not next in w:
                open.append(next)
                w[next] = w[target] + 1

    return w[end] // 3 if end in w else -1


print(bfs(E, S, T))

Solution (Python):
import sys
from collections import deque

N,M=map(int, sys.stdin.readline().split())

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

for i in range(M):
	u,v=map(int, sys.stdin.readline().split())
	nl[u].append(v)

S,T=map(int, sys.stdin.readline().split())

V=[ [ None for j in range(3) ] for i in range(N+1) ]
V[S][0]=0


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

while q:
	x=q.popleft()
	fro=x[0]
	cur_mod=x[1]

	for to in nl[fro]:
		next_mod=(cur_mod+1)%3
		if V[to][next_mod] is None:
			V[to][next_mod]=V[fro][cur_mod]+1
			if V[T][0] is not None:
				break
			q.append( ( to, next_mod ) )


if V[T][0] is None:
	print -1
else:
	print V[T][0]/3

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) 

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

from collections import deque


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

while q:
    now, cost = q.popleft()
    state = cost % 3
    if used[now][state] == mod:
        used[now][state] = cost
        for route in routes[now]:
            q.append((route,cost+1))


try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) 

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

from collections import deque


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

while q:
    now, cost = q.popleft()
    for route in routes[now]:
        n_state = (cost + 1) % 3
        if used[route][n_state] == mod:
            used[route][n_state] = cost + 1
            q.append((route,cost+1))



try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))

Solution (Python):
from collections import deque
N, M = map(int, input().split())
INF = 1001001001
dist = [[INF for _ in range(3)] for _ in range(N)]


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


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

while q:
    k, l = q.popleft()
    for i in G[k]:
        nl = (l + 1) % 3
        if dist[i][nl] == INF:
            dist[i][nl] = dist[k][l] + 1
            q.append((i, nl))

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

Solution (Python):
from collections import deque
N, M = map(int, input().split())
INF = 1001001001
dist = [[INF for _ in range(3)] for _ in range(N)]


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


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

while q:
    v, l = q.popleft()
    for u in G[v]:
        nl = (l + 1) % 3
        if dist[u][nl] == INF:
            dist[u][nl] = dist[v][l] + 1
            q.append((u, nl))

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

Solution (Python):


from collections import defaultdict,deque


class Graph:

  def __init__(self,N,uv,S,T):
    self.graph = uv
    self.start = S
    self.goal = T
    self.states  = [[-3 for _ in range(3)] for _ in range(N)]
    self.states[self.start][0] = 0

  def solve(self):
    nxt = deque([self.start])
    
    while len(nxt) > 0:
      p = nxt.popleft()
      for q in self.graph[p]:
        for ps in range(3):
          if self.states[p][ps] >= 0:
            qs = (ps+1)%3
            if self.states[q][qs] < 0:
              self.states[q][qs] = self.states[p][ps]+1
              nxt.append(q)
            else:
              self.states[q][qs] = min(self.states[q][qs],self.states[p][ps]+1)
    
    return self.states[self.goal][0]


def main():
  
  N,M = map(int, input().split())
  uv = defaultdict(set)
  for _ in range(M):
    u,v = map(int, input().split())
    uv[u-1].add(v-1)
  S,T = map(int, input().split())

  
  graph = Graph(N,uv,S-1,T-1)
  print(graph.solve()//3)


if __name__ == "__main__":
  main()

Solution (Python):
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    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[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, T = 3*(S-1), 3*(T-1)

    cnt = 0
    q = deque()
    q.append(S)
    visited = [False] * (3*N)
    visited[S] = True
    while len(q) > 0:
        q_ = deque()
        cnt += 1
        while len(q) > 0:
            n = q.pop()
            for m in G[n]:
                if visited[m]:
                    continue

                if m == T:
                    return cnt // 3

                visited[m] = True
                q_.append(m)

        q = q_

    return -1


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

Solution (Python):
import sys
from fractions import gcd
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, m = LI()
    g = [[] for i in range(3*(n+1))]
    for i in range(m):
        u, v = LI()
        g[u].append(v + n + 1)
        g[u + n + 1].append(v + 2*(n + 1))
        g[u + 2*(n + 1)].append(v)

    s, t = LI()

    Q = deque([s])
    searched = [0 for i in range(3*(n+1))]
    searched[s] = 1
    depth = [0 for i in range(3*(n+1))]
    while len(Q) != 0:
        v = Q.popleft()
        for i in g[v]:
            if i == t:
                depth[i] = depth[v] + 1
                print(depth[i]//3)
                return
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from fractions import gcd
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, m = LI()
    g = [[] for i in range(3*(n+1))]
    for i in range(m):
        u, v = LI()
        g[u].append(v + n + 1)
        g[u + n + 1].append(v + 2*(n + 1))
        g[u + 2*(n + 1)].append(v)

    s, t = LI()

    Q = deque([s])
    searched = [0 for i in range(3*(n+1))]
    searched[s] = 1
    depth = [0 for i in range(3*(n+1))]
    while len(Q) != 0:
        v = Q.popleft()
        for i in g[v]:
            if i == t:
                depth[i] = depth[v] + 1
                print(depth[i]//3)
                return
            if searched[i] == 0:
                depth[i] = depth[v] + 1
                Q.append(i)
                searched[i] = 1
    print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
import heapq


def main():
    N, M = map(int, input().split())
    E_in = [list(map(int, input().split())) for _ in range(M)]
    S, T = map(int, input().split())

    N2 = N * 2
    
    V = [0] + [i for i in range(3*N+1)]
    E = defaultdict(dict)
    for e in E_in:
        u = e[0]
        v = e[1]
        E[u][v+N] = 1
        E[u+N][v+N2] = 1
        E[u+N2][v] = 1
    
    INF = 10 ** 18

    def calc_distance(V, E, S):
        d = [INF] * len(V)
        d[S] = 0
        h = []
        heapq.heappush(h, (0, S))
        while h:
            du, u = heapq.heappop(h)
            for v, x in E[u].items():
                if du + x < d[v]:
                    d[v] = du + x
                    heapq.heappush(h, (d[v], v))
        return d
    

    d = calc_distance(V, E, S)
    if d[T] == INF:
        print(-1)
    else:
        print(d[T] // 3)


main()

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

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

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

graph = [[] for _ in range(N + 1)]
for v, u in VU:
    graph[v].append(u)

que = deque()
que.append((S, 0))
reached = np.zeros((N + 1, 3), dtype=bool)
reached[S, 0] = True
ans = -1
while que:
    v, d = que.popleft()
    if v == T and d % 3 == 0:
        ans = int(d // 3)
    for u in graph[v]:
        if not reached[u, (d + 1) % 3]:
            reached[u, (d + 1) % 3] = True
            que.append((u, d + 1))
print(ans)

Solution (Python):
import heapq


def dijkstra(n: int, s: int, g: int, Graph) -> int:
    INF = float('inf')
    dis = [[INF, INF, INF] for _ in range(n)]
    dis[s][0] = 0
    hq = []
    heapq.heappush(hq, (0, s, 0))

    while hq:
        c, n, idx = heapq.heappop(hq)
        for i in Graph[n][idx]:
            to, idx, weight = i
            if dis[to][idx] > c + weight:
                dis[to][idx] = c + weight
                if to == g and idx == 0:
                    return dis[to][idx]//3
                heapq.heappush(hq, (dis[to][idx], to, idx))
    return -1


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

graph = [[[], [], []] for _ in range(N)]
for _ in range(M):
    frm, to = map(int, input().split())
    graph[frm-1][0].append((to-1, 1, 1))
    graph[frm-1][1].append((to-1, 2, 1))
    graph[frm-1][2].append((to-1, 0, 1))

S, T = map(int, input().split())
dis = dijkstra(N, S-1, T-1, graph)
print(dis)

Solution (Python):
import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

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


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

heap = [(0, S)]
dist = [INF] * (N * 3 + 1)
ans = -1
while heap:
    d, v = heapq.heappop(heap)
    if v == T and d % 3 == 0:
        ans = int(d // 3)
        break
    for u in graph[v]:
        if d + 1 < dist[u]:
            dist[u] = d + 1
            heapq.heappush(heap, (d + 1, u))
print(ans)

Solution (Python):
import heapq
N, M = map(int, input().split())
Edge = [list(map(int, input().split())) for i in range(M)]

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


G3 = [[] for i in range(3 * N)]
for u, v in Edge:
    u, v = u - 1, v - 1
    G3[u].append([v + N, 1])
    G3[u + N].append([v + N * 2, 1])
    G3[u + 2 * N].append([v, 1])


def dijkstra(x):
    d = [float('inf')] * (3 * N)
    d[x] = 0
    visited = {x}

    
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G3[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u] + cost, node))
    return d


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

Solution (Python):
import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

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

U = []
V = []
for u, v in UV:
    U.extend([u, u + N, u + N * 2])
    V.extend([v + N, v + N * 2, v])









graph = [[] for _ in range(N * 3 + 1)]
for u, v in zip(U, V):
    graph[u].append(v)


heap = [(0, S)]
dist = [IINF] * (N * 3 + 1)
while heap:
    d, v = heapq.heappop(heap)
    if v == T:
        print(int(d // 3))
        exit()
    for u in graph[v]:
        if d + 1 < dist[u]:
            dist[u] = d + 1
            heapq.heappush(heap, (d + 1, u))
print(-1)

Solution (Python):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

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

graph = [[] for _ in range(N + 1)]
for u, v in UV:
    graph[u].append(v)

que = deque()
que.append((S, 0))
reached = np.zeros((N + 1, 3), dtype=bool)
reached[S, 0] = True

while que:
    u, step = que.popleft()
    for v in graph[u]:
        s = step + 1
        if not reached[v, s % 3]:
            reached[v, s % 3] = True
            que.append((v, s))
        if v == T and s % 3 == 0:
            print(s // 3)
            exit()
print(-1)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        G[u-1].append(v-1)
    S, T = map(int, input().split())
    S, T = S-1, T-1

    q = deque()
    q.append(S)
    cnt = 0
    cnt_k = 0
    visited = [False] * N
    visited[S] = True
    while len(q) > 0:
        cnt += 1
        if cnt % 3 == 0:
            cnt_k += 1

        next_ = set()
        while len(q) > 0:
            n0 = q.pop()
            for n1 in G[n0]:
                if cnt % 3 == 0:
                    if n1 == T:
                        return cnt_k

                    if visited[n1]:
                        continue

                    visited[n1] = True

                next_.add(n1)

        q = deque()
        q.extend(list(next_))

    return -1


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

Solution (Python):
import sys, collections

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    son = [[] for i in range(N)] 
    for i in range(M):
        u, v = map(int, input().split())
        son[u-1].append(v-1)
    S, T = map(int, input().split())

    dist = [[-1, -1, -1] for i in range(N)]
    que = collections.deque()
    que.append((0, S-1, 0)) 
    while que:
        cost, now, mod = que.popleft()
        if dist[now][mod] == -1:
            dist[now][mod] = cost
            if mod == 0:
                for s in son[now]:
                    if dist[s][1] == -1: que.append((cost + 1, s, 1))
            else:
                for s in son[now]:
                    if dist[s][(mod + 1) % 3] == -1: que.append((cost, s, (mod + 1) % 3))

    print(dist[T-1][0])  
    return 0

if __name__ == "__main__":
    solve()

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)