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 collections
N,M = map(int,input().split())
edge = collections.defaultdict(list)
for _ in range(M):
    u,v = map(int,input().split())
    edge[u-1].append(v-1)
S,T = map(int,fi.input().split())
dp = [-1 for _ in range(N)]
dp[S-1] = 0
q = collections.deque()
q.append(S-1)
while q:
    p = q.pop()
    for k1 in edge[p]:
        for k2 in edge[k1]:
            for k3 in edge[k2]:
                if dp[k3] == -1:
                    dp[k3] = dp[p] + 1
                    q.append(k3)
                    if k3 == T-1:
                        break
print(dp[T-1])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
VLIST = list([] for i in range(m*3))
for i in range(m):
  v1,v2 = map(int,input().split())
  v1_0 = (v1-1)*3
  v1_1 = (v1-1)*3 + 1
  v1_2 = (v1-1)*3 + 2
  v2_0 = (v2-1)*3
  v2_1 = (v2-1)*3 + 1
  v2_2 = (v2-1)*3 + 2
  VLIST[v1_0].append(v2_1)
  VLIST[v1_1].append(v2_2)
  VLIST[v1_2].append(v2_0)   
s,t = map(int,input().split())
s0 = (s-1)*3
t0 = (t-1)*3

q = []
q.extend(VLIST[s0])
d = 0
chk = [0]*len(VLIST)
dp = [0]*len(VLIST)
dp[s0] = 0
while len(q)>0:
  i = q.pop(0)
  d = dp[i]
  if chk[i]==1:
    continue
  if i==t0:
    print(int(d//3 + 1))
    exit()
  q.extend(VLIST[i])
  for j in VLIST[i]:
    dp[j] = d+1
  chk[i] = 1
print(-1)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
VLIST = list([] for i in range(m*3))
for i in range(m):
  v1,v2 = map(int,input().split())
  v1_0 = (v1-1)*3
  v1_1 = (v1-1)*3 + 1
  v1_2 = (v1-1)*3 + 2
  v2_0 = (v2-1)*3
  v2_1 = (v2-1)*3 + 1
  v2_2 = (v2-1)*3 + 2
  VLIST[v1_0].append(v2_1)
  VLIST[v1_1].append(v2_2)
  VLIST[v1_2].append(v2_0)   
s,t = map(int,input().split())
s0 = (s-1)*3
t0 = (t-1)*3

q = []
dp = []
q.extend(VLIST[s0])
dp.extend([0]*len(VLIST[s0]))
d = 0
chk = [0]*len(VLIST)
while len(q)>0:
  i = q.pop(0)
  #print(i)
  dpi = dp.pop(0)
  if chk[i]==1:
    continue
  if i==t0:
    print(int(dpi//3 + 1))
    exit()
  q.extend(VLIST[i])
  dp.extend([dpi+1]*len(VLIST[i]))
  chk[i] = 1
print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
M =np.matrix(np.zeros((m,m), dtype=np.int))

for i in range(m):
  v1,v2 = map(int,input().split())
  M[v1-1,v2-1] = 1
s,t = map(int,input().split())

M2 = M.copy()
#MAX = int(m//3) + 2
for i in range(m*3):
  M2 = M2*M >0
  #print(M2)
  if (i+2) % 3 ==0:
    if M2[s-1,t-1]>0:
      print((i+2)//3)
      exit()
print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
M =np.matrix(np.zeros((m,m), dtype=np.int8))

for i in range(m):
  v1,v2 = map(int,input().split())
  M[v1-1,v2-1] = 1
s,t = map(int,input().split())

M2 = M.copy()
#MAX = int(m//3) + 2
for i in range(m*3):
  M2 = M2*M >0
  #print(M2)
  if (i+2) % 3 ==0:
    if M2[s-1,t-1]>0:
      print((i+2)//3)
      exit()
print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
M =np.matrix(np.zeros((m,m), dtype=np.int))

for i in range(m):
  v1,v2 = map(int,input().split())
  M[v1-1,v2-1] = 1
s,t = map(int,input().split())

M2 = M.copy()
#MAX = int(m//3) + 2
for i in range(m*3):
  M2 = M2*M
  if (i+2) % 3 ==0:
    if M2[s-1,t-1]>0:
      print((i+2)//3)
      exit()
print(-1)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M, *UV, S, T = map(int, read().split())

it = iter(UV)
G = [[] for _ in range(1+N+N+N)]
for x, y = in zip(it, it):
    x1 = x + N; x2 = x1 + N;
    y1 = y + N; y2 = y1 + N;
    G[x].append(y1)
    G[x1].append(y2)
    G[x2].append(y)

INF = 10 ** 15
dist = [INF] * (N + N + N + 1)
dist[S] = 0
q = [S]
while q:
    qq = []
    for x in q:
        for y in G[x]:
            if dist[y] != INF:
                continue
            qq.append(y)
            dist[y] = dist[x] + 1
            if y == T:
                break
    q = qq

d = dist[T]

answer = -1 if d == INF else d//3
print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque

N,M=map(int,input().split())
# 頂点の番号は0-initialのまま扱う
E=set() # 辺から成るset
for i in range(M):
    u,v=map(int,input().split())
    E.add((u,v))
S,T=map(int,input().split())

d1=[set() for i in range(N+1)] # d1[i]=頂点iからの距離が1であるような頂点vから成るset
for e in E:
    u=e[0];v=e[1]
    d1[u].add(v)

d2=[set() for i in range(N+1)] # d2[i]=頂点iからの距離が2であるような頂点vから成るset
for e in E:
    u=e[0];v=e[1]
    d2[u].update(d1[v])

d3=[set() for i in range(N+1)]
for e in E:
    u=e[0];v=e[1]
    d3[u].update(d2[v])
'''
print(e)
print(d1)
print(d2)
print(d3)
'''
#dis=[-1 for i in range(N+1)];dis[S]=0 # 頂点Sからの距離
dis={S:0}
# WFS
q=deque() # 遅ければlistで実装
q.append(S)
while q:
#    print(q) #DB
#    print(dis) #DB
    u=q.popleft()
    #vs=[v for v in d3[u] if dis[v]==-1]
    vs=[v for v in d3[u] if v not in dis]
    for v in vs:
        dis[v]=dis[u]+1
        q.append(v)

print(dis[T])

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]

vs = set()
def dfs_w(v, d, t):
    # dfs while版 
    r = -1
    stack = [v]
    path = []
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            path.pop()
        else:
            path.append(v)
            vs.add(v)
            for u in d[v]:
                if u == t:
                    #print(r,path)
                    if r != -1:
                        r = min(len(path)//3, r)
                    else:
                        r = len(path)//3
                    #continue
                if u in vs:
                    continue
                stack += [-v, u]
    return r

from collections import deque
def bfs(v,d,t,N):
    queue=deque([v])
    dist = [0] * (N+1)
    while True:
        if len(queue) == 0:
            break
        v = queue.popleft()
        vs.add(v)
        for u in d[v]:
            if u in vs:
                continue
            dist[u] = dist[v] + 1
            if u == t:
                return dist[u]//3
            queue.append(u)
    return r

d = [set() for _ in range(3*N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(N+b)
    d[N+a].add(2*N+b)
    d[2*N+a].add(b)

s, t = [int(x) for x in input().strip().split(" ")]
print(bfs(s, d, t, 3*N+1))

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]

vs = set()
def dfs_w(v, d, t):
    # dfs while版 
    r = -1
    stack = [v]
    path = []
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            path.pop()
        else:
            path.append(v)
            vs.add(v)
            for u in d[v]:
                if u == t:
                    #print(r,path)
                    if r != -1:
                        r = min(len(path)//3, r)
                    else:
                        r = len(path)//3
                    #continue
                if u in vs:
                    continue
                stack += [-v, u]
    return r

from collections import deque
def bfs(v,d,t,N):
    queue=deque([v])
    dist = [0] * (N+1)
    while True:
        if len(queue) == 0:
            break
        v = queue.popleft()
        for u in d[v]:
            if u in vs:
                continue
            dist[u] = dist[v] + 1
            if u == t:
                return dist[u]//3
            queue.append(u)
    return r

d = [set() for _ in range(3*N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(N+b)
    d[N+a].add(2*N+b)
    d[2*N+a].add(b)

s, t = [int(x) for x in input().strip().split(" ")]
print(bfs(s, d, t, 3*N+1))

Submission status: Runtime Error

Solution code:
from collections import deque
N,M,*L,S,T = map(int,open(0).read().split())
G = [[] for _ in range(N)]
step = [0 for _ in range(N)]
step[(S-1)*3] = 0
for u,v in zip(*[iter(L)]*2):
	G[u-1].append(v-1)
q = deque([(S-1,0)])
while q:
	cur,d = q.popleft()
	for nxt in G[cur]:
		if nxt==T-1 and (d+1)%3==0:
			print((d+1)//3)
			exit()
		if not step[nxt] & 1<<((d+1)%3):
			step[nxt] |= 1<<(d+1)%3
			q.append((nxt,d+1))
print(-1)

Submission status: Runtime Error

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

g = {}
steps = 3
for v in range(1,N*steps+1):
    g[v] = []

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

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

visiting = [(S,0)]
visited = {}
while visiting:
    v,d = visiting.pop(0)
    if v in visited:
        continue
    visited[v] = d
    if v == T:
        break

    for v2 in g.get(v,()):
        if v2 in visiting or v2 in visited:
            continue
        visiting.append((v2,d+1))
if T in visited:
    print(visited[T] // steps)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
G = np.zeros((N,N))
for i in range(M):
    a, b = map(int, input().split())
    G[a-1, b-1] = 1
S, T = map(int, input().split())
G3 = np.dot(G, np.dot(G, G))
x = G3
count = 1
lmt = 1000
for i in range(lmt):
    if x[S-1, T-1] >= 1:
        print(count)
        break
    elif i == lmt-1:print(-1)
    else:
        count+=1
        x = np.dot(x, G3)

Submission status: Runtime Error

Solution code:
NM=list(map(int,input().split()))
N=NM[0]
M=NM[1]
graph=[[] for j in range(N)]
 
for i in range(M):
  edge=list(map(int,input().split()))
  graph[edge[0]-1].append(edge[1]-1)
  
ST=list(map(int,input().split()))
S=ST[0]-1
T=ST[1]-1
 
 
 
first=[]
second=[]
third=[]
able=set([S])
 
step=0
 
while True:
  first=[]
  second=[]
  third=[]
  judge = 0
  for i in range(len(able)):
    for j in range(len(graph[able[i]])):
      if not (graph[able[i]][j] in first):
        first.append(graph[able[i]][j])
  for i in range(len(first)):
    for j in range(len(graph[first[i]])):
      if not (graph[first[i]][j] in second):
        second.append(graph[first[i]][j])
  for i in range(len(second)):
    for j in range(len(graph[second[i]])):
      if not (graph[second[i]][j] in third):
        third.append(graph[second[i]][j])
  able=able&set(third)
  if judge == 0:
    print(-1)
    break
  step+=1
  if T in able:
    print(step)
    break

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
e = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    e[(a, 0)].append((b, 1))
    e[(a, 1)].append((b, 2))
    e[(a, 2)].append((b, 0))

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

d = deque()
d.appendleft((S, 0))

inf = float('inf')
dist = defaultdict(lambda: inf)
dist[(S, 0)] = 0

def BFS(now):
    for v in e[now]:
        if(dist[v] > dist[now] + 1):
            dist[v] = dist[now] + 1
            if(v == (T, 0)):
                return
            BFS(v)
    return

BFS((S, 0))

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

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, deq, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] < inf): continue
        dist[node] = dist[now] + 1
        deq.append(node)
    if(len(deq) > 0):
        next_node = deq.popleft()
        BST(next_node, deq, dist)
    return

deq = deque()
BST((S, 0), deq, dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, deq, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] < inf): continue
        dist[node] = dist[now] + 1
        deq.append(node)
    if(len(deq) > 0):
        next_node = deq.pop()
        BST(next_node, deq, dist)
    return

deq = deque()
BST((S, 0), deq, dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = 10 ** 10
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, deq, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] > dist[now] + 1):
            dist[node] = dist[now] + 1
            deq.append(node)
    if(len(deq) > 0):
        next_node = deq.pop()
        BST(next_node, deq, dist)
    else:
        return

deq = deque()
BST((S, 0), deq, dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict
from heapq import heappop, heappush

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = 10 ** 10
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, heap, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] > dist[now] + 1):
            dist[node] = dist[now] + 1
            heappush(heap, node)
    if(heap):
        next_node = heappop(heap)
        BST(next_node, heap, dist)
    else:
        return

heap = []
BST((S, 0), [], dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict
from heapq import heappop, heappush

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = 10 ** 10
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, heap, dist):
    for node in edge[now]:
        if(dist[node] > dist[now] + 1):
            dist[node] = dist[now] + 1
            heappush(heap, node)
    if(heap):
        next_node = heappop(heap)
        BST(next_node, heap, dist)
    else:
        return

heap = []
BST((S, 0), [], dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

def BST(now, goal, visited):
    count = 0
    for node in edge[now]:
        if(node == goal):
            return 1
        elif(not node in visited):
            visited.appendleft(node)
            temp = BST(node, goal, visited)
            if(temp == False):
                continue
            temp += 1
            visited.pop()
            if(count == 0):
                count = temp
            elif(temp < count):
                count = temp
    if(count == 0):
        return False
    else:
        return count

visited = deque()
ret = BST((S, 0), (T, 0), visited)
if(ret == False):
    print(-1)
else:
    print(ret//3)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=map(int,input().split())
A=np.zeros((N,N))
for i in range(M):
  u,v=map(int,input().split())
  A[u-1][v-1]=1
S,T=map(int,input().split())
Z=np.eye(N)
k=0
for i in range(1,10**6+1):
  Z=np.dot(Z,A)
  if Z[S-1][T-1] !=0 and i%3==0:
    print(i//3)
    break
  else:
    k=k+1
if k==10**6:
  print(-1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
alist = [[] for _ in range(n)]
for u, v in uv:
    alist[u-1].append(v-1)
s, t = map(int, input().split())

alist3 = [set([]) for _ in range(n)]
for v in range(n):
    for v1 in alist[v]:
        for v2 in alist[v1]:
            for v3 in alist[v2]:
                alist3[v].add(v3)

# BFS
queue = [s]
visited = [-1]*n
visited[s] = 0
while len(queue) > 0:
    q = queue.pop(0)
    for v in alist3[q]:
        if visited[v] < 0:
            queue.append(v)
            visited[v] = visited[q] + 1
print(visited[t])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ im range(m)]
alist = [[] for _ in range(n)]
for u, v in uv:
    alist[u].append(v)
s, t = map(int, input().split())

alist3 = [set([]) for _ in range(n)]
for u, v in uv:
for v in range(n):
    for v1 in alist[v]:
        for v2 in alist[v1]:
            for v3 in alist[v2]:
                alist3[v].add(v2)

# BFS
queue = [s]
visited = [-1]*n
visited[s] = 0
while len(queue) > 0:
    q = queue.pop(0)
    for v in alist3[q]:
        if visited[v] >= 0:
            queue.append(v)
            visited[v] = visited[q] + 1
print(visited[t])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(M+1)]
for i in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
s, t = map(int, input().split())

d = [-1] * (N + 1)

S = set()
S.add(s)
d[s] = 0
x = 1
while len(S) > 0:
    Q1 = set()
    for u in S:
        for v in G[u]:
            Q1.add(v)
    Q2 = set()
    for u in Q1:
        for v in G[u]:
            Q2.add(v)
    Q3 = set()
    for u in Q2:
        for v in G[u]:
            if d[v] < 0:
                d[v] = x
                Q3.add(v)
    x += 1
    S = Q3

print(d[t])

Submission status: Runtime Error

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

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if h in d and d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1

Submission status: Runtime Error

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

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = {S}
for i in range(1, 1000000):
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(i)
        break
    for h in tuple(history):
        if d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break

Submission status: Runtime Error

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

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1

Submission status: Runtime Error

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

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1

Submission status: Runtime Error

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

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [{y}, False]

def next_node(start):
    history = set()
    for s in start:
        history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1

Submission status: Runtime Error

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

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [set([y]), False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = {S}
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in tuple(history):
        if d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1

Submission status: Runtime Error

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

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [set([y]), False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return history

history = [S]
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in list(history):
        if d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1

Submission status: Runtime Error

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

d = {}
for x, y in links:
    if x in d:
        d[x][0].add(y)
    else:
        d[x] = [set([y]), False]

def next_node(start):
    history = set()
    for s in start:
        if s in d:
            history |= d[s][0]
    return list(history)

history = [S]
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in reversed(history):
        if d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1

Submission status: Runtime Error

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

d = {}
for x, y in links:
    if x in d:
        d[x][0].append(y)
    else:
        d[x] = [[y], False]

def next_node(start):
    history = []
    for s in start:
        if s in d:
            history.extend(d[s][0])
    return list(set(history))

history = [S]
s = 1
while True:
    for _ in range(3):
        history = next_node(history)
    if T in history:
        print(s)
        break
    for h in reversed(history):
        if d[h][1]:
            history.remove(h)
        else:
            d[h][1] = True
    if len(history) == 0:
        print(-1)
        break
    s += 1