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:
import queue as q

def main():
    N, M = list(map(int, input().split()))
    D = {}
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        D.setdefault(u, set()).add(v)

    S, T = list(map(int, input().split()))
    S -= 1
    T -= 1
    print(f(D, S, T, M))

def f(D, S, T, M):
    close = [set(), set(), set()]
    Q = [None] * (10 ** 9)
    index = 0
    end = 1
    Q[0] = (S, 0, 0)

    while end > index:
        p, c, l = Q[index]
        index += 1
        if l == 0 and p == T:
            return c
        close[l].add(p)

        ns = D.setdefault(p, set())
        l, c = (l + 1) % 3, c + (l + 1) // 3
        for n in ns:
            if n in close[l]:
                continue
            Q[end] = (n, c, l)
            end += 1
    return -1

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
E=[list(map(int,input().split())) for i in range(M)]
S,G=map(int,input().split())

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

for x,y in E:
    ELIST[x].append(y)


DIS=[-1]*(N+1)
from collections import deque
DIS[S]=0
S=deque([S])

SA=[0]
while S:
    x=S.pop()
    NEWS=deque()

    for to in ELIST[x]:
        if DIS[to]==-1:
            DIS[to]=i
            NEWS.append(to)
        if DIS[to]<i:
            SA.append(i-to)
        

    i+=1
    S=NEWS

if DIS[G]==-1:
    print(-1)
else:
    SA.sort()
    for s in SA:
        if (DIS[G]+s)%3==0:
            print((DIS[G]+s))

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
if M == 0:
    print(-1)
    sys.exit()

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n

    def get_root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.get_root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self.get_root(x) == self.get_root(y)

    def union(self, x, y):
        r1 = self.get_root(x)
        r2 = self.get_root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2

#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

# ダイクストラ
import heapq

class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


edge = [[] for i in range(N)]
ins = UnionFind(N)


for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    route_map[u][v] = 1
    edge[u].append([1,v])
    edge[v].append([1,u])
    ins.union(u, v)

S, T = map(int, input().split())
if ins.find(S-1, T-1) == False:
    print(-1)
    sys.exit()

# ゴールまでの最短経路
dijkstra_result = Dijkstra(route_map, S - 1、T-1).execute()

if dijkstra_heap(S-1)[T-1]%3 == 0:
    print(dijkstra_heap(S-1)[T-1]//3)
else:
    for x in dijkstra_result:
        for y in range(N):
            if route_map[x][y] == route_map[y][x]:
                break
            else:
                print(-1)
                sys.exit()
    print(dijkstra_heap(S-1)[T-1]//3+1)

Submission status: Runtime Error

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1) and i %3 == 0:
               v = i
            elif (not used[i]) and d[i] < d[v] and i %3 == 0:
                v = i
        if v = -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n,w = map(int,input().split()) #n:頂点数　w:辺の数

cost = [[float("inf") for i in range(n+1)] for i in range(n+1)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y = map(int,input().split())
    cost[x-1][y-1] = 1
s,t = list(map(int, input().split()))

ans = dijkstra(s-1,n,w,cost)
print(ans)
if ans[t-1] %3 == 0:
    print(ans[t-1])

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 hop3(n1):
    n2 = np.dot(n1, conn)
    n3 = np.dot(n2, conn)
    return np.dot(n3, conn)


ans = 1
n = np.zeros((M + 1, 1))
n[S, 1] = 1

while True:
    m = hop3(n)
    if (n == m).all():
        break
    if m[T] != 0:
        print(ans)
        exit()
    ans += 1
    n = m
print(-1)

Submission status: Runtime Error

Solution code:
import re
import numpy as np
from scipy.sparse import lil_matrix, csr_matrix

N, M = [int(i) for i in re.split(" ", input())]
G = lil_matrix((N, N), dtype=np.bool)

for i in range(M):
    u, v = [int(i) for i in re.split(" ", input())]
    G[u-1, v-1] = True
G = G.tocsr()
G = G.dot(G).dot(G)

S, T = [int(i) for i in re.split(" ", input())]

count = -1
G_tmp = G
for i in range(1, len(G)):
    if i == 1:
        pass
    else:
        G_tmp = G_tmp.dot(G)
    if G_tmp[S-1, T-1]:
        count = i
        break

print(count)

Submission status: Runtime Error

Solution code:


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


ans = [10**5]
graph = [[] for j in range(N)]
for i in range(M):
    graph[uv[i][0]-1].append([uv[i][0]-1,uv[i][1]-1])

#graphにはインデックス

visit = [0]*N
trace_count = 0

now_pos = S-1

# print(graph)

def dfs(now_pos,visit,trace_count,ans):
    # print(ans,visit,trace_count)

    if now_pos == T-1:
        # print(trace_count)
        if trace_count%3 == 0:
            if ans[0]>trace_count//3:
                ans[0]= trace_count//3
                # print(ans)
    if visit[now_pos]>=3:
        return
    

    for node in graph[now_pos]:
        visit[node[1]] += 1
        
        dfs(node[1],visit,trace_count+1,ans)

        visit[node[1]] -= 1

    return








if M != 0:
    dfs(now_pos,visit,trace_count,ans)


if ans[0] == 10**5:
    ans[0] = -1


print(ans[0])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split(' '))

if m == 0:
  ans = -1
else:
  edge = []
  for _ in range(m):
    u, v = map(int, input().split(' '))
    edge.append([u, v])
  s, t = map(int, input().split(' '))

  next = {}  # make graph
  th_next = {}
  for i in range(1, n+1):
    next[i] = []
    th_next[i] = []
  for u,v in edge:
    next[u].append(v)
    th_next[u].append(v)

  for _ in range(2):
    for i in range(1, n+1):
      edges = th_next[i]
      if len(edges) == 0:
        break
      else:
        new = []
        for e in edges:
          new = list(set(new + next[e]))
        th_next[i] = new
    
  pos = s  # search
  ans = 0
  while True:
    if pos == t:  # arrive
      break
    if pos == s and ans > 0:
      ans = -1
      break
    else:
      pos = th_next[pos][0]
      ans += 1

print(ans)

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 = []
def dfs(u, path, num, dis):
    global ans
    path += str(u)
    if len(path) == 4 and d[path] != 0:
        ans.append(10**5)
        return

    if u == T and num % 3 == 0:
        ans.append(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 len(ans) == 0:
    print(-1)
else:
    a = min(ans)
    if a == 10**5:
        print(-1)
    else:
        print(a)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 29 20:53:20 2019

@author: Yamazaki Kenichi
"""
from collections import deque
import sys

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

Ta = [[] for i in range(N+1)]
for c in uv:
    Ta[c[0]].append(c[1])

counta = 0
rout = [[] for i in range(N+1)]
while len(rout[S]) < 3:
    next_ = deque([S])
    for i in range(3):
        for j in range(len(next_)):
            tmp = next_.popleft()
            for k in Ta[tmp]:
                next_.append(k)
            rout[tmp].append(i)
        
        if rout[T].count(2) >= 1:
            print(counta)
            sys.exit()
        counta += 1
print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

def kkp(array: np.ndarray, s):
    dst = np.hstack((array[array[:,0]==s,1], array[array[:, 1] == s, 0]))
    return list(set(dst))

def kkp3(steplist, idx):
    dst = []
    state = idx

    state = steplist[state]
    temp = []
    for s1 in state:
        temp.extend(steplist[s1-1])
    state = list(set(temp))
    temp = []
    for s1 in state:
        temp.extend(steplist[s1-1])
    state = list(set(temp))
    return state


n, m = map(int, input().split())
uv = []
for i in range(m):
    temp = list(map(int, input().split()))
    temp.sort()
    uv.append(temp)
s, t = map(int, input().split())

uv_np = np.asarray(uv)

steplist = []*n

steplist = [kkp(uv_np, i+1) for i in range(n)]

cnt = 0
flag = True
state = [s]
check = []
while flag:
    cnt += 1
    temp = []
    for s in state:
        temp.extend(kkp3(steplist, s-1))
    state = list(set(temp))
    if t in state:
        print(cnt)
        break
    else:
        for s in state:
            if not(s in check):

                check.extend(state)
                check = list(set(check))
                break
            flag = False
if flag is False:
    print(-1)

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
        m = d[now]
        for v in m:
            if v != T:
                if go(v, num + 1, ans, flag) == -1:
                    li += 1
        if li == len(m):
            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
N, M = map(int, input().split())
if M == 0:
    print(-1)
    sys.exit()

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n

    def get_root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.get_root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self.get_root(x) == self.get_root(y)

    def union(self, x, y):
        r1 = self.get_root(x)
        r2 = self.get_root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2

#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

# ダイクストラ
import heapq

class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


edge = [[] for i in range(N)]
ins = UnionFind(N)


for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    route_map[u][v] = 1
    edge[u].append([1,v])
    edge[v].append([1,u])
    ins.union(u, v)

S, T = map(int, input().split())
if ins.find(S-1, T-1) == False:
    print(-1)
    sys.exit()

# ゴールまでの最短経路
dijkstra_result = Dijkstra(route_map, s - 1、t-1).execute()

if dijkstra_heap(S-1)[T-1]%3 == 0:
    print(dijkstra_heap(S-1)[T-1]//3)
else:
    for x in dijkstra_result:
        for y in range(N):
            if route_map[x][y] == route_map[y][x]:
                break
            else:
                print(-1)
                sys.exit()
    print(dijkstra_heap(S-1)[T-1]//3+1)

Submission status: Runtime Error

Solution code:


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


ans = [10**5]
graph = [[] for j in range(N)]
for i in range(M):
    graph[uv[i][0]-1].append([uv[i][0]-1,uv[i][1]-1])

#graphにはインデックス

visit = [0]*N
trace_count = 0

now_pos = S-1

# print(graph)

def dfs(now_pos,visit,trace_count,ans):
    # print(ans,visit,trace_count)

    if now_pos == T-1:
        # print(trace_count)
        if trace_count%3 == 0:
            if ans[0]>trace_count//3:
                ans[0]= trace_count//3
                # print(ans)
    if visit[now_pos]>=3:
        return
    

    for node in graph[now_pos]:
        visit[node[1]] += 1
        
        dfs(node[1],visit,trace_count+1,ans)

        visit[node[1]] -= 1

    return









dfs(now_pos,visit,trace_count,ans)


if ans[0] == 10**5:
    ans[0] = -1


print(ans[0])

Submission status: Runtime Error

Solution code:
import os
import sys
from collections import defaultdict

import numpy as np
from functools import lru_cache

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 = np.zeros((N + 1, N + 1), dtype=bool)
for u, v in UV:
    graph[u][v] = True


@lru_cache(maxsize=None)
def dest(v, count):
    if count <= 1:
        return graph[v]
    ret = np.zeros((N + 1), dtype=bool)
    for u in np.where(graph[v])[0]:
        ret |= dest(u, count - 1)
    return ret


checked = np.zeros(N + 1, dtype=bool)
vs = np.zeros(N + 1, dtype=bool)
vs[S] = True
i = 0
prev = 0
while True:
    i += 1
    s = np.zeros(N + 1, dtype=bool)
    for v in np.where(vs)[0]:
        s |= dest(v, 3)
    checked |= vs
    if s[T]:
        print(i)
        break
    if checked.sum() == prev:
        print(-1)
        break
    vs = s ^ checked
    prev = checked.sum()

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=bool)
for _ in range(M):
    u, v = map(int, input().split())
    conn[u, v] = True
S, T = map(int, input().split())


def hop3(n1):
    n2 = np.dot(n1, conn)
    n3 = np.dot(n2, conn)
    return np.dot(n3, conn)


ans = 1
n = np.zeros(M + 1, dtype=bool)
n[S] = True

while True:
    m = hop3(n)
    if (n == m).all():
        break
    if m[T] != 0:
        print(ans)
        exit()
    ans += 1
    n = m
print(-1)

Submission status: Runtime Error

Solution code:
import heapq
def sol(inp=input):
    n,m=map(int,inp().split())
    G={i+1:set() for i in range(n)}
    for _ in range(m):
        i,j=map(int,inp().split())
        G[i].add((j,1))
    s,t=map(int,inp().split())
    cache_kenken={}
    def kenkenpa(v):
        for v1,l1 in tuple(G[v]):
            if l1==1:
                for v2,l2 in tuple(G[v1]):
                    if l1+l2==3:
                        yield v2
                        continue
                    else:
                        G[v].add((v2,l1+l2))
                        for v3,l3 in G[v2]:
                            G[v1].add((v3,l2+l3))
                            yield v3
                            continue
            if l1==2:
                for v2,l2 in G[v1]:
                    if l1+l2==3:
                        yield v2
                        continue
        
    visited={s}
    revisited=set()
    v_steps=[]
    visited_pa={s}
    que=[]
    heapq.heappush(que,(0,s))
    while len(que)>0:
        step,u=heapq.heappop(que)
        for v in kenkenpa(u):
            if v not in visited:
                visited.add(v)
                v_steps.append((step+1,v))
                heapq.heappush(que,(step+1,v))
            if v==t:
                return step+1
            if v not in visited:
                visited.add(v)
    return -1
print(sol())

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 hop3(n1):
    n2 = np.dot(n1, conn)
    n3 = np.dot(n2, conn)
    return np.dot(n3, conn)


ans = 1
n = np.zeros(M + 1)
n[S] = 1

while True:
    m = hop3(n)
    if (n == m).all():
        break
    if m[T] != 0:
        print(ans)
        exit()
    ans += 1
    n = m
print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

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

next = np.zeros((N, N))

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

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

next = np.dot(next, np.dot(next, next))
for i in range(N):
    next[i][i] = 0

now = t
step = 0
hist = [t]
check_list = [[now, step, hist]]
ok = False
while len(check_list) > 0:
    now, step, tmp = check_list.pop(0)
    hist = tmp
    if now == s:
        print(step)
        ok = True
        break
    for i in range(N):
        if next[i][now] > 0:
            check_list.append([i, step+1, hist+[i]])
if not ok:
    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: 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 numpy as np
class AdjDiGraph:
     def __init__(self,g):
          lines = g.split("\n")
          self.size = int(lines[0])+1 
          self.matrix = 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.matrix,self.matrix),self.matrix)
     def connect(self, x, y):
          self.connect1(x,y)            
     def connect1(self, x, y):
          self.matrix[x][y] = 1
     def connected(self,x,y):
          return self.matrix[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:
6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6

Submission status: Runtime Error

Solution code:
import re
import numpy as np

N, M = [int(i) for i in re.split(" ", input())]
G = np.zeros((N, N)).astype(np.bool)

for i in range(M):
    u, v = [int(i) for i in re.split(" ", input())]
    G[u-1, v-1] = True

G = G.dot(G).dot(G)

S, T = [int(i) for i in re.split(" ", input())]

count = -1
G_tmp = np.eye(N, dtype=np.bool)
for i in range(1, len(G)):
    G_tmp = G_tmp.dot(G)
    if G_tmp[S-1, T-1]:
        count = i
        break

print(count)

Submission status: Runtime Error

Solution code:
import sys
import itertools

N, M = map(int, input().split())
nexts = dict()
for _ in range(M):
    u, v = map(int, input().split())
    nexts.setdefault(u, [])
    nexts[u].append(v)
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.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])
    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)