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



Sample input:
4 4
1 2
2 3
3 4
4 1
1 3


Sample output:
2

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    # power_funcを用いて(nCk) mod p を求める 
    # nCk = n!/((n-k)!k!)を使用

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    # a^b mod p を求める
    # bを2進数分解して高速累乗

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

#D
def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge, g):

    dist = [inf for i in range(num)]
    dist[start] = 0
    q = [(dist[start], start)]
    while q:
        du, u = heappop(q)
        for j in edge[u]:
            if dist[j] > du + 1:
                dist[j] = du + 1
                heappush(q, [dist[j], j])
            if j == g:
                return
    return dist
#E
def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = defaultdict(list)
    for x,y in v:
        edge[x].append(y)
    newedge = defaultdict(list)
    for key, i in edge.items():
        b = []
        for j in i:
            for k in edge[j]:
                b.append(k)
            if edge[j] == []:
                a = edge.pop(j)
        b = list(set(b))
        newedge[key] = b
    nnewedge = defaultdict(list)
    for key, i in newedge.items():
        b = []
        for j in i:
            for k in edge[j]:
                if key == k:
                    continue
                b.append(k)
        b = list(set(b))
        nnewedge[key] = b
    d = dijkstra(n, s, nnewedge, t)
    if d[t] == inf:
        print(-1)
    else:
        print(d[t])
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
d = {}

for i in range(M):
    u, v =  map(int, input().split())
    if not u in d:
        d[u] = [] 
    d[u].append(v)
S, T = map(int, input().split())

anslist = []

def go(now, num, ans, flag):
    # print(now, num, ans)
    if ans > 3 * M:
        return -1
    if ans > M / 3 and flag == 0:
        return -1
    if num == 3 and now == T:
        # print(ans)
        anslist.append(ans)
        return
    if now == T:
        flag = 1
    if num == 3:
        ans += 1
        num = 0
    if now in d:
        li = 0
        if T in d[now]:
            if go(T, num + 1, ans, flag) == -1:
                li += 1
        for v in d[now]:
            if v != T:
                if go(v, num + 1, ans, flag) == -1:
                    li += 1
        if li == len(d[now]):
            return -1
    else:
        return -1

if go(S, 0, 1, 0) == -1:
    print(-1)
else:
    print(min(anslist))

Submission status: Runtime Error

Solution code:
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 = [set() for i in range(n+1)]
    new_g = [set() for i in range(n+1)]
    new_gg = [set() for i in range(n+1)]
    for i in range(m):
        u, v = LI()
        g[u].add(v)
    s, t = LI()
    for i in range(n+1):
        new = set()
        for j in g[i]:
            new = new | g[j]
        new_g[i] = new_g[i] | new

    for i in range(n+1):
        new = set()
        for j in new_g[i]:
            new = new | g[j]
        new_gg[i] = new_gg[i] | new

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
g -= 1
co = Max
def dfs(x,nn,now,coun):
    global sss,g,co
    if min(sss[now][nn],coun) == coun:
        if now == g and nn == 0:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            for i in x[now]:
                if nn == 2:
                    nn = 0
                    coun += 1
                else:
                    nn += 1
                dfs(x,nn,i,coun)
    else:
        if now == g and nn == 0:
            co = min(co,coun)
dfs(s,st-1,0,0)
if co == Max:
    print(-1)
else:
    print(co)

Submission status: Runtime Error

Solution code:

# # import itertools

# # # N, K = map(int, input().split())

# # def com(n, r):
# #     a = len(list(itertools.combinations(range(n), r)))
# #     return a


from collections import defaultdict

N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)

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

d = defaultdict(int)
ans = 0
def dfs(u, path, num, dis):
    global ans
    path += str(u)
    if d[path] != 0:
        ans = -1
        return

    if u == T and num % 3 == 0:
        ans = int(dis / 3)
        return
    if len(path) == 4:
        d[path] += 1
        path = ""
    for v in G[u]:
        dfs(v, path, num+1, dis+1)

dfs(S, path="", num=0, dis=0)
if ans == 0:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
N,M = map(int,input().split(' '))
#G = {i:[] for i in range(1,N+1)}

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

#dq =deque([S])
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)

Submission status: Runtime Error

Solution code:
import sys
import itertools

N, M = map(int, input().split())
nexts = dict()
nexts_rev = dict()
for _ in range(M):
    u, v = map(int, input().split())
    nexts.setdefault(u, [])
    nexts[u].append(v)
    nexts_rev.setdefault(v, [])
    nexts_rev[v].append(u)
S, T = map(int, input().split())
if S not in nexts.keys():
    print(-1)
    sys.exit()
dist = 0
dists = [-1] * 3
queue = [S]
while len(queue) > 0:
    next_queue = []
    for n in queue:
        if n == T:
            m = dist % 3
            if m == 0:
                print(dist // 3)
                sys.exit()
            elif dists[m] == -1:
                dists[m] = dist
        else:
            next_queue.extend(nexts[n])
    if dists[1] > 0 and dists[2] > 0:
        break
    queue = next_queue
    dist += 1

if T not in nexts_rev.keys():
    print(-1)
    sys.exit()
dist = 0
dists_rev = [-1] * 3
queue = [T]
while len(queue) > 0:
    next_queue = []
    for n in queue:
        if n == S:
            m = dist % 3
            if dists_rev[m] == -1:
                dists_rev[m] = dist
        else:
            next_queue.extend(nexts_rev[n])
    if dists_rev[0] > 0 and dists_rev[1] > 0 and dists_rev[2] > 0:
        break
    queue = next_queue
    dist += 1

ans = -1
if dists[1] > 0 and dists_rev[1] > 0:
    a = (dists[1] * 2 + dists_rev[1]) // 3
    ans = max(ans, a)
if dists[2] > 0 and dists_rev[2] > 0:
    a = (dists[2] * 2 + dists_rev[2]) // 3
    ans = max(ans, a)
if dists[1] > 0 and dists_rev[0] > 0:
    a = (dists[1] * 3 + dists_rev[0] * 2) // 3
    ans = max(ans, a)
if dists[2] > 0 and dists_rev[0] > 0:
    a = (dists[1] * 3 + dists_rev[2] * 2) // 3
    ans = max(ans, a)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
G = [[] for k in range(N)]

for k in range(M):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)

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

D1 = [200000 for k in range(N)]
D1[S] = 0
def dfs1(now, dist):
    for tsugi in G[now]:
        if D1[tsugi] > dist + 1:
            D1[tsugi] = dist + 1
            dfs1(tsugi, dist+1)

D2 = [200000 for k in range(N)]
D2[T] = 0
def dfs2(now, dist):
    for tsugi in G[now]:
        if D2[tsugi] > dist + 1:
            D2[tsugi] = dist + 1
            dfs2(tsugi, dist+1)

dfs1(S,0)
dfs2(T,0)

if D1[T] == 200000:
    print(-1)
    exit(0)
if D1[T]%3 == 0:
    print(D1[T]//3)
elif D1[T]%3 == 1:
    ans = 100000
    for k in range(N):
        if D2[k]%3 == 2:
            ans = min(1+(D1[T]+D2[k])//3,ans)
    if ans == 100000:
        print(-1)
    else:
        print(ans)
elif D1[T]%3 == 2:
    ans = 100000
    for k in range(N):
        if D2[k]%3 == 1:
            ans = min(1+(D1[T]+D2[k])//3,ans)
    if ans == 100000:
        print(-1)
    else:
        print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np


N, M = map(int, input().split())
conn = np.zeros((M + 1, M + 1), dtype="int8")
for _ in range(M):
    u, v = map(int, input().split())
    conn[u, v] = 1
S, T = map(int, input().split())


def hop3(n):
    n1 = np.zeros(M + 1, dtype="int8")
    n1[n] = 1
    n2 = np.dot(n1, conn)
    n3 = np.dot(n2, conn)
    n4 = np.dot(n3, conn)
    ans = set()
    for i in range(M + 1):
        if n4[i] != 0:
            ans.add(i)
    return ans


q = deque()
q.append(S)
dp = [-1] * (N + 1)
dp[S] = 0


while len(q) > 0:
    n = q.popleft()
    for m in hop3(n):
        if dp[m] < 0:
            dp[m] = dp[n] + 1
            if m == T:
                print(dp[m])
                exit()
            q.append(m)
print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
class AdjDiGraph:
     def __init__(self,g):
          lines = g.split("\n")
          self.size = int(lines[0])+1 
          self.adjMatrix = np.zeros((self.size, self.size)) # 指定された大きさで要素が0の行列を生成する
          for s in lines[1:]:
               d1,d2 = s.split(" ")
               self.connect(int(d1),int(d2))
          self.adjMatrix=np.dot(np.dot(self.adjMatrix,self.adjMatrix),self.adjMatrix)
     def connect(self, x, y):
          self.connect1(x,y)            
     def connect1(self, x, y):
          self.adjMatrix[x][y] = 1
     def connected(self,x,y):
          return self.adjMatrix[x][y] == 1

     def traceByPower(self,start,end,rememberA=None,kaisu=None):
          if rememberA==None:
               c=self.adjMatrix
               rememberA=[self.adjMatrix]
               for i in range(2,self.size):
                    c=np.dot(c,self.adjMatrix)
                    rememberA.append(c)
        
          if kaisu==None:
               kaisu=0
               for A_i in rememberA:
                    kaisu+=1
                    if A_i[start][end]!=0:
                         return self.traceByPower(start,end,rememberA,kaisu)
          else:
               if kaisu==1:
                    return [start,end]
               else:
                    for i in range(1,kaisu):#startからi回でinterchange(中継地点)、interchangeからendをkaisu-i回で行く
                         for interchange in range(self.size):
                              if rememberA[i-1][start][interchange]!=0 and rememberA[kaisu-i-1][interchange][end]!=0:
                                   return self.traceByPower(start,interchange,rememberA,i)[:-1]+self.traceByPower(interchange,end,rememberA,kaisu-i)



n,m=map(int,input().split())
g=[str(n),"\n"]
for i in range(m):
     g.append(input())
     g.append("\n")
graph = AdjDiGraph("".join(g[:-1]))
s,t=map(int,input().split())
ans=graph.traceByPower(s,t)
if ans==None:
     print(-1)
else:
     print(len(ans)-1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
d = {}

for i in range(1, M+1):
    d[i] = []

for i in range(M):
    u, v =  map(int, input().split())
    d[u].append(v)
S, T = map(int, input().split())

anslist = []
def go(now, num, ans, flag):
    # print(now, num, ans)
    if ans > 3 * M:
        return -1
    if ans > M / 3 and flag == 0:
        return -1
    if num == 3 and now == T:
        # print(ans)
        anslist.append(ans)
        return
    if now == T:
        flag = 1
    if num == 3:
        ans += 1
        num = 0
    if now in d:
        li = []
        if T in d[now]:
            go(T, num + 1, ans, flag)
        for v in d[now]:
            if go(v, num + 1, ans, flag) == -1:
                li.append(-1)
        if len(li) == len(d[now]):
            return -1
    else:
        return -1

if go(S, 0, 1, 0) == -1:
    print(-1)
else:
    print(min(anslist))

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np


N, M = map(int, input().split())
conn = np.zeros((M + 1, M + 1))
for _ in range(M):
    u, v = map(int, input().split())
    conn[u, v] = 1
S, T = map(int, input().split())


def get(dic, key):
    return dic[key] if key in dic else []


def hop3(n):
    n1 = np.zeros(M + 1)
    n1[n] = 1
    n2 = np.dot(n1, conn)
    n3 = np.dot(n2, conn)
    n4 = np.dot(n3, conn)
    ans = set()
    for i in range(M + 1):
        if n4[i] == 1:
            ans.add(i)
    return ans


q = deque()
q.append(S)
dp = [-1] * (N + 1)
dp[S] = 0


while len(q) > 0:
    n = q.popleft()
    for m in hop3(n):
        if dp[m] < 0:
            dp[m] = dp[n] + 1
            if m == T:
                print(dp[m])
                exit()
            q.append(m)
print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np
N,M = map(int,input().split(' '))
#G = {i:[] for i in range(1,N+1)}

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

#dq =deque([S])
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)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
N, M = list(map(int, input().split()))

edge = [list(map(int, input().split())) for i in range(M)]
edge = np.asarray([[i[0]-1, i[1]-1] for i in edge])
Map = np.zeros((N, N))
for e in edge:
  Map[e[0]][e[1]] = 1

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

Map = np.dot(np.dot(Map, Map), Map)
Map[Map > 0] = 1
calc_Map = []
count = 0
while True:
  for cand in calc_Map:
    if (Map == cand).all():
      print(-1)
      sys.exit(0)
  calc_Map.append(Map)
  count+=1
  if Map[S][T] == 1:
    break
  Map = np.dot(Map, Map)
  Map[Map > 0] = 1
  
print(count)

Submission status: Runtime Error

Solution code:
words = lambda t : list(map(t, input().split()))

def dfs(ns,s,t):
    n_steps = [[-1] * len(ns) for i in range(3)]
    def search(i, step):
        #print(i, step, n_steps)
        j = step % 3
        if n_steps[j][i] == -1 or (n_steps[j][i] > step):
            n_steps[j][i] = step
            for next in ns[i]:
                search(next, step+1)

    search(s, 0)
    if n_steps[0][t] == -1:
        print(-1)
    else:
        print(n_steps[0][t] // 3)

def main():
    n,v = words(int)
    ns = [[] for _ in range(n)]
    for _ in range(v):
        (st,end) = map(int,input().split())
        ns[st-1].append(end - 1)
    s,t = words(int)
    dfs(ns,s-1,t-1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
uv = []
for i in range(M):
    uv.append(list(map(int, input().split())))
S, T = map(int, input().split())

def getcount():
    now = S
    count = 0
    for m in range(M):
        for i in range(3):
            next_list = [i for i, x in enumerate([x[0] for x in uv]) if x == now]
            next = uv[next_list[0]][1]
            now = next
        count += 1
        if now == T:
            print(count)
            return True
            
    print(-1)
    return False

getcount()

Submission status: Runtime Error

Solution code:
# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
import numpy as np
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
UV = np.array([input().split() for _ in range(M)], dtype=np.int32)
U = UV[:,0] * 3
V = UV[:,1] * 3
S,T = map(int,input().split())

rows = np.concatenate([U, U+1, U+2])
cols = np.concatenate([V+1, V+2, V])

graph = csr_matrix((np.ones_like(rows), (rows, cols)), (3*N+3, 3*N+3))
dist = csgraph.dijkstra(graph, indices = 3*S)

answer = -1 if dist[3*T] > 3*N else int(dist[3*T]//3)
print(answer)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
uv = []
for i in range(M):
    uv.append(list(map(int, input().split())))
S, T = map(int, input().split())

print('-'*10)
print(N,M)
print(uv)
print(S,T)

print('-'*10)
def getcount():
    now = S
    count = 0
    for m in range(M):
        for i in range(3):
            next_list = [i for i, x in enumerate([x[0] for x in uv]) if x == now]
            next = uv[next_list[0]][1]
            now = next
        count += 1
        if now == T:
            print(count)
            return True
            
    print(-1)
    return False

getcount()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
u,v = [0]*m,[0]*m
for i in range(m):
    u[i],v[i] = map(int,input().split())
s,t = map(int,input().split())
ans = 0

for i in range(m-1):
    s = v[u.index(v[u.index(v[u.index(s)])])]
    ans += 1
    if s == t:
        print(ans)
        break
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
import itertools

N, M = map(int, input().split())
nexts = dict()
nexts_rev = dict()
for _ in range(M):
    u, v = map(int, input().split())
    nexts.setdefault(u, [])
    nexts[u].append(v)
    nexts_rev.setdefault(v, [])
    nexts_rev[v].append(u)
S, T = map(int, input().split())
if S not in nexts.keys():
    print(-1)
    sys.exit()
dist = 0
dists = [-1] * 3
queue = [S]
while len(queue) > 0:
    next_queue = []
    for n in queue:
        if n == T:
            m = dist % 3
            if m == 0:
                print(dist // 3)
                sys.exit()
            elif dists[m] == -1:
                dists[m] = dist
        else:
            next_queue.extend(nexts[n])
    if dists[1] > 0 and dists[2] > 0:
        break
    queue = next_queue
    dist += 1

if T not in nexts_rev.keys():
    print(-1)
    sys.exit()
dist = 0
dists_rev = [-1] * 3
queue = [T]
while len(queue) > 0:
    next_queue = []
    for n in queue:
        if n == S:
            m = dist % 3
            if dists_rev[m] == -1:
                dists_rev[m] = dist
        else:
            next_queue.extend(nexts_rev[n])
    if dists_rev[1] > 0 and dists_rev[2] > 0:
        break
    queue = next_queue
    dist += 1

ans = -1
if dists[1] > 0 and dists_rev[1] > 0:
    a = (dists[1] * 2 + dists_rev[1]) // 3
    ans = max(ans, a)
if dists[2] > 0 and dists_rev[2] > 0:
    a = (dists[2] * 2 + dists_rev[2]) // 3
    ans = max(ans, a)
print(ans)

Submission status: Runtime Error

Solution code:
import copy

class Node:
    def __init__(self, i):
        self.num = i
        self.goto = []
        self.kenken = set()

N, M = map(int, input().split())
nodes = [Node(i+1) for i in range(N)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    nodes[v].goto.append(nodes[u])

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

for i in range(N):
    for next in nodes[i].goto:
        for nextnext in next.goto:
            nodes[i].kenken = nodes[i].kenken | set(nextnext.goto)
    if nodes[i] in nodes[i].kenken:
        nodes[i].kenken.remove(nodes[i])

node = nodes[t]
step = 0
prev = []
check_list = [[node, step, prev]]
ok = False
while len(check_list) > 0:
    node, step, tmp = check_list.pop(0)
    prev = copy.deepcopy(tmp)
    if node == nodes[s]:
        print(step)
        ok = True
        break
    for next in node.kenken:
        if next not in prev:
            check_list.append([next, step+1, prev+[next]])
if not ok:
    print(-1)

Submission status: Runtime Error

Solution code:
# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
import numpy as np
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
UV = np.array([input().split() for _ in range(M)], dtype=np.int32)
U = UV[:,0]
V = UV[:,1]
S,T = map(int,input().split())
if M == 0:
  print(-1)
  exit()
rows = np.concatenate([3*U, 3*U+1, 3*U+2])
cols = np.concatenate([3*V+1, 3*V+2, 3*V])

graph = csr_matrix((np.ones_like(rows), (rows, cols)), (3*N+3, 3*N+3))
dist = csgraph.dijkstra(graph, indices = 3*S)

answer = -1 if dist[3*T] > 3*N else int(dist[3*T]//3)
print(answer)

Submission status: Runtime Error

Solution code:
N,M = list(map(int, input().split()))
UV = [list(map(int, input().split())) for _ in range(M)]
S,T = list(map(int, input().split()))

adjucent_dict={}
for u,v in UV:
  adjucent_dict.setdefault(u,set()).add(v)
  #adjucent_dict.setdefault(v,set()).add(u)
  
two_adjucent_dict={}
for u in adjucent_dict.keys():
  vs = [adjucent_dict[v] for v in adjucent_dict[u] if v in adjucent_dict]
  if vs:
    two_adjucent_dict[u] = set.union(*vs)
    
#print(adjucent_dict)
#print(two_adjucent_dict)
three_adjucent_dict={}
for u in adjucent_dict.keys():
  vs = [adjucent_dict[v] for v in two_adjucent_dict[u] if v in adjucent_dict]
  if vs:
    three_adjucent_dict[u] = set.union(*vs)

visited=set([S])
just_visited=set([S])
n=1
while True:
  three_step = set.union(*[three_adjucent_dict[u] for u in just_visited if u in three_adjucent_dict])
  just_visited = three_step - visited
  if T in just_visited:
    print(n)
    break
  if len(just_visited)==0:
    print(-1)
    break
    
  visited = visited & just_visited
  n+=1

Submission status: Runtime Error

Solution code:
def main():
  from heapq import *
  import sys
  input=sys.stdin.readline
  N,M=map(int,input().split())
  G=[set() for i in range(N)]
  for i in range(M):
      u,v=map(int,input().split())
      u,v=u-1,v-1
      G[u].add(v)
  S,T=map(int,input().split())
  A=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          A[i]=A[i] | G[v]
  B=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          B[i]=B[i] | A[v]
  C=[[] for i in range(N)]
  for i in range(N):
      for j in B[i]:
          C[i].append([j,1])
  INF=10**9+7
  def dijkstra(G,s):

    d=[INF]*N
    d[s]=0
    visited={s}
    que=[(0,s)]
    while(que):
      p=heappop(que)
      v=p[1]
      visited.add(v)
      for node,cost in G[v]:
        if (node not in visited) and d[node]>d[v]+cost:
          d[node]=d[v]+cost
          heappush(que,(d[node],node))
    return d
  d=dijkstra(C,S-1)
  if d[T-1]==INF:
    print(-1)
  else:
    print(d[T-1])
if __name__=='__main__':#おまじない
  main()

Submission status: Runtime Error

Solution code:
# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
import numpy as np
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
UV = np.array([input().split() for _ in range(M)], dtype=np.int32)
U = UV[:,0]
V = UV[:,1]
S,T = map(int,input().split())

rows = np.concatenate([3*U, 3*U+1, 3*U+2])
cols = np.concatenate([3*V+1, 3*V+2, 3*V])

graph = csr_matrix((np.ones_like(rows), (rows, cols)), (3*N+3, 3*N+3))
dist = csgraph.dijkstra(graph, indices = 3*S)

answer = -1 if dist[3*T] > 3*N else int(dist[3*T]//3)
print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque


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

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

    converted_edges = [[] for _ in range(N)]
    for v, v_edge in enumerate(edges):
        three_steps_nodes = []
        for w in edges[v]:
            for x in edges[w]:
                for y in edges[x]:
                    three_steps_nodes.append(y)
        converted_edges[v] = three_steps_nodes.copy()

    S, T = map(lambda x: int(x) - 1, input().split())
    q = deque([(S, 0)])

    nodes = [-1] * N

    while q:
        cv, count = q.popleft()
        if cv == T:
            if nodes[cv] == -1:
                nodes[cv] = count
            else:
                nodes[cv] = min(nodes[cv], count)
        else:
            if nodes[cv] == -1 or count < nodes[cv]:
                nodes[cv] = count
                for u in converted_edges[cv]:
                    q.append((u, count + 1))

    print(nodes[T])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import itertools

N, M = map(int, input().split())
nexts = dict()
nexts_rev = dict()
for _ in range(M):
    u, v = map(int, input().split())
    nexts.setdefault(u, [])
    nexts[u].append(v)
    nexts_rev.setdefault(v, [])
    nexts_rev[v].append(u)
S, T = map(int, input().split())
if S not in nexts.keys():
    print(-1)
    sys.exit()
dist = 0
dists = [-1] * 3
queue = [S]
while len(queue) > 0:
    next_queue = []
    for n in queue:
        if n == T:
            m = dist % 3
            if m == 0:
                print(dist)
                sys.exit()
            elif dists[m] == -1:
                dists[m] = dist
        else:
            next_queue.extend(nexts[n])
    queue = next_queue
    dist += 1

if T not in nexts_rev.keys():
    print(-1)
    sys.exit()
dist = 0
dists_rev = [-1] * 3
queue = [T]
while len(queue) > 0:
    next_queue = []
    for n in queue:
        if n == S:
            m = dist % 3
            if dists_rev[m] == -1:
                dists_rev[m] = dist
        else:
            next_queue.extend(nexts[n])
    queue = next_queue
    dist += 1

ans = -1
if dists[1] > 0 and dists_rev[1] > 0:
    a = (dists[1] * 2 + dists_rev[1]) // 3
    ans = max(ans, a)
if dists[2] > 0 and dists_rev[2] > 0:
    a = (dists[2] * 2 + dists_rev[2]) // 3
    ans = max(ans, a)
print(ans)