Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, M, L = map(int, input().split())
D = [[1000000000000]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
for i in range(M):
  A, B, C = map(int, input().split())
  A, B = A-1, B-1
  D[A][B] = C
  D[B][A] = C
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
E = [[1000000000000]*N for i in range(N)]
for i in range(N):
  E[i][i] = 0
for i in range(N):
  for j in range(N):
    if D[i][j] <= L:
      E[i][j] = 1
for k in range(N):
  for i in range(N):
    for j in range(N):
      E[i][j] = min(E[i][j], E[i][k]+E[k][j])
Q = int(input())
for i in range(Q):
  s, t = map(int, input().split())
  s, t = s-1, t-1
  if E[s][t] == 1000000000000:
    r = -1
  else:
    r = E[s][t]-1
  print(r)


Fixed submission:
N, M, L = map(int, input().split())
D = [[1000000000000]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
for i in range(M):
  A, B, C = map(int, input().split())
  A, B = A-1, B-1
  D[A][B] = C
  D[B][A] = C
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
E = [[1000000000000]*N for i in range(N)]
for i in range(N):
  E[i][i] = 0
for i in range(N):
  for j in range(N):
    if D[i][j] <= L:
      E[i][j] = 1
for k in range(N):
  for i in range(N):
    for j in range(N):
      E[i][j] = min(E[i][j], E[i][k]+E[k][j])
Q = int(input())
for i in range(Q):
  s, t = map(int, input().split())
  s, t = s-1, t-1
  if E[s][t] == 1000000000000:
    r = -1
  else:
    r = E[s][t]-1
  print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
for i in range(N):
  Ss = input()
  S.append(Ss)
E = [set() for i in range(N)]
D = [[100000]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
  for j in range(i+1, N):
    if S[i][j] == "1":
      #print(i, j)
      E[i].add(j)
      E[j].add(i)
      D[i][j] = 1
      D[j][i] = 1
ok = True
V = [-1]*N
c = 0
V[0] = 0
q = [0]
while q:
  c = q.pop()
  ns = E[c]
  for n in ns:
    if V[n] == V[c]:
      ok = False
    if not V[n] < 0:
      continue
    V[n] = 1 if V[c] == 0 else 0
    q.append(n)
if not ok:
  print(-1)
  exit()
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
#print(D)
r = max([max(Ds) for Ds in D])+1
print(r)


Fixed submission:
N = int(input())
S = []
for i in range(N):
  Ss = input()
  S.append(Ss)
E = [set() for i in range(N)]
D = [[100000]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
  for j in range(i+1, N):
    if S[i][j] == "1":
      #print(i, j)
      E[i].add(j)
      E[j].add(i)
      D[i][j] = 1
      D[j][i] = 1
ok = True
V = [-1]*N
c = 0
V[0] = 0
q = [0]
while q:
  c = q.pop()
  ns = E[c]
  for n in ns:
    if V[n] == V[c]:
      ok = False
    if not V[n] < 0:
      continue
    V[n] = 1 if V[c] == 0 else 0
    q.append(n)
if not ok:
  print(-1)
  exit()
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
#print(D)
r = max([max(Ds) for Ds in D])+1
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
afs = []
for i in range(M):
  a, b = map(int, input().split())
  cs = map(int, input().split())
  f = 0
  for c in cs:
    f = f|(1<<(c-1))
  afs.append((a, f))
dp = [{} for i in range(M+1)]
dp[0][0] = 0
for i in range(M):
  d = dp[i]
  a0, f0 = afs[i]
  d2 = {}
  for f in d:
    d2[f] = d[f]
  for f in d:
    f2 = f|f0
    a2 = d[f]+a0
    d2[f2] = a2 if f2 not in d2 else min(d2[f2], a2)
  dp[i+1] = d2
#print(dp)
if (1<<N)-1 in dp[M]:
  r = dp[M][(1<<N)-1]
else:
  r = -1
print(r)


Fixed submission:
N, M = map(int, input().split())
afs = []
for i in range(M):
  a, b = map(int, input().split())
  cs = map(int, input().split())
  f = 0
  for c in cs:
    f = f|(1<<(c-1))
  afs.append((a, f))
dp = [{} for i in range(M+1)]
dp[0][0] = 0
for i in range(M):
  d = dp[i]
  a0, f0 = afs[i]
  d2 = {}
  for f in d:
    d2[f] = d[f]
  for f in d:
    f2 = f|f0
    a2 = d[f]+a0
    d2[f2] = a2 if f2 not in d2 else min(d2[f2], a2)
  dp[i+1] = d2
#print(dp)
if (1<<N)-1 in dp[M]:
  r = dp[M][(1<<N)-1]
else:
  r = -1
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
p = 0
def check(l):
  global p
  for i in range(p, N-l):
    s = S[i:i+l]
    if not S.find(s, i+l) < 0:
      p = i
      return True
  return False
a = 1
b = N
while a < b:
  i = (a + b)//2
  if not check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b-1
print(r)


Fixed submission:
N = int(input())
S = input()
r = 0
i = j = 0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r, j-i)
    j += 1
  else:
    i += 1
print(r)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
def check(l):
  for i in range(N-l):
    s = S[i:i+l]
    if not S.find(s, i+l) < 0:
      return True
  return False
a = 1
b = N
while a < b:
  i = (a + b)//2
  if not check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b-1
print(r)


Fixed submission:
N = int(input())
S = input()
r = 0
i = j = 0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r, j-i)
    j += 1
  else:
    i += 1
print(r)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
def check(l):
  for i in range(N-l):
    s = S[i:i+l]
    if not S.find(s, i+l) < 0:
      return True
  return False
a = 1
b = N
while a < b:
  i = (a + b)//2
  if not check(i):
    b = i
  else:
    if a == i:
      break
    a = i
r = b-1
print(r)


Fixed submission:
N = int(input())
S = input()
r = 0
i = j = 0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r, j-i)
    j += 1
  else:
    i += 1
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()
N = len(s)
s2 = s + s
cs = set(t)
#print(cs)
table = {}
for c in cs:
  l = []
  for i in range(len(s)):
    j = s2.find(c, i)
    l.append(-1 if j < 0 else j-i)
  table[c] = l
#print(table)
r = 0
for c in t:
  d = table[c][r%N]
  if d < 0:
    print(-1)
    exit()
  r += d+1
print(r)


Fixed submission:
s = input()
t = input()
N = len(s)
s2 = s + s
cs = set(t)
#print(cs)
table = {}
for c in cs:
  if s.find(c) < 0:
    table[c] = [-1]*N
    continue
  l = [-2] * N
  p = 0
  while p < N:
    i = s2.find(c, p)
    while p <= i:
      if p < N:
        l[p] = i-p
      p += 1
  table[c] = l
#print(table)
r = 0
for c in t:
  d = table[c][r%N]
  if d < 0:
    print(-1)
    exit()
  r += d+1
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
Ts = []
for i in range(N):
  S = input()
  T = sorted(S)
  Ts.append(T)
r = 0
for i in range(N):
  for j in range(i+1, N):
    if Ts[i] == Ts[j]:
      r += 1
print(r)


Fixed submission:
N = int(input())
Ts = []
for i in range(N):
  S = input()
  T = "".join(sorted(S))
  Ts.append(T)
Ts.sort()
r = 0
c = 1
for i in range(N-1):
  if Ts[i] == Ts[i+1]:
    c += 1
  else:
    r += c*(c-1)//2
    c = 1
r += c*(c-1)//2
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  c = K-1 if i == 0 else K-2
  rt = 1
  for j in js:
    if not(counts[j]):
      counts[j] = True
      rt = (rt*c)%1000000007
      c -= 1
      q.append(j)
  r = (r*rt)%1000000007
print(r)


Fixed submission:
N, K = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  c = K-1 if i == 0 else K-2
  for j in js:
    if not(counts[j]):
      counts[j] = True
      r = (r*c)%1000000007
      c -= 1
      q.append(j)
print(r)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  jsn = list(filter(lambda j: not(counts[j]), js))
  #print(js, jsn)
  c = K-1-len(js)+len(jsn)
  for j in jsn:
    counts[j] = True
    r = (r*c)%1000000007
    c -= 1
  q.extend(jsn)
print(r)


Fixed submission:
N, K = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  c = K-1 if i == 0 else K-2
  for j in js:
    if not(counts[j]):
      counts[j] = True
      r = (r*c)%1000000007
      c -= 1
      q.append(j)
print(r)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
ab = []
for i in range(N-1):
  a, b = map(int, input().split())
  ab.append((a-1, b-1))
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = []
  for j in range(N-1):
    a, b = ab[j]
    if a == i:
      js.append(b)
    elif b == i:
      js.append(a)
  jsn = list(filter(lambda j: not(counts[j]), js))
  #print(js, jsn)
  c = K-1-len(js)+len(jsn)
  for j in jsn:
    counts[j] = True
    r = (r*c)%1000000007
    c -= 1
  q.extend(jsn)
print(r)


Fixed submission:
N, K = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  c = K-1 if i == 0 else K-2
  for j in js:
    if not(counts[j]):
      counts[j] = True
      r = (r*c)%1000000007
      c -= 1
      q.append(j)
print(r)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
for i in range(1,K+1):
  r = 1
  for j in range(1, i+1):
    r = (r * (N-K+2-j))
  for j in range(1, i+1):
    r = int(r / j)
  for j in range(1, i):
    r = (r * (K-j))
  for j in range(1, i):
    r = int(r / j)
  print(r % 1000000007)


Fixed submission:
N, K = map(int, input().split())
a = N-K+1
print(a)
for i in range(1,K):
  a = int(a * (N-K+1-i) * (K-i) // i // (i+1))
  print(a % 1000000007)
Buggy python submission (verdict: Time Limit Exceeded):
R, G, B, N = map(int, input().split())
c = 0
for r in range(0, N+1):
  for g in range(0, N+1):
    n = N-r*R-g*G
    if n < 0:
      continue
    if n%B == 0:
      c += 1
print(c)


Fixed submission:
R, G, B, N = map(int, input().split())
R, G, B = sorted([R, G, B], reverse=True)
if B == 1:
  c = 0
  for r in range(0, N+1):
    if r*R > N:
      break
    n = N-r*R
    c += 1+n//G
  print(c)
  exit()
c = 0
for r in range(0, N+1):
  if r*R > N:
    break
  for g in range(0, N+1):
    if r*R+g*G > N:
      break
    n = N-r*R-g*G
    if n%B == 0:
      c += 1
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
A = []
q = []
for i in range(H):
  As = list(input())
  A.append(As)
  for j in range(W):
    if A[i][j] == "#":
      q.append((i, j))
r = 0
while q:
  q2 = []
  for i, j in q:
    if i-1 >= 0 and A[i-1][j] == ".":
      A[i-1][j] = "#"
      q2.append((i-1, j))
    if i+1 < H and A[i+1][j] == ".":
      A[i+1][j] = "#"
      q2.append((i+1, j))
    if j-1 >= 0 and A[i][j-1] == ".":
      A[i][j-1] = "#"
      q2.append((i, j-1))
    if j+1 < W and A[i][j+1] == ".":
      A[i][j+1] = "#"
      q2.append((i, j+1))
  q = q2
  r += 1
r -= 1
print(r)


Fixed submission:
H, W = map(int, input().split())
A = []
q = []
for i in range(H):
  As = list(input())
  A.append(As)
  for j in range(W):
    if A[i][j] == "#":
      q.append((i, j))
r = 0
while q:
  q2 = []
  for i, j in q:
    if i-1 >= 0 and A[i-1][j] == ".":
      A[i-1][j] = "#"
      q2.append((i-1, j))
    if i+1 < H and A[i+1][j] == ".":
      A[i+1][j] = "#"
      q2.append((i+1, j))
    if j-1 >= 0 and A[i][j-1] == ".":
      A[i][j-1] = "#"
      q2.append((i, j-1))
    if j+1 < W and A[i][j+1] == ".":
      A[i][j+1] = "#"
      q2.append((i, j+1))
  q = q2
  r += 1
r -= 1
print(r)
Buggy python submission (verdict: Runtime Error):
S = input()
r = 0
L = []
for c in S:
  if c == "A" or c == "C" or c == "G" or c == "T":
    r += 1
  else:
    L.append(r)
    r = 0
print(max(L))


Fixed submission:
S = input()
r = 0
L = []
for c in S:
  if c == "A" or c == "C" or c == "G" or c == "T":
    r += 1
  else:
    L.append(r)
    r = 0
L.append(r)
print(max(L))
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
Is = []
p = 0
while True:
  i = S.find("AC", p)
  if i < 0:
    break
  Is.append(i)
  p = i+2
#print(Is)
for i in range(Q):
  l, r = map(int, input().split())
  l, r = l-1, r-1
  c = 0
  for i in Is:
    if i >= l and i+1 <= r:
      c += 1
  print(c)


Fixed submission:
N, Q = map(int, input().split())
S = input()
ns = [-1]*N
n = 0
ns[0] = n
for i in range(N-1):
  if S[i:i+2] == "AC":
    n += 1
  ns[i+1] = n
#print(ns)
for i in range(Q):
  l, r = map(int, input().split())
  l, r = l-1, r-1
  c = ns[r]-ns[l]
  print(c)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
N = len(S)
while True:
  n = len(S)
  S = S.replace("01", "")
  S = S.replace("10", "")
  if len(S) == n:
    break
#print(N, S)
r = N-len(S)
print(r)


Fixed submission:
S = input()
N = len(S)
N0 = S.count("0")
N1 = S.count("1")
r = 2*min(N0, N1)
print(r)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
ABs = []
for i in range(M):
  A, B = map(int, input().split())
  A, B = A-1, B-1
  ABs.append((A, B))
UF = list(range(N))
Ns = [1]*N
def par(m):
  if UF[m] == m:
    return m
  r = par(UF[m])
  UF[m] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[i] = j
  Ns[j] = Ns[i]+Ns[j]
def size(m):
  return Ns[par(m)]
r = N*(N-1)//2
rs = [r]
for A, B in reversed(ABs):
  if par(A) == par(B):
    rs.append(r)
    continue
  sA = size(A)
  sB = size(B)
  unite(A, B)
  r -= sA*sB
  rs.append(r)
rs.pop()
for r in reversed(rs):
  print(r)


Fixed submission:
N, M = map(int, input().split())
ABs = []
for i in range(M):
  A, B = map(int, input().split())
  A, B = A-1, B-1
  ABs.append((A, B))
UF = list(range(N))
Ns = [1]*N
def par(m):
  s = []
  r = UF[m]
  while r != m:
    s.append(m)
    m = r
    r = UF[m]
  for i in s:
    UF[i] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[j] = i
  Ns[i] = Ns[j] = Ns[i]+Ns[j]
def size(m):
  return Ns[par(m)]
r = N*(N-1)//2
rs = [r]
for A, B in reversed(ABs):
  if par(A) == par(B):
    rs.append(r)
    continue
  sA = size(A)
  sB = size(B)
  unite(A, B)
  r -= sA*sB
  rs.append(r)
rs.pop()
for r in reversed(rs):
  print(r)

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
ABs = []
for i in range(M):
  A, B = map(int, input().split())
  A, B = A-1, B-1
  ABs.append((A, B))
UF = list(range(N))
Ns = [1]*N
def par(m):
  if UF[m] == m:
    return m
  r = par(UF[m])
  UF[m] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[i] = j
  Ns[i] = Ns[j] = Ns[i]+Ns[j]
def size(m):
  return Ns[par(m)]
r = N*(N-1)//2
rs = [r]
for A, B in reversed(ABs):
  if par(A) == par(B):
    rs.append(r)
    continue
  sA = size(A)
  sB = size(B)
  unite(A, B)
  r -= sA*sB
  rs.append(r)
rs.pop()
for r in reversed(rs):
  print(r)


Fixed submission:
N, M = map(int, input().split())
ABs = []
for i in range(M):
  A, B = map(int, input().split())
  A, B = A-1, B-1
  ABs.append((A, B))
UF = list(range(N))
Ns = [1]*N
def par(m):
  s = []
  r = UF[m]
  while r != m:
    s.append(m)
    m = r
    r = UF[m]
  for i in s:
    UF[i] = r
  return r
def unite(m, n):
  i = par(m)
  j = par(n)
  UF[j] = i
  Ns[i] = Ns[j] = Ns[i]+Ns[j]
def size(m):
  return Ns[par(m)]
r = N*(N-1)//2
rs = [r]
for A, B in reversed(ABs):
  if par(A) == par(B):
    rs.append(r)
    continue
  sA = size(A)
  sB = size(B)
  unite(A, B)
  r -= sA*sB
  rs.append(r)
rs.pop()
for r in reversed(rs):
  print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
hs = list(map(int, input().split()))
cs = [0]
for i in range(1, N):
  ccs = []
  for j in range(1, min(i, K)+1):
    c = cs[i-j]+abs(hs[i]-hs[i-j])
    ccs.append(c)
  c = min(ccs)
  cs.append(c)
r = cs[-1]
print(r)


Fixed submission:
N, K = map(int, input().split())
hs = list(map(int, input().split()))
cs = [0]
for i in range(1, N):
  ccs = []
  for j in range(1, min(i, K)+1):
    c = cs[i-j]+abs(hs[i]-hs[i-j])
    ccs.append(c)
  c = min(ccs)
  cs.append(c)
r = cs[-1]
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int, input().split()))
def xor(L):
  r = L[0]
  for i in range(1, len(L)):
    r ^= L[i]
  return r
re = 0
r = 0
for l in range(0, N):
  while r < N:
    if sum(As[l:r+1]) == xor(As[l:r+1]):
      r += 1
    else:
      break
  #print(l, r)
  re += r-l
print(re)


Fixed submission:
N = int(input())
As = list(map(int, input().split()))
def xor(L):
  r = L[0]
  for i in range(1, len(L)):
    r ^= L[i]
  return r
re = 0
r = 0
s = 0
x = 0
for l in range(0, N):
  #s += As[l]
  #x ^= As[l]
  while r < N:
    #print(l, r, s, x)
    if s+As[r] == x^As[r]:
      s += As[r]
      x ^= As[r]
    #if sum(As[l:r+1]) == xor(As[l:r+1]):
      r += 1
    else:
      break
  s -= As[l]
  x ^= As[l]
  #print(l, r)
  re += r-l
print(re)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
for i in range(N):
  Ss = input()
  S.append(Ss)
r = 0
for i in range(N):
  T = S[i:]+S[:i]
  ok = True
  for i in range(N):
    for j in range(i+1, N):
      if T[i][j] != T[j][i]:
        ok = False
        break
  if ok:
    r += 1
r *= N
print(r)


Fixed submission:
N = int(input())
S = []
for i in range(N):
  Ss = input()
  S.append(Ss)
r = 0
for i in range(N):
  T = S[i:]+S[:i]
  ok = True
  for i in range(N):
    for j in range(i+1, N):
      if T[i][j] != T[j][i]:
        ok = False
        break
  if ok:
    r += 1
r *= N
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
import queue
H, W = map(int, input().split())
numw = 0
S = []
for i in range(H):
  ss = input()
  numw += ss.count(".")
  S.append(ss)
#print(numw)
D = [[1000000]*W for i in range(H)]
q = queue.Queue()
q.put((0, 0, 0))
D[0][0] = 0
while not(q.empty()):
  i, j, d = q.get()
  if j > 0 and S[i][j-1] == "." and D[i][j-1] >= d:
    D[i][j-1] = d+1
    q.put((i, j-1, d+1))
  if i > 0 and S[i-1][j] == "." and D[i-1][j] >= d:
    D[i-1][j] = d+1
    q.put((i-1, j, d+1))
  if j+1 < W and S[i][j+1] == "." and D[i][j+1] >= d:
    D[i][j+1] = d+1
    q.put((i, j+1, d+1))
  if i+1 < H and S[i+1][j] == "." and D[i+1][j] >= d:
    D[i+1][j] = d+1
    q.put((i+1, j, d+1))
#print(D)
if D[H-1][W-1] == 1000000:
  print(-1)
  exit()
r = numw-D[H-1][W-1]-1
print(r)


Fixed submission:
import queue
H, W = map(int, input().split())
numw = 0
S = []
for i in range(H):
  ss = input()
  numw += ss.count(".")
  S.append(ss)
#print(numw)
D = [[-1]*W for i in range(H)]
q = queue.Queue()
q.put((0, 0, 0))
D[0][0] = 0
while not(q.empty()):
  i, j, d = q.get()
  if j > 0 and S[i][j-1] == "." and D[i][j-1] < 0:
    D[i][j-1] = d+1
    q.put((i, j-1, d+1))
  if i > 0 and S[i-1][j] == "." and D[i-1][j] < 0:
    D[i-1][j] = d+1
    q.put((i-1, j, d+1))
  if j+1 < W and S[i][j+1] == "." and D[i][j+1] < 0:
    D[i][j+1] = d+1
    q.put((i, j+1, d+1))
  if i+1 < H and S[i+1][j] == "." and D[i+1][j] < 0:
    D[i+1][j] = d+1
    q.put((i+1, j, d+1))
#print(D)
if D[H-1][W-1] < 0:
  print(-1)
  exit()
r = numw-D[H-1][W-1]-1
print(r)

Buggy python submission (verdict: Time Limit Exceeded):
import queue
H, W = map(int, input().split())
numw = 0
S = []
for i in range(H):
  ss = input()
  numw += ss.count(".")
  S.append(ss)
#print(numw)
D = [[1000000]*W for i in range(H)]
q = queue.Queue()
q.put((0, 0, 0))
D[0][0] = 0
while not(q.empty()):
  i, j, d = q.get()
  D[i][j] = d
  if j > 0 and S[i][j-1] == "." and D[i][j-1] > d:
    q.put((i, j-1, d+1))
  if i > 0 and S[i-1][j] == "." and D[i-1][j] > d:
    q.put((i-1, j, d+1))
  if j+1 < W and S[i][j+1] == "." and D[i][j+1] > d:
    q.put((i, j+1, d+1))
  if i+1 < H and S[i+1][j] == "." and D[i+1][j] > d:
    q.put((i+1, j, d+1))
#print(D)
if D[H-1][W-1] == 1000000:
  print(-1)
  exit()
r = numw-D[H-1][W-1]-1
print(r)


Fixed submission:
import queue
H, W = map(int, input().split())
numw = 0
S = []
for i in range(H):
  ss = input()
  numw += ss.count(".")
  S.append(ss)
#print(numw)
D = [[-1]*W for i in range(H)]
q = queue.Queue()
q.put((0, 0, 0))
D[0][0] = 0
while not(q.empty()):
  i, j, d = q.get()
  if j > 0 and S[i][j-1] == "." and D[i][j-1] < 0:
    D[i][j-1] = d+1
    q.put((i, j-1, d+1))
  if i > 0 and S[i-1][j] == "." and D[i-1][j] < 0:
    D[i-1][j] = d+1
    q.put((i-1, j, d+1))
  if j+1 < W and S[i][j+1] == "." and D[i][j+1] < 0:
    D[i][j+1] = d+1
    q.put((i, j+1, d+1))
  if i+1 < H and S[i+1][j] == "." and D[i+1][j] < 0:
    D[i+1][j] = d+1
    q.put((i+1, j, d+1))
#print(D)
if D[H-1][W-1] < 0:
  print(-1)
  exit()
r = numw-D[H-1][W-1]-1
print(r)
Buggy python submission (verdict: Runtime Error):
A = int(input())
B = int(input())
C = int(input())
X = int(input())
r = 0;
for a in range(0, A + 1):
    for b in range(0, B + 1):
        for c in range(0, C + 1):
            if (500 * a + 100 * b + 50 * c == X):
                r += 1
print(r)


Fixed submission:
X = int(input())
A = int(input())
B = int(input())
r = X-A
r -= r//B*B
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
Ps = set()
M = [False]*100001
p = 2
while p <= 100000:
  if not(M[p]):
    Ps.add(p)
    for i in range(p, 100000, p):
      M[i] = True
  p += 1
#print(sorted(Ps))
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  re = 0
  for i in range(l, r+1, 2):
    if i in Ps and (i+1)//2 in Ps:
      re += 1
  print(re)


Fixed submission:
Ps = set()
M = [False]*100001
p = 2
while p <= 100000:
  if not(M[p]):
    Ps.add(p)
    for i in range(p, 100000, p):
      M[i] = True
  p += 1
#print(sorted(Ps))
r = 0
Ss = [0]*100001
for i in range(100000):
  if i%2 == 1 and i in Ps and (i+1)//2 in Ps:
    r += 1
  Ss[i] = r
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  re = Ss[r]-Ss[l-1]
  print(re)
Buggy python submission (verdict: Runtime Error):
N, A, B = [int(s) for s in input().split()]
r = 0;
def sumdig(n):
    r = 0;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    d = n % 10;
    r += d;
    n = (n - d) / 10;
    return r;
for n in range(1, N + 1):
    s = sumdig(n)
    if (s >= A and s <= B):
        r += n;
print(r)


Fixed submission:
A, B, C, D = map(int, input().split())
L = A+B
R = C+D
if L > R:
  print("Left")
if L == R:
  print("Balanced")
if L < R:
  print("Right")
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
X, Y = map(int, input().split())
fs = s.split("T")
nsx = list(map(len, fs[0::2]))
nsy = list(map(len, fs[1::2]))
xs = set()
q = [(nsx[0], 1)]
while q:
  x, i = q.pop()
  if i == len(nsx):
    xs.add(x)
  else:
    q.append((x+nsx[i], i+1))
    q.append((x-nsx[i], i+1))
ys = set()
q = [(0, 0)]
while q:
  y, i = q.pop()
  if i == len(nsy):
    ys.add(y)
  else:
    q.append((y+nsy[i], i+1))
    q.append((y-nsy[i], i+1))
#print(xs, ys)
if X in xs and Y in ys:
  print("Yes")
else:
  print("No")


Fixed submission:
s = input()
X, Y = map(int, input().split())
fs = s.split("T")
nsx = list(map(len, fs[0::2]))
nsy = list(map(len, fs[1::2]))
ssx = []
ssx.append({ 0 })
ssx.append({ nsx[0] })
for i in range(1, len(nsx)):
  s = ssx[i]
  n = nsx[i]
  s2 = set()
  for x in s:
    s2.add(x+n)
    s2.add(x-n)
  ssx.append(s2)
#print(ssx)
ssy = [{ 0 }]
for i in range(0, len(nsy)):
  s = ssy[i]
  n = nsy[i]
  s2 = set()
  for y in s:
    s2.add(y+n)
    s2.add(y-n)
  ssy.append(s2)
#print(ssy)
if X in ssx[-1] and Y in ssy[-1]:
  print("Yes")
else:
  print("No")