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 sys
from collections import deque

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  roads0 = [[] for _ in range(n)]
  roads1 = [[] for _ in range(n)]
  roads2 = [[] for _ in range(n)]
  
  for i in range(m):
    u, v = map(int, input().split())
    roads0[u-1].append(v-1)
    roads1[u-1].append(v-1)
    roads2[u-1].append(v-1)
    
  ans = 100000000
  
  s, t = map(int, input().split())
  not_yet = deque([])
  already = [[False]*3 for _ in range(n)]
  dist = [[0]*3 for _ in range(n)]
  for v in roads0[s-1]:
    not_yet.append((v, 1))
    dist[v][1] = 1
    already[v][1] = True
  already[s-1][0] = True
  while not_yet:
    key = not_yet.pop()
    k1, k2 = key[0], key[1]
    if k2 == 0:
      for v in roads1[k2]:
        if already[v][1]:
          continue
        dist[v][1] = dist[k1][0]+1
        already[v][1] = True
        not_yet.append((v, 1))
    elif k2 == 1:
      for v in roads2[k2]:
        if already[v][2]:
          continue
        dist[v][2] = dist[k1][1]+1
        already[v][2] = True
        not_yet.append((v, 2))
    else:
      for v in roads3[k2]:
        if already[v][0]:
          continue
        dist[v][0] = dist[k1][2]+1
        already[v][0] = True
        not_yet.append((v, 0))
  if already[t-1][0]:
    print(dist[t-1][0])
  else:
    print(-1)

    
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import sys
n,M=map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(M):
    u,v = [int(i) for i in input().split()]
    G[v-1].append(u-1)
s,t=map(lambda x:int(x)-1,input().split())
m = [-1 for _ in range(n)]
m2 = [-1 for _ in range(n)]
m[t] = 0
m2[t] = 0
cnt=0
while True:
    for i in range(n):
        if i == s and m[i]%3==0:
            print(m[i]//3)
            sys.exit()
            
        for j in G[i]:
            if m[i] != -1:
                m2[j] = m[i] + 1
    m = m2.copy()
    cnt += 1
    if cnt > n*5:
        print(-1)
        sys.exit()

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
n,M=map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(M):
    u,v = [int(i) for i in input().split()]
    G[v-1].append(u-1)
s,t=map(lambda x:int(x)-1,input().split())
m = [-1 for _ in range(n)]
m2 = [-1 for _ in range(n)]
m[t] = 0
m2[t] = 0
cnt=0
while True:
    for i in range(n):
        if i == s and m[i]%3==0:
            print(m[i]//3)
            sys.exit()
            
        for j in G[i]:
            if m[i] != -1:
                m2[j] = m[i] + 1
    m = m2.copy()
    cnt += 1
    if cnt > n*M:
        print(-1)
        sys.exit()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
from collections import deque

def solve(N: int, M: int, edges, S: int, T: int):
    S -= 1
    T -= 1
    now = [S]
    seen = [False for _ in range(N)]
    c = 0
    while now:
        c += 1
        next = []
        for n in now:
            seen[n] = True
            for nz in edges[n].nonzero()[0]:
                if nz == T:
                    print(c)
                    exit()
                if not seen[nz]:
                    next.append(nz)
        now = next
    print(-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Mat = np.zeros((N, N))
    for _ in range(M):
        u, v = int(next(tokens)) - 1, int(next(tokens))-1
        Mat[u][v] = 1
        #Mat[v][u] = 1


    Three = np.copy(Mat)
    for _ in range(2):
        Three = Three.dot(Mat)

    #print(Three)

    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, Three, S, T)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, M: int, edges, S: int, T: int):
    S -= 1
    T -= 1
    now = np.zeros(10**5)
    now[S] = 1
    seen = now > 0
    c = 0
    s = 0
    while s < np.count_nonzero(seen):
        c += 1
        s = np.count_nonzero(seen)
        now = now.dot(edges)
        if now[T]:
            print(c)
            sys.exit(0)
        seen |= (now > 0)
    print(-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Mat = np.zeros((10**5, 10**5))
    for _ in range(M):
        u, v = int(next(tokens)) - 1, int(next(tokens))-1
        Mat[u][v] = 1
        #Mat[v][u] = 1


    Three = np.copy(Mat)
    for _ in range(2):
        Three = Three.dot(Mat)

    #print(Three)

    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, Three, S, T)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, M: int, edges, S: int, T: int):
    S -= 1
    T -= 1
    now = np.zeros(N)
    now[0] = 1
    seen = now > 0
    c = 0
    s = 0
    while s < np.count_nonzero(seen):
        c += 1
        s = np.count_nonzero(seen)
        now = now.dot(edges)
        if now[T]:
            print(c)
            exit()
        seen |= (now > 0)
    print(-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Mat = np.zeros((N, N))
    for _ in range(M):
        u, v = int(next(tokens)) - 1, int(next(tokens))-1
        Mat[u][v] = 1
        #Mat[v][u] = 1


    Three = np.copy(Mat)
    for _ in range(2):
        Three = Three.dot(Mat)

    #print(Three)

    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, Three, S, T)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, M: int, edges, S: int, T: int):
    S -= 1
    T -= 1
    now = np.zeros(N)
    now[0] = 1
    seen = now > 0
    c = 0
    s = 0
    while s < np.count_nonzero(seen):
        c += 1
        s = np.count_nonzero(seen)
        now = now.dot(edges)
        if now[T]:
            print(c)
            exit()
        seen |= now > 0
    print(-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Mat = np.zeros((N, N))
    for _ in range(M):
        u, v = int(next(tokens)) - 1, int(next(tokens))-1
        Mat[u][v] = 1
        #Mat[v][u] = 1


    Three = np.copy(Mat)
    for _ in range(2):
        Three = Three.dot(Mat)

    #print(Three)

    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, Three, S, T)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from queue import Queue
N, M = map(int, input().split())
INF = -1
dist = [INF]*N*3
dist = np.array(dist).reshape(N, 3)
vector = np.zeros((N, N))

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1, graf2-1] = 1
S, T = map(int, input().split())
S, T = S-1, T-1

# BFS
dist[S][0] = 0
q = Queue(3*N+1)
q.put((S, 0))
while not q.empty():
    v, l = q.get()
    for i in range(N):
        if vector[v][i] != 1:
            continue
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        q.put((i, new_l))

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

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import deque
N, M = map(int, input().split())
INF = 100000
dist = [INF]*N*3
dist = np.array(dist).reshape(N, 3)
vector = np.zeros((N, N))

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1, graf2-1] = 1
S, T = map(int, input().split())
S, T = S-1, T-1

# BFS
dist[S][0] = 0
queue = deque()
queue.append((S, 0))
while len(queue) > 0:
    v, l = queue.popleft()
    for i in range(N):
        if vector[v][i] != 1:
            continue
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        queue.append((i, new_l))

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
edge = [[] for i in range(n*3)]
#edge[i] : iから出る道の[行先]の配列
for i in range(m):
    x,y = map(int,input().split())
    x-=1;y-=1
    x*=3;y*=3
    edge[x  ].append(y+1)
    edge[x+1].append(y+2)
    edge[x+2].append(y  )
    
def dfs(s,g,res,visited):
  visited[s]=1
  if s==g or s==g+1 or s==g+2:
    if res%3==0:
      return res//3
  
  if 0 not in visited:
    return float("inf")
  
  l=float("inf")
  for i in edge[s]:
    if visited[i]==0:
      l=min(l,dfs(i,g,res+1,visited))
  return l

s,t=map(int,input().split())
s-=1;t-=1
ans=dfs(s*3,t*3,0,[0]*(n*3))
if ans==float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
edge = [[] for i in range(n*3)]
#edge[i] : iから出る道の[行先]の配列
for i in range(m):
    x,y = map(int,input().split())
    x-=1;y-=1
    x*=3;y*=3
    edge[x  ].append(y+1)
    edge[x+1].append(y+2)
    edge[x+2].append(y  )
    
def dfs(s,g,res,visited):
  if s==g or s==g+1 or s==g+2:
    if res%3==0:
      return res//3
  
  if len(visited)>3*n:
    return float("inf")
  
  if edge[s]==[]:
    return float("inf")
  
  l=float("inf")
  for i in edge[s]:
    if i not in visited:
      l=min(l,dfs(i,g,res+1,visited+[i]))
  return l

s,t=map(int,input().split())
s-=1;t-=1
ans=dfs(s*3,t*3,0,[])
if ans==float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n,m=map(int,input().split())
edge = [[] for i in range(n*3)]
#edge[i] : iから出る道の[行先]の配列
for i in range(m):
    x,y = map(int,input().split())
    x-=1;y-=1
    x*=3;y*=3
    edge[x  ].append(y+1)
    edge[x+1].append(y+2)
    edge[x+2].append(y  )
    
def dfs(s,g,res):
  #print(s,g,res)
  if s==g or s==g+1 or s==g+2:
    if res%3==0:
      return res//3
  
  if res>n+m:
    return float("inf")
  
  if edge[s]==[]:
    return float("inf")
  
  l=float("inf")
  for i in edge[s]:
    l=min(l,dfs(i,g,res+1))
  return l

s,t=map(int,input().split())
s-=1;t-=1
ans=dfs(s*3,t*3,0)
if ans==float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
from queue import PriorityQueue

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

d1 = [set() for _ in range(N+1)]
d2 = [set() for _ in range(N+1)]
d3 = [set() for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    d1[u].add(v)

for i in range(1, N+1):
    for j in d1[i]:
        d2[i] = d2[i].union(d1[j])

for i in range(1, N+1):
    for j in d1[i]:
        d3[i] = d3[i].union(d2[j])

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


class UnionFind:

    def __init__(self, N: int):
        # d[i] = <parent id> if i is a child,
        #       - <size of the group> if i is a root
        self.d = [-1 for _ in range(N)]

    def root(self, x: int) -> int:
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

    def unite(self, x: int, y: int) -> bool:
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

    def size(self, x: int):
        return -self.d[self.root(x)]

    def show(self):
        m = {}
        for n in range(len(self.d)):
            r = self.root(n)

            if r not in m:
                m[r] = [n]
            else:
                m[r].append(n)

        print("root -> childs")
        print("---------------------")
        for key in m:
            print("{} -> {}".format(key, m[key]))


class Pair:
    def __init__(self, v: int, dist: int):
        self.v = v
        self.dist = dist

    def __lt__(self, other):
        return self.dist < other.dist


uf = UnionFind(N+1)

for i in range(1, N+1):
    for j in d3[i]:
        uf.unite(i, j)

if not uf.same(S, T):
    print(-1)
    exit()

# Dijkstra method
que = PriorityQueue()
que.put(Pair(S, 0))
INF = 10**9
d = [INF]*(N+1)

d[S] = 0

while(not que.empty()):
    p: Pair = que.get()
    if (d[p.v] < p.dist):
        continue
    for e in d3[p.v]:
        if d[e] > d[p.v] + 1:
            d[e] = d[p.v] + 1
            que.put(Pair(e, d[e]))

print(d[T])

Submission status: Runtime Error

Solution code:
from collections import deque

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

s, t = map(int, input().split())
dist = [-1] * (3 * n)
queue = deque([3 * s - 3])
dist[3 * s - 3] = 0
while queue:
  vertex = queue.leftpop()
  for next_vertex in adj_list[vertex]:
    if dist[next_vertex] == -1:
      continue
    dist[next_vertex] = dist[vertex] + 1
    queue.append(next_vertex)
t_distance = dist[3 * t - 3]
if t_distance == -1:
  print(-1)
else:
  print(t_distance // 3)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import sys
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

adj = [[] for _ in range(n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v)

u = []
v = []
c = []


def dfs(start, now, depth):
    if depth == 3:
        u.append(start)
        v.append(now)
        c.append(1)
        return

    for nxt in adj[now]:
        dfs(start, nxt, depth + 1)


for i in range(n):
    dfs(i, i, 0)

graph = csr_matrix((c, (u, v)), shape=(n, n))
dist = dijkstra(graph).astype(int)
ans = dist[s-1][t-1]
if ans < 0:
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

adj = [[] for _ in range(n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v)

u = []
v = []
c = []


def dfs(start, now, depth):
    if depth == 3:
        u.append(start)
        v.append(now)
        c.append(1)
        return

    for nxt in adj[now]:
        dfs(start, nxt, depth + 1)


for i in range(n):
    dfs(i, i, 0)

graph = csr_matrix((c, (u, v)), shape=(n, n))
dist = dijkstra(graph).astype(int)
ans = dist[s-1][t-1]
if ans < 0:
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N*3+5)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v+N+1)
        adj[u+N+1].append(v+2*N+2)
        adj[u+2*N+2].append(v)

    s, t = map(int, input().split())
    que = deque()
    que.append(s)
    seen = [-1] * (N*3+5)
    seen[1] = 0
    while que:
        v = que.popleft()
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                que.append(u)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import defaultdict
from collections import deque

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

INF = 10 ** 15
# visit = [False] * ( (N + 1) * 3 )
dist  = [-1] * ( (N) * 3 + 1 )
graph_connection = defaultdict(lambda :[])
graph_cost = defaultdict(lambda :defaultdict(lambda :INF))
#
# def dfs(v,dist_before):
#
#     dist[v] = dist_before + 1
#     next_vertexs = graph_connection[v]
#     for next_v  in next_vertexs :
#         if dist[next_v] == -1:
#             dfs(next_v,dist[v])
#     return 0
#

for cost in  Cs:
    a,b= cost
    for i in range(0,3):
        from_v = a + (i) * N
        to_v = b + (i + 1) % 3 * N
        graph_connection[from_v].append(to_v )

        # from_v = b + (i) * N
        # to_v = a + (i + 1) % 3 * N
        # graph_connection[from_v].append(to_v )

# dist[S] = 0


que = deque()
#(from_v,to_v)
que.append((S,S))

while not que.empty():
    from_v, to_v = que.popleft()
    dist[to_v] = dist[from_v] + 1
    for next_v in graph_connection[to_v]:
        if dist[next_v] == -1:
            que.appendleft((to_v,next_v))
if dist[T] < 0:
    print(dist[T] )
else:
    print(dist[T]//3)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import shortest_path
def main():
    n, m = map(int, input().split())
    g = [[0]*(n*3) for _ in range(n*3)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        g[u][v+n] = 1
        g[u+n][v+2*n] = 1
        g[u+2*n][v] = 1
    s, t = map(int, input().split())
    dist = shortest_path(g, indices=s-1, method="D")
    if dist[t-1] == float('inf'):
        print("-1")
    else:
        print(int(dist[t-1])//3)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from scipy.sparse import lil_matrix
import numpy as np
from scipy.sparse.csgraph import dijkstra
n, m = map(int, input().split())
inf = 10**2
graph = [[inf for i in range(n+1)] for j in range(n+1)]
graph_new = [[inf for i in range((n+1)*3)] for j in range((n+1)*3)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u][v] = 1
    for i in range(3):
        graph_new[u*3 + i][v*3 +((i+1)%3)] = 1
start, goal = map(int, input().split())
graph = dijkstra(graph_new, indices=start*3)
if graph[goal*3] != inf:
    print(int(graph[goal*3]) // 3)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2001)
n, m = list(map(int, input().split(' ')))
path = {}  # key: index, val: nexts
passed = {}  # key: index, length % 3
for i in range(m):
    u, v = list(map(int, input().split(' ')))
    path[u] = path.get(u, []) + [v]
start, goal = list(map(int, input().split(' ')))
hoge = 9999999999999
def f(position, length, history=[]):
    key = (position, length % 3)
    if position == goal and length % 3 == 0:
        #print(position, length, history)
        #print(1, path[1])
        #print(2, path[2])
        #print(3, path[3])
        #print(4, path[4])
        #print(5, path[5])
        return length // 3
    if key not in passed:
        passed[key] = hoge
        for next in path.get(position, []):
            passed[key] = min(passed[key], f(next, length + 1, history + [next]))
    return passed[key]
ans = f(start, 0)
print(ans if ans != hoge else -1)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


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


def dfs(nodes, v):
    if nodes[0] != -1:
        if (v, 1) in G2[nodes[0]]:
            return
        G2[nodes[0]].append((v, 1))
    for u in G[v]:
        dfs(nodes[1:] + [v], u)


dfs([-1] * 3, S)
dist = dijkstra(G2, N+1, S)
print(dist[T] if dist[T] != float('inf') else -1)

Submission status: Runtime Error

Solution code:
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import shortest_path
n, m = map(int, input().split())
graph = lil_matrix((n+1,n+1), dtype=int)
for i in range(m):
    u, v = map(int, input().split())
    graph[u, v] = 1
start, goal = map(int, input().split())
graph = graph * graph * graph
k = shortest_path(graph, indices=start)
if k[goal] != float('inf'):
    print(int(k[goal]))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())  # N頂点, M辺
graph = [[] for _ in range(N)]

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

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

dist = [[-1]*3 for _ in range(N)]
dist[S][0] = 0
q = []
heappush(q, (0, S))
while len(q):
    count, v = heappop(q)  # count, ノードのIndex
    for nv in graph[v]:  # nvは次のノードの番号
        np = (count + 1) % 3
        if dist[nv][np] == -1:  # 未到達なら
            dist[nv][np] = dist[v][count] + 1
            heappush(q, (nv, np))
if dist[T][0] == -1:
    print(-1)
else:
    print(dist[T][0]//3)

Submission status: Runtime Error

Solution code:
import sys
import os
f = open('../../input.txt', 'r')
sys.stdin = f

n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s,t = map(int, input().split())

before_dict = {}
after_dict = {}
after_3 = {}

for i in range(1,n+1):
    before_dict[i] =[]
    after_dict[i] = []
    after_3[i] = []

for i in range(m):
    u, v = uv[i]
    before_dict[v].append(u)
    after_dict[u].append(v)

for i in range(m):
    u, v = uv[i]
    for j in before_dict[u]:
        for k in after_dict[v]:
            if( j != k):
                after_3[j].append(k)

from collections import deque
d = deque()
d.append(s)

length = [-1] * (n+1)
length[s] = 0

check = True

while(check):
    if(len(d) == 0):
        break
    num = d.popleft()
    for i in after_3[num]:
        if(length[i] == -1):
            length[i] = length[num] + 1
            d.append(i)

    if(length[t] > -1):
        break

print(length[t])

Submission status: Runtime Error

Solution code:
from collections import deque

N,M=map(int,input().split())
a=[set() for i in range(N)] # 0-index
for i in range(M):
    u,v=map(lambda x:int(x)-1,input().split())
    a[u].add(v)
S,T=map(lambda x:int(x)-1,input().split())
# print(a)

r=[-1 for i in range(N)]
q0=deque();q1=deque();q2=deque()
q0.append(S);r[S]=0
while q0:
    u=q0.popleft()
    for v in a[u]:
        q1.append(v)
    for w in a[v]:
        q2.append(w)
    for x in a[w]:
        if r[x]==-1:
            r[x]=r[u]+1
            q0.append(x)
# print(r)
print(r[T])

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
F = [set() for _ in range(n)]
G = np.zeros((n, n))
for _ in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  F[u].add(v)
for i in range(n):
  for j in F[i]:
    for k in F[j]:
      for l in F[k]:
        G[i][l] = 1
csr = csr_matrix(G)
s, t = map(int, input().split())
s -= 1
t -= 1
A = dijkstra(csr, indices=s)
if A[t] == float("inf"):
  print(-1)
else:
  print(int(A[t]))

Submission status: Runtime Error

Solution code:
print("reference: yaketate08")

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

graph = [[] for i in range(N + 1)]
for U, V in UV:
    graph[U].append(V)

INF = 10 ** 9

U = [[INF for _ in range(N)] for i in range(3)]
U[0][S] = 0 # S != T なのでこの表記はOK

#そうか、余りの数で最小のものを都度探す。
que = deque([(S, 0)])
while que:
    v, t = que.popleft()
    u = (t + 1) % 3
    d = U[t][v]
    if t == 2:
        d += 1
    Uu = U[u]
    for w in G[v]:
        if Uu[w] != INF:
            continue
        que.append((w, u))
        Uu[w] = d
print(U[0][T] if U[0][T] < INF else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=list(map(int,input().split()))
    g[u-1].append(v-1)
S,T=map(int,input().split())
S-=1;T-=1
INF=10**9
U=[[INF]*n for i in range(3)]
U[0][S]=0
que=deque([(0,S)])
while que:
    t,v=que.popleft()
    u=(t+1)%3
    if t==2:
        U[t][v]+=1
    for w in g[v]:
        if U[u][w]!=INF:
            continue
        que.append((u,w))
        U[u][w]=d
print(U[0][T] if U[0][T]<INF else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=list(map(int,input().split()))
    g[u-1].append(v-1)
s,t=map(int,input().split())
s-=1;t-=1
INF=10**9
U=[[INF]*n for i in range(3)]
U[0][s]=0
que=deque([s,0])
while que:
    v,t=que.pop()
    u=(t+1)%3
    d=U[u][v]
    if t==2:
        d+=1
    for w in g[v]:
        if U[u][w]!=INF:
            continue
        que.append((w,u))
        U[u][w]=d
print(U[0][t] if U[0][t]<INF else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
n,m=map(int,input.split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=list(map(int,input().split()))
    g[u-1].append(v-1)
s,t=map(int,input().split())
s-=1;t-=1
INF=10**9
U=[[INF]*n for i in range(3)]
U[0][s]=0
que=deque([s,0])
while que:
    v,t=que.pop()
    u=(t+1)%3
    d=U[u][v]
    if t==2:
        d+=1
    for w in g[v]:
        if U[u][w]!=INF:
            continue
        que.append((w,u))
        U[u][w]=d
print(U[0][t] if U[0][t]<INF else -1)

Submission status: Runtime Error

Solution code:
import numpy as np
n, m = map(int, input().split())
graph = np.zeros((n+1,n+1))
for i in range(m):
    u, v = map(int, input().split())
    graph[u][v] = 1
start, goal = map(int, input().split())
graph2 = np.zeros((n+1,n+1))
np.dot(graph,graph,out = graph2)
np.dot(graph2,graph,out = graph)
#一回けんけんぱした後のグラフがgraph
for i in range(1,n+1):
    if graph[start][goal] >= 1:
        print(i)
        exit()
    np.dot(graph,graph,out = graph)
print(-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
N, M = map(int, input().split())
G = defaultdict(list)
for _ in range(M):
    u, v = map(int, input().split())
    G[(u-1, 0)].append((v-1, 1))
    G[(u-1, 1)].append((v-1, 2))
    G[(u-1, 2)].append((v-1, 0))
S, T = map(int, input().split())
G3 = defaultdict(list)
dist = defaultdict(lambda : -1)
que = deque([(S-1, 0)])
dist[(S-1, 0)] = 0
while que:
    if v == (T-1, 0):
        break
    v = que.pop()
    d = dist[v]
    for nv in G[v]:
        if dist[nv]>=0:
            continue
        dist[nv] = d+1
        que.append(nv)
print(dist[(T-1, 0)]//3)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split(' '))

already_reach = [-1]*(N+1)
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split(' '))
    graph[u].append(v)
S,T = map(int,input().split(' '))

def search(S_list,current_count=0):
    for s in S_list:
        already_reach[s] = current_count
    #print(already_reach)
    next_list = []
    for s in S_list:
        for i1 in graph[s]:
            for i2 in graph[i1]:
                for i3 in graph[i2]:
                    if already_reach[i3] == -1: #はじめての到達
                        next_list.append(i3)
    if len(next_list) > 0:
        search(next_list,current_count+1)
search([S])
print(already_reach[T])

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
INF = 10**7
to = [ [] for _ in range(n) ]
dist = [ [INF]*n for _ in range(3) ]
for _ in range(m):
    u, v = map(int, input().split())
    to[u-1].append(v-1)
s, t = map(int, input().split())
s -= 1
t -= 1

dist[s][0] = 0
que = deque([(s, 0)])
while que:
    u, t = que.popleft()
    d = dist[t][u]
    w = (t+1) % 3
    if t == 2:
        d += 1
    for v in to[u]:
        if dist[w][v] != INF:
            continue
        que.append((v, w))
        dist[w][v] = d
print( dist[0][t] if dist[0][t] < INF else -1 )