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:
from heapq import *
f_inf = float('inf')

def dijkstra(start,node,edge):
    #始点sから各頂点への最短距離
    #node:頂点数
    #d:各頂点へのコスト(存在しないときはinf)
    #q:キュー(スタートからのコスト,頂点)
    d = [[f_inf, f_inf, f_inf] for _ in [0]*node]
    d[start][0] = 0
    #スタートをキューに入れる
    q = [(0,start)]

    while(len(q) != 0):
    #キューの先頭を取得
      ci,i = heappop(q)
    #キューの先頭から繋がっている頂点を探索
      for j in edge[i]:
        nc = ci + 1
        if (d[j][nc%3] > nc):
          d[j][nc%3] = nc
          heappush(q,(nc, j))
    return d
#入力
N,M = (int(x) for x in input().split())
#二種類のエッジ
E = [[] for _ in [0]*N]

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

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

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

n, m = map(int, input().split())
g = [[] for _ in range(3 * n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    # u0 -> v1
    g[3 * u].append(3 * v + 1)
    # u1 -> v2
    g[3 * u + 1].append(3 * v + 2)
    # u2 -> v0
    g[3 * u + 2].append(3 * v)

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

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


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

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

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

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

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

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

q = queue.Queue()
q.put((S,0))
# Deep First Serch
while q.empty() == False:
    now, cost = q.get()
    state = cost % 3
    if used[now,state] == mod:
        used[now,state] = cost
        for route in routes[now]:
            q.put((route,cost+1))

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

Submission status: Runtime Error

Solution code:
import sys
from collection import deque

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

        G[3*u].append(3*v+1)
        G[3*u+1].append(3*v+2)
        G[3*u+2].append(3*v)

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

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

                if m == T:
                    return cnt

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

        q = q_

    return -1


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

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np


N, M = map(int, input().split())
conn = np.zeros((N + 1, N + 1))
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(N + 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:
n, m = map(int, input().split())
d = {i+1 : [] for i  in range(n)}
for _ in range(m):
    u, v = map(int, input().split())
    d[u].append(v)
s, t = map(int, input().split())
q = [s]
visited = set([s])
c = 1
def solve():
    while True:
        global visited, c
        flag = True
        for i, v in enumerate(q[:]):
            q.pop(i)
            es = [e3 for e1 in d[v] for e2 in d[e1] for e3 in d[e2] if not e3 in visited]
            if len(es):
                flag = False
            if t in es:
                return c
            else:
                visited |= set(es)
                q.extend(es)
        if flag:
            return -1
        c += 1
print(solve())

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
d = {i+1 : [] for i  in range(n)}
for _ in range(m):
    u, v = map(int, input().split())
    d[u].append(v)
s, t = map(int, input().split())
q = [s]
visited = set([s])
def calc(c):
    global visited
    flag = True
    for i, v in enumerate(q[:]):
        q.pop(i)
        es = [e3 for e1 in d[v] for e2 in d[e1] for e3 in d[e2] if not e3 in visited]
        if len(es):
            flag = False
        if t in es:
            return c
        else:
            visited |= set(es)
            q.extend(es)
    if flag:
        return -1
    return calc(c + 1)
print(calc(1))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
d = {i+1 : [] for i  in range(n)}
for _ in range(m):
    u, v = map(int, input().split())
    d[u].append(v)
s, t = map(int, input().split())
q = [s]
visited = set([s])
def calc(c):
    global visited
    if len(q) == 0:
        return -1
    for i, v in enumerate(q[:]):
        q.pop(i)
        es = [e3 for e1 in d[v] for e2 in d[e1] for e3 in d[e2] if not e3 in visited]
        if t in es:
            return c
        else:
            visited |= set(es)
            q.extend(es)
    return calc(c + 1)
print(calc(1))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
G = [set() for i in range(N)]
G3 = [set() for i in range(N)]
for _ in range(M):
    s,t = map(int,input().split())
    G[s-1].add(t)
S,T = map(int,input().split())

pque = {S}
que = {S}
nque = set(), set()
ans = 0

for i in range(N):
    for s in G[i]:
        nque |= G[s-1]
    for s in nque:
        G3[i] |= G[s-1]
    G3[i] -= {S}
    nque = set()

while T not in que and len(que) != 0:
    for s in que:
        nque |= G3[s-1]

    pque |= que
    que = nque - pque
    nque = set()
    ans += 1

if len(que) == 0: ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
edge_to = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    edge_to[u-1].append(v-1)
S, T = map(int,input().split())
S -= 1
T -= 1
dest = [set() for i in range(N)]
def find_dest(i, j, cnt): #けんけんぱで行けるところ
    if cnt == 2:
        for k in edge_to[j]:
            dest[i].add(k)
        return
    for k in edge_to[j]:
        find_dest(i, k, cnt+1)
for i in range(N):
    find_dest(i, i, 0)
visited = [False for i in range(N)]
visited[S] = True
import queue
q = queue.Queue(-1)
q.put_nowait((S, 0))
while q.not_empty:
    now, cnt = q.get_nowait()
    for j in dest[now]:
        if j == T:
            print(cnt+1)
            exit(0)
        if not visited[j]:
            q.put_nowait((j, cnt+1))
            visited[j] = True
print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np


N, M = map(int, input().split())
conn = np.zeros((N + 1, N + 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((1, N + 1))
v = np.zeros((1, N + 1))
n[0, S] = 1
v += n

while True:
    m = hop3(n)

    b = np.count_nonzero(v)
    v += m
    a = np.count_nonzero(v)
    if (a == b):
        break

    if m[0, T] != 0:
        print(ans)
        exit()
    ans += 1
    n = m

print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
class AdjWeightedDiGraph:
    def __init__(self,g):
        lines = g.split("\n")
        self.size = int(lines[0])*3+3
        self.adjMatrix = np.full((self.size,self.size),float('inf'))
        for i in range(self.size):
            self.adjMatrix[i][i] = 0 # 対角成分は$0$とする。
        for s in lines[1:]:
            d1,d2 = s.split(" ")
            self.connect(3*int(d1),3*int(d2)+1)
            self.connect(3*int(d1)+1,3*int(d2)+2)
            self.connect(3*int(d1)+2,3*int(d2))
    def connect(self,x, y):
        self.adjMatrix[x][y] = 1
    def floyd(self):
        d = self.adjMatrix        # 距離行列dの初期値は隣接行列
        for k in range(self.size):   # 頂点kを経由したら短くいけるか調べる
            newd = np.copy(d)
            for i in range(self.size):
                for j in range(self.size):
                    if d[i][j] > d[i][k]+d[k][j]: # 頂点iから頂点jに行くとき頂点kを経由したら短くいけるなら、
                        newd[i][j] = d[i][k]+d[k][j] # それを新しい値とする。
            d = newd # 新しい距離行列を次の距離行列とする。
        return d

n,m=map(int,input().split())
g=[str(n),"\n"]
for i in range(m):
     g.append(input())
     g.append("\n")
graph = AdjWeightedDiGraph("".join(g[:-1]))

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


dm = graph.floyd()[3*s][3*t]
if dm==float('inf'):
     print(-1)
else:
     print(int(dm)//3)

Submission status: Runtime Error

Solution code:
import numpy as np


N, M = map(int, input().split())
conn = np.zeros((N + 1, N + 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((1, N + 1))
n[0, S] = 1

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
D = [[-1, -1, -1] for i in range(N)]
Q = [[-1, -1, -1] for i in range(M)]
if M:
  Q[0] = [S - 1, 0, RD[S - 1] % 3]
else:
  Q = [[-1, -1, -1]]
o = 0
i = 1
while Q:
  q, d, m = Q[o]
  Q[o] = [-1, -1, -1]
  o = (o + 1) % M
  if q == -1:
    break
  if RD[q] == -1:
    continue
  D[q][m] = d + RD[q]
  if m != 0:
    for adj in E[q]:
      _m = (d + 1 + RD[adj]) % 3
      if D[adj][_m] == -1:
        Q[i] = [adj, d + 1, _m]
        i = (i + 1) % M
P = [d[0] for d in D if d[0] != -1]
if P:
  print(min(P) // 3)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, i):
        self.num = i
        self.ken = set()
        self.kenken = set()
        self.kenkenpa = 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].ken.add(nodes[u])

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

for i in range(N):
    for pre in nodes[i].ken:
        nodes[i].kenken = nodes[i].kenken | pre.ken

for i in range(N):
    for prepre in nodes[i].kenken:
        nodes[i].kenkenpa = nodes[i].kenkenpa | prepre.ken

node = nodes[t]
step = 0
check_list = [[node, step]]
check = [False] * N
ok = False
while len(check_list) > 0:
    node, step = check_list.pop(0)
    for pre in node.kenkenpa:
        if pre == nodes[s]:
            print(step+1)
            ok = True
            break
        if not check[pre.num]:
            check[pre.num] = True
            check_list.append([pre, step+1])
    if ok:
        break
if not ok:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np


N, M = map(int, input().split())
conn = np.zeros((N + 1, N + 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((1, N + 1))
n[1, 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:
N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
D = [[-1, -1, -1] for i in range(N)]
Q = [[-1, -1, -1] for i in range(M)]
Q[0] = [S - 1, 0, RD[S - 1] % 3]
o = 0
i = 1
while Q:
  q, d, m = Q[o]
  Q[o] = [-1, -1, -1]
  o = (o + 1) % N
  if q == -1:
    break
  if RD[q] == -1:
    continue
  D[q][m] = d + RD[q]
  if m != 0:
    for adj in E[q]:
      _m = (d + 1 + RD[adj]) % 3
      if D[adj][_m] == -1:
        Q[i] = [adj, d + 1, _m]
        i = (i + 1) % N
P = [d[0] for d in D if d[0] != -1]
if P:
  print(min(P) // 3)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
import numpy as np


N, M = map(int, input().split())
conn = np.zeros((N + 1, N + 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(N + 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:
N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
D = [[-1, -1, -1] for i in range(N)]
Q = [[-1, -1, -1] for i in range(4 * N)]
Q[0] = [S - 1, 0, RD[S - 1] % 3]
o = 0
i = 1
while Q:
  q, d, m = Q[o]
  o += 1
  if q == -1:
    break
  if RD[q] == -1:
    continue
  D[q][m] = d + RD[q]
  if m != 0:
    for adj in E[q]:
      _m = (d + 1 + RD[adj]) % 3
      if D[adj][_m] == -1:
        Q[i] = [adj, d + 1, _m]
        i += 1
P = [d[0] for d in D if d[0] != -1]
if P:
  print(min(P) // 3)
else:
  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 kaisu==self.size:
                         return None
                    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())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
D = [[-1, -1, -1] for i in range(N)]
Q = [[-1, -1, -1] for i in range(3 * N)]
Q[0] = [S - 1, 0, RD[S - 1] % 3]
o = 0
i = 1
while Q:
  q, d, m = Q[o]
  o += 1
  if q == -1:
    break
  if RD[q] == -1:
    continue
  D[q][m] = d + RD[q]
  if m != 0:
    for adj in E[q]:
      _m = (d + 1 + RD[adj]) % 3
      if D[adj][_m] == -1:
        Q[i] = [adj, d + 1, _m]
        i += 1
P = [d[0] for d in D if d[0] != -1]
if P:
  print(min(P) // 3)
else:
  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
check_list = [[now, step]]
ok = False
check = [False] * N
check[now] = True
while len(check_list) > 0:
    now, step = check_list.pop(0)
    for i in range(N):
        if next[i][now] > 0:
            if not check[i]:
                if i == s:
                    print(step+1)
                    # print(check)
                    ok = True
                    break
                check_list.append([i, step+1])
                check[i] = True
    if ok:
        break
if not ok:
    print(-1)

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, N * M))

def f(D, S, T, W):
    close = [set(), set(), set()]
    Q = [None] * W
    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:
N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
if RD[S - 1] == -1:
  print(-1)
else:
  D = [[-1, -1, -1] for i in range(N)]
  Q = [[-1, -1] for i in range(5 * N)]
  Q[0] = [S - 1, 0]
  o = 0
  i = 1
  while Q:
    q, d = Q[o]
    o += 1
    if q == -1:
      break
    if RD[q] == -1:
      continue
    m = (d + RD[q]) % 3
    if D[q][m] != -1:
      continue
    D[q][m] = d + RD[q]
    if m != 0:
      for adj in E[q]:
        _m = (d + 1 + RD[adj]) % 3
        if D[adj][_m] == -1:
          Q[i] = [adj, d + 1]
          i += 1
  P = [d[0] for d in D if d[0] != -1]
  if P:
    print(min(P) // 3)
  else:
    print(-1)

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, N))

def f(D, S, T, N):
    close = [set(), set(), set()]
    Q = [None] * 30 * N
    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:
S, T = [int(c)-1 for c in input().split()]

reach = [[-1 for _ in range(N)] for _ in range(3)]
reach[0][S] = 0

queue={S}

time = 1
for _ in range(4*N):
    queue_new = set()
    for q in queue:
        for v in path[q]:
            if reach[time%3][v]==-1:
                reach[time%3][v]=time
        queue_new.add(v)
		
    queue = queue_new
    time += 1

if reach[0][T]==-1:
    print(-1)
else:
    print(reach[0][T]//3)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
if RD[S - 1] == -1:
  print(-1)
else:
  D = [[-1, -1, -1] for i in range(N)]
  Q = [[-1, -1] for i in range(3 * N)]
  Q[0] = [S - 1, 0]
  o = 0
  i = 1
  while Q:
    q, d = Q[o]
    o += 1
    if q == -1:
      break
    if RD[q] == -1:
      continue
    m = (d + RD[q]) % 3
    if D[q][m] != -1:
      continue
    D[q][m] = d + RD[q]
    if m != 0:
      for adj in E[q]:
        Q[i] = [adj, d + 1]
        i += 1
  P = [d[0] for d in D if d[0] != -1]
  if P:
    print(min(P) // 3)
  else:
    print(-1)

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, N))

def f(D, S, T, N):
    close = [set(), set(), set()]
    Q = [None] * 3 * N
    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
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())

path_list = [[] for _ in range(n)]

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

s, t = map(int, input().split())
s -= 1
t -= 1
i = 0
dp = [set() for _ in range(3)]
dp[0].add(s)
while i < 3*n-1:
  a = set()
  b = []
  for dot in dp[i%3]:
    b.append(path_list[dot])
  dp[(i+1)%3] |= set(b)
  if t in dp[0]:
    print(-~i//3)
    exit()
  
  i += 1
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
check_list = [[now, step]]
ok = False
check = [False] * N
while len(check_list) > 0:
    now, step = check_list.pop(0)
    if now == s:
        print(step)
        ok = True
        break
    for i in range(N):
        if next[i][now] > 0:
            if not check[i]:
                check_list.append([i, step+1])
                check[i] = True
if not ok:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys

inf = 10 ** 6

def main():
    n, m = [int(i) for i in sys.stdin.readline().strip().split()]
    edges = [tuple(int(i) for i in sys.stdin.readline().strip().split()) for j in range(m)]
    e_dict = {i: [] for i in range(1, n+1)}
    s, t = [int(i) for i in sys.stdin.readline().strip().split()]

    for a, b in edges:
        e_dict[a].append(b)

    ret = -1
    log = [(10 ** 8, 0)] * (n+1)
    que = []
    que.append((s, 0))
    log[s] = 0
    for _ in range(inf):
        if not len(que):
            break
        nod, st = que.pop(0)
        log[nod] = (st, log[nod][1]+1)
        if log[nod][1] > 3:
            break
        if nod == t and st % 3 == 0:
            ret = st // 3
            break
        for u in e_dict[nod]:
            if log[u][0] == 10**8 or log[u][0] % 3 != (st+1) % 3:
                que.append((u, st+1))
    return ret
    
print(main())