Problem: 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.

Submission attempts (in order):
from collections import deque
import numpy as np
N,M = map(int,input().split(' '))


GM = np.zeros((N,N)).astype(np.int)

for j in [0]*M:
	u,v = map(int,input().split(' '))
	GM[u-1,v-1] = 1
	#G[u].append(v)
S,T = map(int,input().split(' '))

G3M = np.dot(np.dot(GM,GM),GM)

#G3 = {i: np.where(G3M[i-1]>0)[0] for i in range(1,N+1)}


st = [S]
visited = [S]
ans = 1
exist = True
while(exist):
	new_st = []
	exist = False
	for cand in st:
		#for n in G3[cand]:
		ls = np.where(G3M[cand-1]>0)[0]
		for n in ls:
			n = n+1
			if n == T:
				print(ans)
				exit()
			if not n in visited:
				exist = True
				visited.append(n)
				new_st.append(n)
	st = new_st[:]
	ans += 1
print(-1)









from collections import deque
import numpy as np
N,M = map(int,input().split(' '))


GM = np.zeros((N,N)).astype(np.int)

for j in [0]*M:
	u,v = map(int,input().split(' '))
	GM[u-1,v-1] = 1
	#G[u].append(v)
S,T = map(int,input().split(' '))

G3M = np.dot(np.dot(GM,GM),GM)

#G3 = {i: np.where(G3M[i-1]>0)[0] for i in range(1,N+1)}


st = [S]
visited = [S]
ans = 1
exist = True
while(exist):
	new_st = []
	exist = False
	for cand in st:
		#for n in G3[cand]:
		ls = np.where(G3M[cand-1]>0)[0]
		for n in ls:
			n = n+1
			if n == T:
				print(ans)
				exit()
			if not n in visited:
				exist = True
				visited.append(n)
				new_st.append(n)
	st = new_st
	ans += 1
print(-1)









from collections import deque
import numpy as np
N,M = map(int,input().split(' '))


GM = np.zeros((N,N)).astype(np.int)

for j in [0]*M:
	u,v = map(int,input().split(' '))
	GM[u-1,v-1] = 1
	#G[u].append(v)
S,T = map(int,input().split(' '))

GM = np.dot(np.dot(GM,GM),GM)

G3 = {i: list(np.where(GM[i-1]==1)[0]+1) for i in range(1,N+1)}


st = [S]
visited = [S]
ans = 1
exist = True
while(exist):
	new_st = []
	exist = False
	for cand in st:
		for n in G3[cand]:
			if n == T:
				print(ans)
				exit()
			if not n in visited:
				exist = True
				visited.append(n)
				new_st.append(n)
	st = new_st
	ans += 1
print(-1)









from collections import deque
import numpy as np
N,M = map(int,input().split(' '))


GM = np.zeros((N,N)).astype(np.int)

for j in [0]*M:
	u,v = map(int,input().split(' '))
	GM[u-1,v-1] = 1
	#G[u].append(v)
S,T = map(int,input().split(' '))

G3M = np.dot(np.dot(GM,GM),GM)

G3 = {i: list(np.where(G3M[i-1]>0)[0]+1) for i in range(1,N+1)}


st = [S]
visited = [S]
ans = 1
exist = True
while(exist):
	new_st = []
	exist = False
	for cand in st:
		for n in G3[cand]:
			if n == T:
				print(ans)
				exit()
			if not n in visited:
				exist = True
				visited.append(n)
				new_st.append(n)
	st = new_st
	ans += 1
print(-1)









import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N,M= map(int,input().split())
g = defaultdict(list)

for i in range(M):
    u,v = list(map(int,input().split()))
    g[u].append(N + v)
    g[N + u].append(2*N + v)
    g[2*N + u].append(v)
S,T= map(int,input().split())

dq = deque([S])
inf = 10**15
d = [inf for i in range(3*N+1)]
d[S] = 0

while dq:
    v = dq.popleft()
    for nv in g[v]:
        if d[nv] > d[v] + 1:
            d[nv] = d[v] + 1
            dq.append(nv)

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





Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted