Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque 
from collections import defaultdict
n, x, y = map(int, input().split())
graph = [[] for _ in range(n)]     
for i in range(n-1):
  graph[i] += [i+1]
  graph[i+1] += [i]
graph[x-1] += [y-1]
graph[y-1] += [x-1]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0)) 

def bfs(s):
  dist = [float('inf')]*n
  dist[s] = 0
  q = deque([s])

  while q:
    u = q.popleft() 
    for v in graph[u]:
      if dist[v] == float('inf'):
        q += [v]
        dist[v] = dist[u] + 1

  return dist

ans = defaultdict(int)
for i in range(n):
  d = bfs(i)
  for j in range(i+1, n):
    ans[d[j]] += 1 

for i in range(1, n):
  if i in ans.keys():
    print(ans[i])
  else:
    print(0)


Fixed submission:
from collections import deque 
from collections import defaultdict
n, x, y = map(int, input().split())
graph = [[] for _ in range(n)]     
for i in range(n-1):
  graph[i] += [i+1]
  graph[i+1] += [i]
graph[x-1] += [y-1]
graph[y-1] += [x-1]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0)) 

def bfs(s):
  dist = [float('inf')]*n
  dist[s] = 0
  q = deque([s])

  while q:
    u = q.popleft() 
    for v in graph[u]:
      if dist[v] == float('inf'):
        q += [v]
        dist[v] = dist[u] + 1

  return dist

ans = defaultdict(int)
for i in range(n):
  d = bfs(i)
  for j in range(i+1, n):
    ans[d[j]] += 1 

for i in range(1, n):
  if i in ans.keys():
    print(ans[i])
  else:
    print(0)

Buggy python submission (verdict: Time Limit Exceeded):
  
n, x, y = map(int, input().split())
x -= 1
y -= 1
d= [[float('inf')]*n for _ in range(n)]
for i in range(n-1):
  if i == 0:
    d[0][1] = 1
    d[n-1][n-2] = 1
  else:
    d[i][i+1] = 1
    d[i][i-1] = 1
for i in range(n):
  d[i][i] = 0

d[x][y] = 1
d[y][x] = 1
def warshall_floyd(d):
  #d[i][j]: iからjへの最短距離
  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])
  return d

d = warshall_floyd(d)
  
from collections import defaultdict
di = defaultdict(int)
for i in range(n):
  for j in range(i+1, n):
    di[d[i][j]] += 1 

for i in range(1, n):
  if i in di.keys():
    print(di[i])
  else:
    print(0)

Fixed submission:
from collections import deque 
from collections import defaultdict
n, x, y = map(int, input().split())
graph = [[] for _ in range(n)]     
for i in range(n-1):
  graph[i] += [i+1]
  graph[i+1] += [i]
graph[x-1] += [y-1]
graph[y-1] += [x-1]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0)) 

def bfs(s):
  dist = [float('inf')]*n
  dist[s] = 0
  q = deque([s])

  while q:
    u = q.popleft() 
    for v in graph[u]:
      if dist[v] == float('inf'):
        q += [v]
        dist[v] = dist[u] + 1

  return dist

ans = defaultdict(int)
for i in range(n):
  d = bfs(i)
  for j in range(i+1, n):
    ans[d[j]] += 1 

for i in range(1, n):
  if i in ans.keys():
    print(ans[i])
  else:
    print(0)
Buggy python submission (verdict: Runtime Error):
, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
q = sorted(list(map(int, input().split())), reverse=True)
r = sorted(list(map(int, input().split())), reverse=True)

p = p[:x]
q = q[:y]
a = p + q + r 
a = sorted(a, reverse=True)
print(sum(a[:x+y]))


Fixed submission:
x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
q = sorted(list(map(int, input().split())), reverse=True)
r = sorted(list(map(int, input().split())), reverse=True)

p = p[:x]
q = q[:y]
a = p + q + r 
a = sorted(a, reverse=True)
print(sum(a[:(x+y)]))

Buggy python submission (verdict: Runtime Error):
x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
q = sorted(list(map(int, input().split())), reverse=True)
r = sorted(list(map(int, input().split())), reverse=True)
ans = 0
ans += sum(p[:x])
ans += sum(q[:y])
pq = p[:x] + q[:y]
pq = sorted(pq)
if a+b >= c:
  for i in range(c):
    if pq[i] < r[i]:
      ans = ans - pq[i] + r[i]
  print(ans)
else:
  for i in range(c-a-b):
    ans += r[i]
  print(ans)



Fixed submission:
x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
q = sorted(list(map(int, input().split())), reverse=True)
r = sorted(list(map(int, input().split())), reverse=True)

p = p[:x]
q = q[:y]
a = p + q + r 
a = sorted(a, reverse=True)
print(sum(a[:(x+y)]))

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
q = sorted(list(map(int, input().split())), reverse=True)
r = sorted(list(map(int, input().split())), reverse=True)
dp = defaultdict(int)
dq = defaultdict(int)
dr = defaultdict(int)
ans = 0
ans += sum(p[:x])
ans += sum(q[:y])
pq = p[:x] + q[:y]
pq = sorted(pq)
for i in range(c):
  if pq[i] < r[i]:
    ans = ans - pq[i] + r[i]
print(ans)




Fixed submission:
x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())), reverse=True)
q = sorted(list(map(int, input().split())), reverse=True)
r = sorted(list(map(int, input().split())), reverse=True)

p = p[:x]
q = q[:y]
a = p + q + r 
a = sorted(a, reverse=True)
print(sum(a[:(x+y)]))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n = int(input())
l = [i for i in range(1, n+1)]
alpha_dict = {}
for i,c in enumerate(range(ord('A'),ord('Z')+1)):
  alpha_dict[i+1] = chr(c)

ans = set()
for v in itertools.product(range(1, n+1), repeat=n):
  m = min(v)
  used = []
  dic = {i:0 for i in range(n+1)}
  tmp = ""
  for u in v:
    if dic[u] == 0:
      dic[u] = len(used)+1
      used += [u]
      tmp += str(alpha_dict[dic[u]]).lower()
    else:
      tmp += str(alpha_dict[dic[u]]).lower()
  ans.add(tmp)

ans = sorted(list(ans))
for v in ans:
  print(v)



Fixed submission:
n = int(input())
alpha_dict = {}
for i,c in enumerate(range(ord('A'),ord('Z')+1)):
  alpha_dict[i] = str(chr(c)).lower()


ans = []
def dfs(s, mx, ans):
  if len(s) == n:
    ans += [s]
    return 
  else:
    for i in range(mx+2):
      dfs(s+alpha_dict[i], max(i, mx), ans)

dfs("", -1, ans)
ans = sorted(ans)
for a in ans:
  print(a)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(m)]

if n == 1:
  for i in range(10):
    i = str(i)
    for s, c in sc:
      if i == str(c):
        flag = True 
      else:
        flag = False
        break 
    if flag:
      print(''.join(i))
      exit()

for i in range(10**(n-1), 1000):
  i = list(str(i))
  flag = False
  for s,c in sc:
    if i[s-1] == str(c):
      flag = True
    else:
      flag = False
      break
  if flag:
    print(''.join(i))
    exit()

print('-1')

Fixed submission:
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(M)]
for i in range(0, 1000):
  i = str(i)
  flag = True
  if len(i) != N:
    continue
  for s, c in sc:
    #print(i, s, len(i))
    if len(list(i)) < s:
      flag = False
      break
    if i[s-1] != str(c):
      flag = False
      break
  if flag:
    print(i)
    exit()

print(-1)

Buggy python submission (verdict: Runtime Error):
if n == 1:
  for i in range(10):
    i = str(i)
    for s, c in sc:
      if i == str(c):
        flag = True 
      else:
        flag = False
        break 
    if flag:
      print(''.join(i))
      exit()

for i in range(10**(n-1), 1000):
  i = list(str(i))
  flag = False
  for s,c in sc:
    if i[s-1] == str(c):
      flag = True
    else:
      flag = False
      break
  if flag:
    print(''.join(i))
    exit()

print('-1')

Fixed submission:
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(M)]
for i in range(0, 1000):
  i = str(i)
  flag = True
  if len(i) != N:
    continue
  for s, c in sc:
    #print(i, s, len(i))
    if len(list(i)) < s:
      flag = False
      break
    if i[s-1] != str(c):
      flag = False
      break
  if flag:
    print(i)
    exit()

print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
Mod = 10**9+7
n, a, b = map(int, input().split())
N = n+1

def COMinit():
  #N_C_kのN
  for i in range(2, N):
    fac.append(fac[-1]*i%Mod)
    inv.append((-inv[Mod%i] * (Mod//i)) % Mod)
    finv.append(finv[-1] * inv[-1] % Mod)


def COM(n, k):
  if n < 0 or k < 0 or n < k:
    return 0
  return fac[n] * (finv[k] * finv[n-k] % Mod) % Mod

COMinit()
#xのn乗をmで割った余り
def pos(x, n, m):
    if n == 0:
        return 1
    res = pos(x*x%m, n//2, m)
    if n%2 == 1:
        res = res*x%m
    return res


def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

print((power_func(2, n, Mod)-COM(n,a)-COM(n,b)-1)%Mod)

Fixed submission:
def ncr(n, r, p): 
  num = den = 1 
  for i in range(r): 
      num = (num * (n - i)) % p 
      den = (den * (i + 1)) % p 
  return (num * pow(den, p - 2, p)) % p
p=10**9+7
n,a,b = map(int,(input().split()))
bb = ncr(n,a,p)+ncr(n,b,p)+1
print((pow(2,n,p)-(bb%p))%p)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
p = list(map(int, input().split()))
e = [(n+1)/2 for n in p]
ans = 0
for i in range(N-K+1):
  ans = max(ans, sum(e[i:i+K]))
print(ans)

Fixed submission:
N, K = map(int, input().split())
p = list(map(int, input().split()))
e = [(n+1)/2 for n in p]
now = sum(e[0:K])
ans = now
if N == 1:
  print(e[0])
  exit()

for i in range(1, N-K+1):
  now -= e[i-1]
  now += e[i+K-1]
  ans = max(ans, now)
print(ans)
Buggy python submission (verdict: Runtime Error):
H, N = map(int, input().split())
A = list(map(int, input().split()))

if sum(A) >= H:
  print('Yes')
else:

Fixed submission:
H, N = map(int, input().split())
A = list(map(int, input().split()))

if sum(A) >= H:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Runtime Error):
import math
a, b = map(int, input().split())
#a,bの最小公倍数
def lcm(a, b):
  return a * b // math.gcd (a, b)
print(lcm(a, b))

Fixed submission:
import fractions
a, b = map(int, input().split())
print(a * b // fractions.gcd(a, b))
Buggy python submission (verdict: Runtime Error):
x = int(input())
dic = {0: 100, 1:101, 2:102, 3:103, 4:104, 5:105}
global ans
ans = 0
def dfs(i, v):
  global ans
  if v == x:
    ans = 1
    return

  if v > x:
    return
  
  for k in range(6):
    dfs(k, v+dic[k])

  return 

dfs(0, 0)
if ans == 1:
  print(1)
else:
  print(0)

Fixed submission:
x = int(input())
n = x // 100 + 10
for i1 in range(n+1):
  for i2 in range(n+1-i1+1):
    for i3 in range(n+1-i1-i2+1):
      for i4 in range(n+1-i1-i2-i3+1):
        for i5 in range(n+1-i1-i2-i3-i4+1):
          for i6 in range(n+1-i1-i2-i3-i4-i5+1):
            if 100*i1+101*i2+102*i3+103*i4+104*i5+105*i6 == x:
              if i1<=1000000 and i2<=1000000 and i3<=1000000 and i4<=1000000 and i5<=1000000 and i6<=1000000:
                print(1)
                exit()
print(0)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = list(map(str, input()))

def solve(k):
  k1, k2, k3 = list(k)
  ans = 0
  for i1 in range(n):
    if s[i1] == k1:
      for i2 in range(i1+1, n):
        if s[i2] == k2:
          for i3 in range(i2+1, n):
            if s[i3] == k3:
              return 1
  return 0

ans = 0
for k in range(1000):
  k = '{:0=3}'.format(k)
  ans += solve(k)

print(ans)

Fixed submission:
n = int(input())
s = list(map(str, input()))

def solve(k):
  k1, k2, k3 = list(k)
  ans = 0
  flag = 0
  for i1 in range(n):
    if s[i1] == k1:
      for i2 in range(i1+1, n):
        if s[i2] == k2:
          for i3 in range(i2+1, n):
            if s[i3] == k3:
              flag = 1
              break
          break
      break
  if flag:
    return 1
  else:
    return 0

ans = 0
for k in range(1000):
  k = '{:0=3}'.format(k)
  ans += solve(k)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = list(map(str, input()))

def solve(k):
  k1, k2, k3 = list(k)
  ans = 0
  for i1 in range(n):
    if s[i1] == k1:
      for i2 in range(i1+1, n):
        if s[i2] == k2:
          for i3 in range(i2+1, n):
            if s[i3] == k3:
              return 1
  return 0

ans = 0
for k in range(1000):
  k = '{:0=3}'.format(k)
  ans += solve(k)

print(ans)

Fixed submission:
n = int(input())
s = list(map(str, input()))

def solve(k):
  k1, k2, k3 = list(k)
  ans = 0
  flag = 0
  for i1 in range(n):
    if s[i1] == k1:
      for i2 in range(i1+1, n):
        if s[i2] == k2:
          for i3 in range(i2+1, n):
            if s[i3] == k3:
              flag = 1
              break
          break
      break
  if flag:
    return 1
  else:
    return 0

ans = 0
for k in range(1000):
  k = '{:0=3}'.format(k)
  ans += solve(k)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n = int(input())
s = list(map(str, input()))
num = [i for i in range(n)]
st = set()
for ll in list(itertools.combinations(s, r=3)):
  nn = ''.join(ll)
  st.add(nn)

print(len(st))

Fixed submission:
n = int(input())
s = list(map(str, input()))

def solve(k):
  k1, k2, k3 = list(k)
  ans = 0
  flag = 0
  for i1 in range(n):
    if s[i1] == k1:
      for i2 in range(i1+1, n):
        if s[i2] == k2:
          for i3 in range(i2+1, n):
            if s[i3] == k3:
              flag = 1
              break
          break
      break
  if flag:
    return 1
  else:
    return 0

ans = 0
for k in range(1000):
  k = '{:0=3}'.format(k)
  ans += solve(k)

print(ans)
Buggy python submission (verdict: Runtime Error):
days = {"SUN":7, "SAT": 1, "FRI":2, "THU":3, "WED":4, "TUR":5, "MON": 6}
s = input()
print(days[s])


Fixed submission:
dic = {"SUN": 7, "MON": 6, "TUE": 5, "WED": 4, "THU": 3, "FRI": 2, "SAT": 1}
print(dic[input()])

Buggy python submission (verdict: Runtime Error):
import math
a, b, x = map(int, input().split())
tmp = 0
for i in range(10, 0, -1):
  if a * (10**(i-1)) + b * i <= x:
    tmp = i
    break
if tmp >= 10:
  print(1000000000)
  exit()
if tmp == 0:
  print(0)
  exit()
ans = 0
ans = math.floor((x-b*tmp)/a)
if ans > 10**(tmp):
  ans = 10**(tmp)-1
print(ans)

Fixed submission:
dic = {"SUN": 7, "MON": 6, "TUE": 5, "WED": 4, "THU": 3, "FRI": 2, "SAT": 1}
print(dic[input()])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N)]
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]

col_max = 0
for i in range(N-1):
  a, b = ab[i]
  graph[a] += [b]
  graph[b] += [a]

for i in range(N):
  col_max = max(col_max, len(graph[i]))
print(col_max)

def bfs(s):
  q = deque([s])
  col = [0]*N
  col[s] = 1
  ad_col = [set() for _ in range(N)]
  edge_col = {}
  pre = -1

  while q:
    u = q.pop()
    col_q = deque([i for i in range(1, col_max+1) if i not in ad_col[u]])
    #print(u, col_q, ad_col)
    for v in graph[u]:
      if v != pre and col[v] == 0:
        c = col_q.popleft()
        col[v] = c
        q.append(v)
        ad_col[u].add(c)
        ad_col[v].add(c)
        edge_col[(u, v)] = c
        edge_col[(v, u)] = c
        pre = v
  return edge_col

col = bfs(0)
#print(col)

for a, b in ab:
  print(col[(a, b)])

Fixed submission:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N)]
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]

col_max = 0
for i in range(N-1):
  a, b = ab[i]
  graph[a] += [b]
  graph[b] += [a]

for i in range(N):
  col_max = max(col_max, len(graph[i]))
print(col_max)

def bfs(s):
  q = deque([s])
  col = [-1]*N
  col[s] = 0
  edge_col = {}

  while q:
    c = 1
    u = q.pop()
    for v in graph[u]:
      if col[v] == -1:
        if c == col[u]:
          c += 1
        col[v] = c
        q.append(v)
        edge_col[(u, v)] = c
        edge_col[(v, u)] = c
        c += 1
  return edge_col

col = bfs(0)

for a, b in ab:
  print(col[(a, b)])
Buggy python submission (verdict: Runtime Error):
import math
a, b, x = map(int, input().split())
y = a*a*b - x

if (a*a*b/2 < x):
  print(90-math.degrees(math.atan((a**3)/(2*y))))
else:
  print(90-math.degrees(math.atan((2*x)/(a* b**2))))


Fixed submission:
import math
a, b, x = map(int, input().split())
y = a*a*b - x
if y == 0:
  print(0)
  exit()

if (a*a*b/2 < x):
  print(90-math.degrees(math.atan((a**3)/(2*y))))
else:
  print(90-math.degrees(math.atan((2*x)/(a* b**2))))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n):
  for j in range(i+1, n):
    s = l[i]+l[j]
    tmpl = l[j+1:n]
    ans += bisect_left(l[j+1:n], s)

print(ans)

Fixed submission:
import bisect
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n):
  for j in range(n-1, i, -1):
    s = l[i]+l[j]
    ans += bisect_left(l[j+1:n], s)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n = int(input())
l = list(map(int, input().split()))
ll = list(itertools.combinations(l, 3))
ans = 0
for a, b, c in ll:
  if a < b+c and b < c+a and c<a+b:
    ans += 1
print(ans)

Fixed submission:
import bisect
from bisect import bisect_left
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n):
  for j in range(n-1, i, -1):
    s = l[i]+l[j]
    ans += bisect_left(l[j+1:n], s)

print(ans)
Buggy python submission (verdict: Runtime Error):
import math
from collections import Counter
A, B = map(int, input().split())
C = math.gcd(A, B)

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(C))+1):
  while C % i == 0:
    C /= i
    prime_count[i] += 1
if C > 1:
  prime_count[int(C)] += 1

print(len(prime_count)+1)

Fixed submission:
import fractions
import math
from collections import Counter
a, b = map(int, input().split())
n = fractions.gcd(a, b)

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(n))+1):
  while n % i == 0:
    n /= i
    prime_count[i] += 1
if n > 1:
  prime_count[int(n)] += 1

print(len(prime_count)+1)

Buggy python submission (verdict: Runtime Error):
import math
from collections import Counter
a, b = map(int, input().split())
n = math.gcd(a, b)

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(n))+1):
  while n % i == 0:
    n /= i
    prime_count[i] += 1
if n > 1:
  prime_count[int(n)] += 1

print(len(prime_count)+1)

Fixed submission:
import fractions
import math
from collections import Counter
a, b = map(int, input().split())
n = fractions.gcd(a, b)

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(n))+1):
  while n % i == 0:
    n /= i
    prime_count[i] += 1
if n > 1:
  prime_count[int(n)] += 1

print(len(prime_count)+1)

Buggy python submission (verdict: Runtime Error):

import math
from collections import Counter
a, b = map(int, input().split())
n = math.gcd(a, b)

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(n))+1):
  while n % i == 0:
    n /= i
    prime_count[i] += 1
if n > 1:
  prime_count[int(n)] += 1

print(len(prime_count)+1)

Fixed submission:
import fractions
import math
from collections import Counter
a, b = map(int, input().split())
n = fractions.gcd(a, b)

prime_count = Counter()
for i in range(2, math.ceil(math.sqrt(n))+1):
  while n % i == 0:
    n /= i
    prime_count[i] += 1
if n > 1:
  prime_count[int(n)] += 1

print(len(prime_count)+1)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
key = []
for _ in range(M):
  a, b = map(int, input().split())
  s = 0
  C = list(map(lambda x:int(x)-1, input().split()))
  for c in C:
    s |= 1<<c
  key += [(s, a)]
  
dp = [float('inf')]*(1<<N)
dp[0] = 0
for s in range(1<<N):
  for i in range(M):
    t = s | key[i][0] # 遷移先
    cost = dp[s] + key[i][1]
    dp[t] = min(dp[t], cost)
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])






Fixed submission:
N, M = map(int, input().split())
key = []
for _ in range(M):
  a, b = map(int, input().split())
  s = 0
  C = list(map(lambda x:int(x)-1, input().split()))
  for c in C:
    s |= 1<<c
  key += [(s, a)]
  
dp = [float('inf')]*(1<<N)
dp[0] = 0
for s in range(1<<N):
  for i in range(M):
    t = s | key[i][0] # 遷移先
    cost = dp[s] + key[i][1]
    dp[t] = min(dp[t], cost)
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())
dp = [[0]*N for _ in range(N)]
dp[N-1][N-1] = 1
for i in range(N-1, -1, -1):
  if S[i] == S[-1]:
    dp[N-1][i] = 1

for i in range(N-1, -1, -1):
  if S[i] == S[-1]:
    dp[i][N-1] = 1

for i in range(N-1, 0, -1):
  for j in range(N-1, 0, -1):
    if S[i-1] == S[j-1]:
      dp[i-1][j-1] = dp[i][j] + 1

ans = 0
for i in range(N):
  for j in range(i+1, N):
    ans = max(ans, min(dp[i][j], j-i))
print(ans)

Fixed submission:
N = int(input())
S = list(input())
dp = [[0]*N for _ in range(N)]
dp[N-1][N-1] = 1
for i in range(N-1, -1, -1):
  if S[i] == S[-1]:
    dp[N-1][i] = 1

for i in range(N-1, -1, -1):
  if S[i] == S[-1]:
    dp[i][N-1] = 1

for i in range(N-1, 0, -1):
  for j in range(N-1, 0, -1):
    if S[i-1] == S[j-1]:
      dp[i-1][j-1] = dp[i][j] + 1

ans = 0
for i in range(N):
  for j in range(i+1, N):
    ans = max(ans, min(dp[i][j], j-i))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N = int(input())
A = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
q = deque([])

# 選手iが試合ができるかをチェックして、できるならばキューに入れる
def check(i, q):
  if len(A[i]) == 0:
    return
  j = A[i][-1]
  if len(A[j]) == 0:
    return
  if A[j][-1] == i:
    if i > j:
      i, j = j, i
    q.append((i, j))
  return 

for i in range(N):
  check(i, q)

day = 0
while q:
  day += 1
  q = set(sorted(q))
  prev = deque([])
  prev, q = q, prev
  for i, j in prev:
    A[i].pop(-1)
    A[j].pop(-1)
  for i, j in prev:
    check(i, q)
    check(j, q)
  
for i in range(N):
  if len(A[i]) != 0:
    print(-1)
    exit()

print(day)



Fixed submission:
from collections import deque
N = int(input())
A = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
q = deque([])

# 選手iが試合ができるかをチェックして、できるならばキューに入れる
def check(i, q):
  if len(A[i]) == 0:
    return
  j = A[i][-1]
  if len(A[j]) == 0:
    return
  if A[j][-1] == i:
    if i > j:
      i, j = j, i
    q.append((i, j))
  return 

for i in range(N):
  check(i, q)

day = 0
while q:
  day += 1
  q = set(sorted(q))
  prev = deque([])
  prev, q = q, prev
  for i, j in prev:
    A[i].pop(-1)
    A[j].pop(-1)
  for i, j in prev:
    check(i, q)
    check(j, q)
  
for i in range(N):
  if len(A[i]) != 0:
    print(-1)
    exit()

print(day)