Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
k,s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                count += 1
print(count)

Fixed submission:
k,s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z >= 0 and z <= k:
            count += 1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
k, s = map(int, input().split())
k += 1
count = 0
for x in range(k):
    for y in range(k):
        for z in range(k):
            if x + y + z == s:
                count += 1
            elif x + y + z > s:
                continue
print(count)

Fixed submission:
k,s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z >= 0 and z <= k:
            count += 1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
k, s = map(int, input().split())
k += 1
count = 0
for x in range(k):
    for y in range(k):
        for z in range(k):
            if x + y + z == s:
                count += 1
print(count)

Fixed submission:
k,s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z >= 0 and z <= k:
            count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
ans = 0
tmp = 1

for i in range(n):
  if a[i] == tmp:
    tmp += 1
  else:
    ans += 1

if ans = 0:
  print(-1)
else:
  print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
ans = 0
tmp = 1

for i in range(n):
  if a[i] == tmp:
    tmp += 1
  else:
    ans += 1

if ans != 0 and tmp ==1:
  print(-1)
else:
  print(ans)
Buggy python submission (verdict: Runtime Error):
import math
X = int(input())

def dfs(price):
  if price > X:
    return 0
  ret = 1 if price == X else 0
  for pri in range(100, 106):
    ret += dfs(price+pri)
  return ret

if dfs(0) > 0:
  print(1)
else:
  print(0)

Fixed submission:
X = int(input())

num = X // 100

if num * 100 <= X <= num * 105:
  print(1)
else:
  print(0)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(x) for x in input().split()]
ans_list = []
for i in range(1, len(A) + 1):
  #print(i)
  for j in range(1, len(A) + 1):
    #print(j)
    if i == A[j - 1]:
      ans_list.append(j)
      break
map_ans_list = map(str, ans_list)
print(' '.join(map_ans_list))

Fixed submission:
N = int(input())
A = [int(x) for x in input().split()]
ans_list = [0]*N
for i, j in enumerate(A, 1): #enumerate -> インデックス番号、要素の順に取得
  ans_list[j - 1] = i

print(' '.join(map(str, ans_list)))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = [int(_) for _ in input().split()]

while M != 0:
  ind = A.index(max(A))
  A[ind] = A[ind] // 2
  M -= 1
  
print(sum(A))

Fixed submission:
S = input()
ans_list = ["Sunny", "Cloudy", "Rainy", "Sunny"]
for i in range(3):
  if S == ans_list[i]:
    ans = ans_list[i+1]

print(ans)

Buggy python submission (verdict: Runtime Error):
S = input()
ans_list = ["Sunny", "Cloudy", "Rainy", "Sunny"]
for i in range(2):
  if S == ans_list[i]:
    ans = ans_list[i+1]

print(ans)

Fixed submission:
S = input()
ans_list = ["Sunny", "Cloudy", "Rainy", "Sunny"]
for i in range(3):
  if S == ans_list[i]:
    ans = ans_list[i+1]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = [int(_) for _ in input().split()]

for i in range(M):
  ind = A.index(max(A))
  A[ind] = A[ind] // 2
  
print(sum(A))

Fixed submission:
import heapq
N, M = map(int, input().split())
A = [int(_)*(-1) for _ in input().split()]
heapq.heapify(A)

while M != 0:
  max_ = -heapq.heappop(A) // 2
  heapq.heappush(A, -max_)
  M -= 1
  
print(-sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = [int(_) for _ in input().split()]

while M != 0:
  ind = A.index(max(A))
  A[ind] = A[ind] // 2
  M -= 1
  
print(sum(A))

Fixed submission:
import heapq
N, M = map(int, input().split())
A = [int(_)*(-1) for _ in input().split()]
heapq.heapify(A)

while M != 0:
  max_ = -heapq.heappop(A) // 2
  heapq.heappush(A, -max_)
  M -= 1
  
print(-sum(A))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = [int(_) for _ in input().split()]

while M != 0:
  A.sort(reverse=True)
  A[0] = A[0] // 2
  M -= 1
  
print(sum(A))

Fixed submission:
import heapq
N, M = map(int, input().split())
A = [int(_)*(-1) for _ in input().split()]
heapq.heapify(A)

while M != 0:
  max_ = -heapq.heappop(A) // 2
  heapq.heappush(A, -max_)
  M -= 1
  
print(-sum(A))
Buggy python submission (verdict: Runtime Error):
N = int(input())

def dfs(s):
  if int(s) > N: #sがNより大きくなったら再帰終了
    return 0
  ret = 1 if all(s.count(c) > 0 for c in '753') else 0　#sが七五三数ならretに1を入れる
  for c in '753':
    ret += dfs(s+c)
  return ret

print(dfs('0'))　#s='0'からスタート

Fixed submission:
N = int(input())
 
def dfs(s):
  if int(s) > N: 
    return 0
  ret = 1 if all(s.count(c) > 0 for c in '753') else 0
  for c in '753':
    ret += dfs(s+c)
  return ret
 
print(dfs('0'))

Buggy python submission (verdict: Runtime Error):
N = input()
N_ = len(N)
A = N_ * N_ - 1 * N_ - 2

if int(N) < 357:
  print(0)
elif int(N[0]) < 2:
  A = N_ - 1 * N_ - 2 * N_ - 3
elif int(N[0]) == 3 or int(N[0]) == 4:
  A = N_ - 1 * N_ - 2
elif int(N[0]) == 5 int(N[0]) == 6:
  A = 2 * N_ -1 * N_ -2
elif int(N[0]) >= 7:
  A = N_ * N_ - 1 * N_ - 2
  

print(A)


Fixed submission:
N = int(input())
 
def dfs(s):
  if int(s) > N: 
    return 0
  ret = 1 if all(s.count(c) > 0 for c in '753') else 0
  for c in '753':
    ret += dfs(s+c)
  return ret
 
print(dfs('0'))

Buggy python submission (verdict: Time Limit Exceeded):
N = input()
counter = 0

for i in range(1, int(N)+1):
  if 357<= i and i <= 777777753:
    a = str(i)
    if '7' in a and a != '':
      a = a.replace('7', '')
      if '3' in a and a != '':
        a = a.replace('3', '')
        if a != '':
          a = a.replace('5', '')
          if a == '':
            counter += 1
print(counter)

Fixed submission:
N = int(input())
 
def dfs(s):
  if int(s) > N: 
    return 0
  ret = 1 if all(s.count(c) > 0 for c in '753') else 0
  for c in '753':
    ret += dfs(s+c)
  return ret
 
print(dfs('0'))

Buggy python submission (verdict: Time Limit Exceeded):
N = input()
counter = 0

for i in range(1, int(N)+1):
  a = str(i)
  if '7' in a and a != '':
    a = a.replace('7', '')
    if '3' in a and a != '':
      a = a.replace('3', '')
      if a != '':
        a = a.replace('5', '')
        if a == '':
          counter += 1
print(counter)

Fixed submission:
N = int(input())
 
def dfs(s):
  if int(s) > N: 
    return 0
  ret = 1 if all(s.count(c) > 0 for c in '753') else 0
  for c in '753':
    ret += dfs(s+c)
  return ret
 
print(dfs('0'))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
N = int(input())
S = list(input())
ans = []

for i in range(N):
  A = S[:i].count('W') + S[i+1:].count('E')
  if A == 0:
    print(0)
    sys.exit()
  else:
    ans.append(A)
print(min(ans))

Fixed submission:
N = int(input())
S = input()
#左からスタートするとして，全てWならば0になるため
E_count = S.count('E')
W_count = 0
mini_count = E_count

for i in S:
  if i == 'E':
    #リーダーはどちらを向いていても良いので1を引く
    E_count -= 1
  else:
    #Wの場合は，今後向きを変えてもらう必要があるため
    W_count += 1
  if mini_count > E_count + W_count:
    mini_count = E_count + W_count
print(mini_count)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())
ans = []

for i in range(N):
  ans.append(S[:i].count('W') + S[i:].count('E'))
  
print(min(ans))

Fixed submission:
N = int(input())
S = input()
#左からスタートするとして，全てWならば0になるため
E_count = S.count('E')
W_count = 0
mini_count = E_count

for i in S:
  if i == 'E':
    #リーダーはどちらを向いていても良いので1を引く
    E_count -= 1
  else:
    #Wの場合は，今後向きを変えてもらう必要があるため
    W_count += 1
  if mini_count > E_count + W_count:
    mini_count = E_count + W_count
print(mini_count)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
power = 1
A = 10**9 + 7

for i in range(1, N+1):
  power = power * i

ans = power % A

print(ans)

Fixed submission:
N = int(input())
power = 1
A = 10**9 + 7

  #yをxで割った時の商をa、余りをbとすると、y=ax+b
  #ここにiを掛けると、y=(ax+b)i
  #y=aix+bi、となるので第１項は余りが０になる
  #なので、毎回割って、その余りにのみ注目すれば良い

for i in range(1, N+1):
  power = power * i % A

print(power)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, x = map(int, input().split())
ans = len([_ for _ in range(a, b+1) if _ % x ==0])

print(ans)

Fixed submission:
a, b, x = map(int, input().split())

#aの商と余り、bの商を求める
qa = a // x
qb = b // x
ra = a % x
#bの商からaの商を引く
ans = qb - qa

#ここまでの操作で、a以外の値の内、xで割り切れる値の数がansに入っているため、
#aが割り切れるかどうかで条件分岐させる
if ra == 0:
  print(ans+1)
else:
  print(ans)

Buggy python submission (verdict: Runtime Error):
a, b, x = map(int, input().split())
#aからbまでをliに格納
li = list(range(a, b+1))
ans = 0

#liの要素数だけfor文を回す
for i in range(len(li)):
  #li[i]がxで割り切れる時
  if li[i] % x == 0:
    #ansに1を追加
    ans += 1
    
print(ans)

Fixed submission:
a, b, x = map(int, input().split())

#aの商と余り、bの商を求める
qa = a // x
qb = b // x
ra = a % x
#bの商からaの商を引く
ans = qb - qa

#ここまでの操作で、a以外の値の内、xで割り切れる値の数がansに入っているため、
#aが割り切れるかどうかで条件分岐させる
if ra == 0:
  print(ans+1)
else:
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
p = list(map(int, input().split()))
count = 0

for i in range(1,N + 1):
	pi = p[i - 1]
	if all(pi <= j for j in p[:i]):
		count += 1

print(count)

Fixed submission:
N = int(input())
p = list(map(int, input().split()))
count = 0
min = p[0]

for i in range(N):
	if p[i] <= min:
		count += 1
		min = p[i]

print(count)
Buggy python submission (verdict: Runtime Error):
    n, m = list(map(int, input().split()))
    if n==m:
        print("Yes")
    else:
        print("No")

Fixed submission:
n, m = list(map(int, input().split()))
if n==m:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
a, b = [input() for i in range(2)]
a_array = []
for i in range(int(b)):
    a_array.append(a)
a_str = "".join(a_array)

b_array = []
for i in range(int(a)):
    b_array.append(b)
b_str = "".join(b_array)


if a_str < b_str:
    print(a_str)
elif b_str < a_str:
    print(b_str)
else:
    print(a_str)


Fixed submission:
a, b = input().split()

a_array = []
for i in range(int(b)):
    a_array.append(a)
a_str = "".join(a_array)

b_array = []
for i in range(int(a)):
    b_array.append(b)
b_str = "".join(b_array)


if a_str < b_str:
    print(a_str)
elif b_str < a_str:
    print(b_str)
else:
    print(a_str)
Buggy python submission (verdict: Time Limit Exceeded):

n = int(input())
P = list(map(int, input().split()))

count = 0
flag = False

for i in range(n):
    for j in range(i+1):
        if P[i] <= P[j]:
            flag = True
        else:
            flag = False
            break
    if flag == True:
        count += 1
    flag = False

print(count)


Fixed submission:

n = int(input())
P = list(map(int, input().split()))

count = 0
m = P[0]
for i in range(n):
    if P[i] <= m:
        count += 1
        m = P[i]
print(count)
Buggy python submission (verdict: Runtime Error):

n, m = int(input()).split()

if m == n:
    print('Yes')
else:
    print('No')

Fixed submission:

n, m = input().split()
n = int(n)
m = int(m)

if m == n:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
N, M = map(int,input().split())
AC_Set = set()
WA_Dict = {}
WA_SUM = 0
for i in range(M):
    num,result = list(input().split())
    if num in AC_Set:
        continue
    else:
        if result == "AC":
            AC_Set.add(num)
            WA_SUM += WA_Dict.get(num)
        else:
            WA_Dict[num] = WA_Dict.get(num,0) + 1

print("{} {}".format(len(AC_Set),WA_SUM))


Fixed submission:
N, M = map(int,input().split())
AC_Set = set()
WA_Dict = {}
WA_SUM = 0
for i in range(M):
    num,result = list(input().split())
    if num in AC_Set:
        continue
    else:
        if result == "AC":
            AC_Set.add(num)
            WA_SUM += WA_Dict.get(num,0)
        else:
            WA_Dict[num] = WA_Dict.get(num,0) + 1

print("{} {}".format(len(AC_Set),WA_SUM))
Buggy python submission (verdict: Runtime Error):
n = input()
s = input()
print(s.count("ABC")

Fixed submission:
n = input()
s = input()
print(s.count("ABC"))
Buggy python submission (verdict: Runtime Error):
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A, B = map(int, input().split())

print(lcm(A, B))


Fixed submission:
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

A,B = map(int, input().split())
print(lcm(A,B))
Buggy python submission (verdict: Runtime Error):
N,M = int(input().split())
if N == M:
  print('Yes')
else:
  print('No')

Fixed submission:
n,m = input().split()
N = int(n)
M = int(m)
if N == M:
  print('Yes')
else:
  print('No')

Buggy python submission (verdict: Runtime Error):
    l = input().split()
     
    if l[0] == l[1]:
      print('Yes')
    else:
      print('No')

Fixed submission:
ls = [int(i) for i in input().split()]

if ls[0] == ls[1]:
  print('Yes')
else :
  print('No')

Buggy python submission (verdict: Runtime Error):
n = input()
m = input()

if n == m:
  print('YES')
else:
  print('NO')
    

Fixed submission:
ls = [int(i) for i in input().split()]

if ls[0] == ls[1]:
  print('Yes')
else :
  print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

P = [int(i) for i in input().split()]

count = 0

for i in range(0, N):
  flag = True
  for j in range(0, i):
    if P[i] > P[j]:
      flag = False
      break
  if flag == True:
    count += 1

print(count)


Fixed submission:
N = int(input())

P = [int(i) for i in input().split()]

count = 1	# 一つ目は絶対OK
min = P[0]

for i in range(1, N):
  if P[i] > min:
    continue
  min = P[i]
  count += 1

print(count)
Buggy python submission (verdict: Runtime Error):
def f(n):
    d = 10
    z = 0
    while d <= n:
        z += (n // d)
	    d = 5 * d
    return z

n = int(input())

if n % 1 == 1: # odd                                                                                                                                    
    print(0)
else: # even                                                                                                                                            
    ans = f(n)
    print(ans)

Fixed submission:
def f(n):
    d, z = 10, 0
    while d <= n:
        z += n // d
        d *= 5
    return z

n = int(input())

ans = 0
if n % 2 == 0: # even                                                                                                                                   
    ans = f(n)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, u, v = map(int, input().split())
V = [ [] for _ in range(n + 1) ]
for _ in range(n - 1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

t, a = 0, 0
tpos, apos = {u:0}, {v:0}

amin = float("-inf")
while len(tpos) > 0:
    t_new = dict() # T moves                                                                                                                            
    for k, v in tpos.items():
        for dst in V[k]:
            t_new[dst] = max(t_new.get(dst, 0), v + 1)
            if dst in apos:
                amin = max(amin, apos[dst])
                del t_new[dst]

    a_new = dict() # A moves                                                                                                                            
    for k, v in apos.items():
        for dst in V[k]:
            a_new[dst] = max(a_new.get(dst, 0), v + 1)
            if dst in t_new:
                amin = max(amin, a_new[dst])
                del t_new[dst]

    tpos = t_new
    apos = a_new

print(amin)


Fixed submission:
n, u, v = map(int, input().split())
V = [ [] for _ in range(n + 1) ]
for _ in range(n - 1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)

import collections

def bfs(x):
    X = [ -1 ] * (n + 1)
    q = collections.deque([ (x, 0) ])
    X[x] = 0
    while q:
        node, dist = q.popleft()
        for dst in V[node]:
            if X[dst] == -1:
                X[dst] = dist + 1
                q.append((dst, dist + 1))
    return X

T = bfs(u)
A = bfs(v)

ans = 0
for i in range(1, len(T)):
    if T[i] < A[i]:
        ans = max(ans, A[i] - 1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

def f(L):
    n = len(L)
    L.sort()
    count = 0
    # a=3 b=4 c=2, c < a + b => 2 < 3+4
    # a < b + c   =>  a - b < c  =>  c > a - b
    # b < c + a   =>  b - a < c  =>  c > b - a
    # c < a + b
    for i in range(n):
        for j in range(i + 1, n):
            a, b = L[i], L[j]
            start = bisect.bisect_left(L, max(a-b, b-a))
            end = bisect.bisect_left(L, a + b)
            for k in range(start, end):
                assert L[k] < a + b
                assert L[k] > a - b
#                assert L[k] > b - a
                if k != i and k != j and L[k] < a + b:
                    # other two checks
                    if L[k] < a + b and a < b + L[k] and b < L[k] + a:
                        count += 1
    return count // 3

assert f([3, 4, 2, 1]) == 1
assert f([1, 1000, 1]) == 0
assert f([218, 786, 704, 233, 645, 728, 389]) == 23

_N = input()
L = list(map(int, input().split()))
ans = f(L)
print(ans)


Fixed submission:
import bisect

def f(L):
    n = len(L)
    L.sort()

    count = 0

    for i in range(n):
        for j in range(i + 1, n):
            a = L[i]
            b = L[j]
            start = max(a - b, b - a)
            end = a + b
            si = bisect.bisect_right(L, start)
            ei = bisect.bisect_left(L, end)
            zx = ei - si
            if i >= si and i < ei:
                zx -= 1
            if j >= si and j < ei:
                zx -= 1
            count += zx
    return count // 3

assert f([3, 4, 2, 1]) == 1
assert f([1, 1000, 1]) == 0
assert f([218, 786, 704, 233, 645, 728, 389]) == 23

_N = input()
L = list(map(int, input().split()))
ans = f(L)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def f(L):
    n = len(L)
    L.sort()
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            a, b = L[i], L[j]
            for k in range(n):
                if k != i and k != j and L[k] < a + b:
                    # other two checks
                    if a < b + L[k] and b < L[k] + a:
                        count += 1
                else:
                    break
    return count

assert f([3, 4, 2, 1]) == 1
assert f([1, 1000, 1]) == 0
assert f([218, 786, 704, 233, 645, 728, 389]) == 23

_N = input()
L = list(map(int, input().split()))
ans = f(L)
print(ans)


Fixed submission:
import bisect

def f(L):
    n = len(L)
    L.sort()

    count = 0

    for i in range(n):
        for j in range(i + 1, n):
            a = L[i]
            b = L[j]
            start = max(a - b, b - a)
            end = a + b
            si = bisect.bisect_right(L, start)
            ei = bisect.bisect_left(L, end)
            zx = ei - si
            if i >= si and i < ei:
                zx -= 1
            if j >= si and j < ei:
                zx -= 1
            count += zx
    return count // 3

assert f([3, 4, 2, 1]) == 1
assert f([1, 1000, 1]) == 0
assert f([218, 786, 704, 233, 645, 728, 389]) == 23

_N = input()
L = list(map(int, input().split()))
ans = f(L)
print(ans)
Buggy python submission (verdict: Runtime Error):
import functools

n = int(input())
A = list(map(int, input().split()))

@functools.lru_cache(None)
def rec(i):
  if i == 0: return 0
  i1 = rec(i - 1) + abs(A[i - 1] - A[i])
  i2 = float("inf")
  if i >= 2:
      i2 = rec(i - 2) + abs(A[i - 2] - A[i])
  return min(i1, i2)

ans = rec(n - 1)
print(ans)


Fixed submission:
def frog(H):
    n = len(H)
    cost = 0
    n_2 = 0
    n_1 = 0
    for i in range(n):
        if i >= 1:
            cost = abs(H[i] - H[i - 1]) + n_1
            if i >= 2:
                cost = min(cost, abs(H[i] - H[i - 2]) + n_2)
        n_2 = n_1
        n_1 = cost
    return cost

assert frog([10, 10, 10]) == 0
assert frog([10, 10]) == 0
assert frog([10, 30, 40, 20]) == 30
assert frog([30, 10, 60, 10, 60, 50]) == 40

n = int(input())
H = list(map(int, input().split()))
ans = frog(H)
print(ans)
Buggy python submission (verdict: Runtime Error):
# AtCoder DP Task F - LCS
def backtrack(C, A, B, i, j):
    if i == 0 or j == 0:
        return ""
    if A[i - 1] == B[j - 1]:
        return backtrack(C, A, B, i - 1, j - 1) + A[i - 1]
    if C[i][j - 1] > C[i - 1][j]:
        return backtrack(C, A, B, i, j - 1)
    return backtrack(C, A, B, i - 1, j)

def lcs(A, B):
    a, b = len(A), len(B)
    C = [ [0] * (b + 1) for _ in range(a + 1) ]
    for i in range(1, a + 1):
        for j in range(1, b + 1):
            if A[i - 1] == B[j - 1]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j - 1], C[i - 1][j])
#    return C[a][b]
    ret = backtrack(C, A, B, a, b)
    return ret

assert lcs("XMJYAUZ", "MZJAWXU") == "MJAU"
assert lcs("AGCAT", "GAC") == "AC"
assert lcs("AAAA", "AAAA") == "AAAA"

x = input().strip()
y = input().strip()
ans = lcs(x, y)
print(ans)


Fixed submission:
# AtCoder DP Task F - LCS
def backtrack(C, A, B, i, j):
    out = ""
    while i != 0 and j != 0:
        if A[i - 1] == B[j - 1]:
            out = A[i - 1] + out
            i -= 1
            j -= 1
        elif C[i][j - 1] > C[i - 1][j]:
            j -= 1
        else:
            i -= 1
    return out

def lcs(A, B):
    a, b = len(A), len(B)
    C = [ [0] * (b + 1) for _ in range(a + 1) ]
    for i in range(1, a + 1):
        for j in range(1, b + 1):
            if A[i - 1] == B[j - 1]:
                C[i][j] = C[i-1][j-1] + 1
            else:
                C[i][j] = max(C[i][j - 1], C[i - 1][j])
#    return C[a][b]
    ret = backtrack(C, A, B, a, b)
    return ret

assert lcs("XMJYAUZ", "MZJAWXU") == "MJAU"
assert lcs("MZJAWXU", "XMJYAUZ") == "MJAU"
assert lcs("AGCAT", "GAC") == "AC"
assert lcs("AAAA", "AAAA") == "AAAA"
assert lcs("a", "z") == ""

if False:
    import random
    for _ in range(1000):
        q = [chr(random.randint(ord('a'), ord('z'))) for _ in range(random.randint(1, 1000))]
        p = [chr(random.randint(ord('a'), ord('z'))) for _ in range(random.randint(1, 1000))]
        lcs("".join(q), "".join(p))

x = input().strip()
y = input().strip()
ans = lcs(x, y)
print(ans)
Buggy python submission (verdict: Runtime Error):
def dfs(node, edges, dp, visited):
    visited.add(node)
    for child in edges.get(node, []):
        if not child in visited:
            dfs(child, edges, dp, visited)
        dp[node] = max(dp[node], 1 + dp[child])

def main(n, edges):
    dp = [0] * (n + 1)
    visited = set()
    for i in range(1, n + 1):
        if not i in visited:
            dfs(i, edges, dp, visited)
    return max(dp)

assert main(6, { 2: [3], 4: [5], 5: [6] }) == 2
assert main(4, { 1: [2, 3], 3: [2, 4], 2: [4] }) == 3

n, m = map(int, input().split())
edges = {}
for _ in range(m):
    u, v = map(int, input().split())
    if u not in edges:
        edges[u] = set([v])
    else:
        edges[u].add(v)
ans = main(n, edges)
print(ans)



Fixed submission:
from collections import deque

def main(n, edges):
    deg = [0] * (n + 1)
    adj = {}

    for j in range(1, n + 1):
        adj[j] = []

    for u, v in edges:
        adj[u].append(v)
        deg[v] += 1

    S = deque()

    dp = [-1] * (n + 1)

    for u in range(1, n + 1):
        if deg[u] == 0:
            S.append(u)
            dp[u] = 0

    L = []

    while S:
        v = S.popleft()
        L.append(v)
        for u in adj[v]:
            deg[u] -= 1
            if deg[u] == 0:
                S.append(u)
                dp[u] = max(dp[u], dp[v] + 1)

    return max(dp)

assert main(6, [ (2, 3), (4, 5), (5, 6) ]) == 2
assert main(4, [ (1, 2), (1, 3), (3, 2), (3, 4), (2, 4) ]) == 3

n, m = map(int, input().split())
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))
ans = main(n, edges)
print(ans)