Problem p02991 (python)

Fixed submission:
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]
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)