Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

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

memo = {}
def search(node, k):
  global memo
  s = set()
  if k == 0:
    return set([node])
  if (node, k) in memo:
    return memo[(node, k)]
  children = graph[node]
  for child in children:
    s |= search(child, k-1)
  memo[(node, k)] = s
  return s


# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  g[i] = search(i, 3)

dist = [-1] * N
dist[S] = 0
d = deque([[S, -1]])
while d:
  node, par = d.popleft()
  children = g[node]
  for child in children:
    if dist[child] < 0:
      dist[child] = dist[node] + 1
      d.append([child, node])

if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

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

memo = {}
def search(node, k):
  global memo
  s = set()
  if k == 0:
    return set([node])
  if (node, k) in memo:
    return memo[(node, k)]
  children = graph[node]
  for child in children:
    s |= search(child, k-1)
  memo[(node, k)] = s
  return s


# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  g[i] = search(i, 3)

dist = [-1] * N
dist[S] = 0
d = deque([[S, -1]])
while d:
  node, par = d.popleft()
  children = g[node]
  for child in children:
    if dist[child] < 0:
      dist[child] = dist[node] + 1
      d.append([child, node])

if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

S, T = map(int, input().split())
S -= 1; T -= 1
  
def search(node, k):
  s = set()
  if k == 0:
    return set([node])
  children = graph[node]
  for child in children:
    s |= search(child, k-1)
  return s


# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  g[i] = search(i, 3)

dist = [-1] * N
dist[S] = 0
d = deque([[S, -1]])
while d:
  node, par = d.popleft()
  children = g[node]
  for child in children:
    if dist[child] < 0:
      dist[child] = dist[node] + 1
      d.append([child, node])

if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
from collections import deque

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

# 距離が3のノード間にだけ辺を張り直す
row = []
col = []
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    s = set()
    for j in range(n):
      node = d.popleft()
      if node in s:
        continue
      s.add(node)
      children = graph[node]
      d.extend(children)
  _g = list(set(d))
  row.extend([i] * len(_g))
  col.extend(_g)

d = [1] * len(row)
graph = csr_matrix((d, (row, col)), shape=(N, N))
S, T = map(int, input().split())
S -= 1; T -= 1
dist = dijkstra(graph, indices=S).astype(int)
if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
from collections import deque

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

# 距離が3のノード間にだけ辺を張り直す
row = []
col = []
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    for j in range(n):
      node = d.popleft()
      children = graph[node]
      d.extend(children)
  _g = list(set(d))
  row.extend([i] * len(_g))
  col.extend(_g)

d = [1] * len(row)
graph = csr_matrix((d, (row, col)), shape=(N, N))
S, T = map(int, input().split())
S -= 1; T -= 1
dist = dijkstra(graph, indices=S).astype(int)
if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
row = []
col = []
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  row.extend([3*u, 3*u+1, 3*u+2])
  col.extend([3*v+1, 3*v+2, 3*v])

d = [1] * (3*M)

graph = csr_matrix((d, (row, col)), shape=(3*N, 3*N))

S, T = map(int, input().split())
S -= 1; T -= 1
dist = dijkstra(graph, indices=3*S).astype(int)

if dist[3*T] > 0:
  print(dist[3*T] // 3)
else:
  print(-1)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
row = []
col = []
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  row.extend([3*u, 3*u+1, 3*u+2])
  col.extend([3*v+1, 3*v+2, 3*v])

d = [1] * (3*M)

graph = csr_matrix((d, (row, col)), shape=(3*N, 3*N))

S, T = map(int, input().split())
S -= 1; T -= 1
dist = dijkstra(graph, indices=3*S).astype(int)

if dist[3*T] > 0:
  print(dist[3*T] // 3)
else:
  print(-1)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    for j in range(n):
      node = d.popleft()
      children = graph[node]
      d.extend(children)
  g[i] = list(set(d))

S, T = map(int, input().split())
S -= 1; T -= 1
d = deque([[S, -1]])
dist = [float('inf')] * N
dist[S] = 0
# 幅優先探索
while d:
  n = len(d)
  for i in range(n):
    node, par = d.popleft()
    children = g[node]
    for child in children:
      if child == par:
        continue
      if dist[child] > dist[node] + 1:
        dist[child] = dist[node] + 1
        d.append([child, node])
      if child == T:
        print(dist[child])
        quit()

print(-1)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  d = deque([i])
  for _ in range(3):
    n = len(d)
    for j in range(n):
      node = d.popleft()
      children = graph[node]
      d.extend(children)
  g[i] = d

S, T = map(int, input().split())
S -= 1; T -= 1
d = deque([[S, -1]])
dist = [float('inf')] * N
dist[S] = 0
# 幅優先探索
while d:
  n = len(d)
  for i in range(n):
    node, par = d.popleft()
    children = g[node]
    for child in children:
      if child == par:
        continue
      dist[child] = min(dist[child], dist[node] + 1)
      if child == T:
        print(dist[child])
        quit()
      d.append([child, node])

print(-1)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

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

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

is_visited = [False]*N
is_visited[s] = True

d = deque([s])
ans = 0
while d:
  ans += 1
  diff = 0
  for step in range(1, 4):
    if d:
      len_d = len(d)
      for i in range(len_d):
        node = d.popleft()
        children = graph[node]
        for child in children:
          if step == 3:
            if child == t:
              d = []
              diff = 1
              break
            if not is_visited[child]:
              is_visited[child] = True
              diff += 1
              d.append(child)
          else:
            d.append(child)
        
        else:
          continue
        break
    
    else:
      ans = -1
      break
  
  if not diff:
    ans = -1
    break

print(ans)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

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

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

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

is_visited = [False]*N
is_visited[s] = True

d = deque([s])
ans = 0
while d:
  ans += 1
  diff = 0
  for step in range(1, 4):
    if d:
      len_d = len(d)
      for i in range(len_d):
        node = d.popleft()
        children = graph[node]
        for child in children:
          if step == 3:
            if child == t:
              d = []
              diff = 1
              break
            if not is_visited[child]:
              is_visited[child] = True
              diff += 1
              d.append(child)
          else:
            d.append(child)
        
        else:
          continue
        break
    
    else:
      ans = -1
      break
  
  if not diff:
    ans = -1
    break

print(ans)

Fixed submission:
from collections import deque

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

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

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


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)