Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def unite(x, y, s_list):
    x_list = None
    y_list = None
    for s in s_list:
        if x in s and y in s:
            x_list = s.copy()
            y_list = s.copy()
            del s
        elif x in s:
            x_list = s.copy()
            del s
        elif y in s:
            y_list = s.copy()
            del s
    if x_list != None and y_list != None:
        s_list.append(list(set(x_list + y_list)))
    elif x_list != None and y_list == None:
        x_list.append(y)
        s_list.append(x_list)
    elif x_list == None and y_list != None:
        y_list.append(x)
        s_list.append(y_list)
    else:
        s_list.append([x, y])

def same(x, y, s_list):
    x_list = None
    y_list = None
    for s in s_list:
        if x in s and y in s:
            return 1
    return 0


n, q = list(map(int, input().split()))
com_list = list()
x_list = list()
y_list = list()
s_list = list()

for _ in range(q):
    com, x, y = list(map(int, input().split()))
    com_list.append(com)
    x_list.append(x)
    y_list.append(y)

for i in range(q):
    com = com_list[i]
    x = x_list[i]
    y = y_list[i]
    if com == 0:
        unite(x, y, s_list)
    else:
        result = same(x, y, s_list)
        print(result)

    

Fixed submission:
def make_set(x, disjoint):
    disjoint[x] = x

def find_set(x, disjoint):
    if x not in disjoint.keys():
        make_set(x, disjoint)
    if x != disjoint[x]:
        disjoint[x] = find_set(disjoint[x], disjoint)
    return disjoint[x]

def link(x, y, disjoint):
    disjoint[y] = x

def unite(x, y, disjoint):
    link(find_set(x, disjoint), find_set(y, disjoint), disjoint)

def same(x, y, disjoint):
    if find_set(x, disjoint) == find_set(y, disjoint):
        return 1
    return 0

n, q = list(map(int, input().split()))
com_list = list()
x_list = list()
y_list = list()

for _ in range(q):
    com, x, y = list(map(int, input().split()))
    com_list.append(com)
    x_list.append(x)
    y_list.append(y)

disjoint = dict()

for i in range(q):
    com = com_list[i]
    x = x_list[i]
    y = y_list[i]

    if com == 0:
        unite(x, y, disjoint)
    else:
        print(same(x, y, disjoint))
Buggy python submission (verdict: Runtime Error):
def fibonacci(n):
    if n == 0 or n == 1:
         F[n] = 1
        return F[n]
    if F[n] is not None:
        return F[n]
    F[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return F[n]


n = int(input())
F = [None] * n

Fixed submission:
def fibonacci(n):
    if n == 0 or n == 1:
        F[n] = 1
        return F[n]
    if F[n] is not None:
        return F[n]
    F[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return F[n]


n = int(input())
F = [None]*(n + 1)
print(fibonacci(n))

Buggy python submission (verdict: Runtime Error):
def fibonacci(n):
    if n == 0 or n == 1:
         F[n] = 1
        return F[n]
    if F[n] is not None:
        return F[n]
    F[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return F[n]


n = int(input())
F = [None] * n
print(fibonacci(n))

Fixed submission:
def fibonacci(n):
    if n == 0 or n == 1:
        F[n] = 1
        return F[n]
    if F[n] is not None:
        return F[n]
    F[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return F[n]


n = int(input())
F = [None]*(n + 1)
print(fibonacci(n))
Buggy python submission (verdict: Runtime Error):
INF = 9999


def prim(M):
    n = len(M)
    color = [0] * n
    d = [INF] * n
    d[0] = 0

    while True:
        minv = INF
        u = -1
        for i in range(n):
            # Black:2
            if minv > d[i] and color[i] != 2:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = 2

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
    return sum(d)


if __name__ == '__main__':
    n = int(input())
    A = []
    for i in range(n):
        for j in range(n):
            src = input()
            dst = src.replace('-1', 'INF')
            ai = list(map(int, dst.split()))
            A.append(ai)
    print(prim(A))

Fixed submission:
INF = 9999


def prim(M):
    n = len(M)
    color = [0] * n
    d = [INF] * n
    d[0] = 0

    while True:
        minv = INF
        u = -1
        for i in range(n):
            # Black:2
            if minv > d[i] and color[i] != 2:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = 2

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
    return sum(d)


if __name__ == '__main__':
    n = int(input())
    A = []
    for i in range(n):
        src = input()
        dst = src.replace('-1', str(INF))
        ai = list(map(int, dst.split()))
        A.append(ai)
    print(prim(A))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
r = [int(input()) for i in range(N)]

max_value = (-1)*(10 ** 9)
for j in range(1,len(r)):
    for i in range(0,j):
        max_value = max(max_value, r[j]-r[i])
print(max_value)

Fixed submission:
# ??\?????????
N = int(input())
r = [int(input()) for i in range(N)]

# ?????§????¨????
max_profit = (-1) * (10 ** 9)
min_value = r[0]
for j in range(1, len(r)):
    max_profit = max(max_profit, r[j] - min_value)
    min_value = min(min_value, r[j])
print(max_profit)
Buggy python submission (verdict: Runtime Error):
def linearSearch(A, n, key):
    i = 0
    A.append(key)
    while A[i] != key:
        i += 1
    del A[n]
    return i != n


if __name__ == '__main__':
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))
    cnt = 0

    for i in q:
        if linearSearch(S, n,T[i]):
            cnt += 1

    print(cnt)

Fixed submission:
def linearSearch(A, n, key):
    i = 0
    A.append(key)
    while A[i] != key:
        i += 1
    del A[n]
    return i != n


if __name__ == '__main__':
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))
    cnt = 0

    for i in range(q):
        if linearSearch(S, n,T[i]):
            cnt += 1

    print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
def h1(key):
    return key % m


def h2(key):
    return 1 + key % (m - 1)


def h(key, i):
    return h1(key + i * h2(key)) % m


def insert(T, key):
    i = 0
    while True:
        j = h(key, i)
        if T[j] is None:
            T[j] = key
            return j
        else:
            i += 1


def search(T, key):
    i = 0
    while True:
        j = h(key, i)
        if T[j] == key:
            return j
        elif T[j] is None or i >= m:
            return None
        else:
            i += 1


global m
r = {"A": 1, "C": 2, "G": 3, "T": 4, }
t = []
m = int(input())
for i in range(m):
    cmd, key = input().split()
    if cmd == "insert":
        t.append(key)
    else:
        if key in t:
            print("yes")
        else:
            print("no")

Fixed submission:
t = set()
m = int(input())
for i in range(m):
    cmd, key = input().split()
    if cmd == "insert":
        t.add(key)
    else:
        if key in t:
            print("yes")
        else:
            print("no")
Buggy python submission (verdict: Runtime Error):
class DisjoinSet:
    def __init__(self, size):
        self.rank = [0 for _ in range(size)]
        self.p = [0 for _ in range(size)]
        for i in range(n):
            self.makeSet(i)

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = x

    def same(self, x, y):
        print(int(self.findSet(x) == self.findSet(y)))

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    # ???????±???????
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


if __name__ == '__main__':
    n, q = map(int, input().split())
    D = DisjoinSet(n)
    cmd = {0: lambda x, y: D.unite(x, y), 1: lambda x, y: D.same(x, y)}
    for _ in range(q):
        c, x, y = map(int, input().split())
        cmd[c](x, y)

Fixed submission:
class DisjoinSet:
    def __init__(self, size):
        self.rank = [0 for _ in range(size)]
        self.p = [0 for _ in range(size)]
        for i in range(n):
            self.makeSet(i)

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def same(self, x, y):
        print(int(self.findSet(x) == self.findSet(y)))

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    # ???????±???????
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


if __name__ == '__main__':
    n, q = map(int, input().split())
    D = DisjoinSet(n)
    cmd = {0: lambda x, y: D.unite(x, y), 1: lambda x, y: D.same(x, y)}
    for _ in range(q):
        c, x, y = map(int, input().split())
        cmd[c](x, y)
Buggy python submission (verdict: Runtime Error):
def get_longest_count(X, Y):
  count = 0
  while len(X) > 0 and len(Y) > 0:
    if X[-1] != Y[-1]:
      return count + max(get_longest_count(X[:-1], Y), get_longest_count(X, Y[:-1]))
    else:
      X = X[:-1]
      Y = Y[:-1]
      count += 1
  return count

for i in range(int(input())):
  X = input()
  Y = input()
  print(get_longest_count(X, Y))

Fixed submission:
def get_longest_count(X, Y):
  offsets = [0]
  for y in Y:
    tmp = offsets[:]
    for i, o in enumerate(offsets):
      j = X.find(y, o)
      if j < 0: break
      if i < len(offsets) - 1:
        tmp[i + 1] = min(offsets[i + 1], j + 1)
      else:
        tmp.append(j + 1)
    offsets = tmp
  return len(offsets) - 1

for i in range(int(input())):
  X = input()
  Y = input()
  print(get_longest_count(X, Y))

Buggy python submission (verdict: Time Limit Exceeded):
def get_longest_count(X, Y):
  m = [[0] * (len(Y) + 1) for i in range(len(X) + 1)]
  for i in range(1, len(X) + 1):
    for j in range(1, len(Y) + 1):
      if X[i - 1] == Y[j - 1]:
        m[i][j] = m[i - 1][j - 1] + 1
      else:
        m[i][j] = max(m[i][j - 1], m[i - 1][j])
  return m[-1][-1]

for i in range(int(input())):
  X = input()
  Y = input()
  print(get_longest_count(X, Y))

Fixed submission:
def get_longest_count(X, Y):
  offsets = [0]
  for y in Y:
    tmp = offsets[:]
    for i, o in enumerate(offsets):
      j = X.find(y, o)
      if j < 0: break
      if i < len(offsets) - 1:
        tmp[i + 1] = min(offsets[i + 1], j + 1)
      else:
        tmp.append(j + 1)
    offsets = tmp
  return len(offsets) - 1

for i in range(int(input())):
  X = input()
  Y = input()
  print(get_longest_count(X, Y))
Buggy python submission (verdict: Time Limit Exceeded):
def bfs(s, t):
  q = [s]
  visited = []
  while len(q) > 0:
    v = q.pop(0)
    if v == t: return True
    if v not in visited and len(G[v]) > 0:
      q.extend(sorted(G[v]))
      visited.append(v)
  return False

u, n = map(int, input().split())
G = [[] for _ in range(u)]
for _ in range(n):
  a, b = map(int, input().split())
  if b not in G[a]: G[a].append(b)
  if a not in G[b]: G[b].append(a)

q = int(input())
for _ in range(q):
  s, t = map(int, input().split())
  if bfs(s, t):
    print("yes")
  else:
    print("no")

Fixed submission:
def grouping(G):
  gid_list = [0] * len(G)

  gid = 1
  for i, _ in enumerate(G):
    if gid_list[i] > 0: continue
    q = [i]
    while len(q) > 0:
      v = q.pop(0)
      gid_list[v] = gid
      for v in sorted(G[v]):
        if gid_list[v] <= 0: q.append(v)
    gid += 1
  return gid_list

u, n = map(int, input().split())
G = [[] for _ in range(u)]
for _ in range(n):
  a, b = map(int, input().split())
  if b not in G[a]: G[a].append(b)
  if a not in G[b]: G[b].append(a)

gid_list = grouping(G)

q = int(input())
for _ in range(q):
  s, t = map(int, input().split())
  if gid_list[s] == gid_list[t]:
    print("yes")
  else:
    print("no")
Buggy python submission (verdict: Time Limit Exceeded):
prime_numbers = [2]
def is_prime(n):
  if n in prime_numbers: return True
  if n > prime_numbers[-1]:
    for i in range(prime_numbers[-1] + 1, n):
      is_prime(i)

  for i in prime_numbers:
    if i ** 2 > n: break
    if n % i == 0: return False
  prime_numbers.append(n)
  return True

N = int(input())
count = 0
for i in range(N):
  x = int(input())
  if is_prime(x): count += 1
print(count)

Fixed submission:
def is_prime(n):
  if n < 2: return False
  for i in range(2, int(n ** 0.5) + 1):
    if n % i == 0: return False
  return True

count = 0
for i in range(int(input())):
  if is_prime(int(input())) : count += 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
p = [int(input()) for i in range(n)]

diff = -float('inf')
for i in range(n):
  for j in range(i + 1, n):
    diff = max(diff, p[j] - p[i])

print(diff)

Fixed submission:
import sys

n = int(input())

max_diff = - 10 ** 9
min_n = int(input())

for n in map(int, sys.stdin.readlines()):
  max_diff = max(max_diff, n - min_n)
  min_n = min(min_n, n)

print(max_diff)
Buggy python submission (verdict: Runtime Error):
def insertion_sort(A, n, g, cnt):
  for i in range(g, n):
    v = A[i]
    j = i - g
    while j >= 0 and A[j] > v:
      A[j + g] = A[j]
      j = j - g
      cnt += 1
    A[j + g] = v
  return cnt

def shell_sort(A, n):
  cnt = 0
  m = 5
  G = [5,4,3,2,1]
  for i in range(m):
    cnt = insertion_sort(A, n, G[i], cnt)
  return m, G, cnt

data = []
for i in range(int(input())):
  data.append(int(input()))

m, G, cnt = shell_sort(data, 5)
print(m)
print(" ".join(map(str, G)))
print(cnt)
for i in data: print(i)

Fixed submission:
def insertion_sort(A, n, g, cnt):
  for i in range(g, n):
    v = A[i]
    j = i - g
    while j >= 0 and A[j] > v:
      A[j + g] = A[j]
      j = j - g
      cnt += 1
    A[j + g] = v
  return cnt

def shell_sort(A, n):
  cnt = 0
  G = []
  h = 1
  while h <= n:
    G.append(h)
    h = h * 3 + 1
  m = len(G)
  G = G[::-1]

  for i in range(m):
    cnt = insertion_sort(A, n, G[i], cnt)

  return m, G, cnt

data = []
for i in range(int(input())):
  data.append(int(input()))

m, G, cnt = shell_sort(data, len(data))
print(m)
print(" ".join(map(str, G)))
print(cnt)
for i in data: print(i)
Buggy python submission (verdict: Time Limit Exceeded):
dic = []

for i in range(int(input())):
  cmd, arg = input().split()
  if cmd == "insert":
    dic.append(arg)
  else:
    if arg in dic:
      print("yes")
    else:
      print("no")

Fixed submission:
dic = {}

for i in range(int(input())):
  cmd, arg = input().split()
  if cmd == "insert":
    dic[arg] = 0
  else:
    if arg in dic:
      print("yes")
    else:
      print("no")

Buggy python submission (verdict: Time Limit Exceeded):
dic = {"A":[], "C":[], "G":[], "T":[]}

for i in range(int(input())):
  cmd, arg = input().split()
  if cmd == "insert":
    dic[arg[0]].append(arg)
  else:
    if arg in dic[arg[0]]:
      print("yes")
    else:
      print("no")

Fixed submission:
dic = {}

for i in range(int(input())):
  cmd, arg = input().split()
  if cmd == "insert":
    dic[arg] = 0
  else:
    if arg in dic:
      print("yes")
    else:
      print("no")
Buggy python submission (verdict: Time Limit Exceeded):
def solve(p, t):
  if p >= len(A): return False
  if t == A[p]: return True
  if t <= 0: return False
  #print("({}, {})".format(p, t))

  if solve(p + 1, t):
    return True
  else:
    return solve(p + 1, t - A[p])

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

for t in M:
  if solve(0, t): print("yes")
  else: print("no")

Fixed submission:
memo = {}
def solve(p, t):
  key = "{}:{}".format(p, t)
  if key in memo: return memo[key]
  if p >= len(A): return False
  if t == A[p]: return True
  if t <= 0: return False
  #print("({}, {})".format(p, t))

  if solve(p + 1, t):
    memo["{}:{}".format(p + 1, t)] = True
    return True
  else:
    memo["{}:{}".format(p + 1, t)] = False
    return solve(p + 1, t - A[p])

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

for t in M:
  if solve(0, t): print("yes")
  else: print("no")
Buggy python submission (verdict: Time Limit Exceeded):
def merge(A, l, m, r):
  n1 = m - l
  n2 = r - m
  L = [0] * (n1 + 1)
  R = [0] * (n2 + 1)

  for i in range(n1): L[i] = A[l + i]
  for i in range(n2): R[i] = A[m + i]
  L[n1] = float('inf')
  R[n2] = float('inf')

  i = 0
  j = 0
  count = 0
  for k in range(l, r):
    count += 1
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
  return count

def merge_sort(A, l, r):
  count = 0
  if l + 1 < r:
    m = (l + r) // 2
    count += merge_sort(A, l, m)
    count += merge_sort(A, m, r)
    count += merge(A, l, m, r)
  return count

n = int(input())
A = list(map(int, input().split()))
count = merge_sort(A, 0, len(A))
print(" ".join(map(str, A)))
print(count)

Fixed submission:
def merge(A, l, m, r):
  L = A[l:m] + [SENTINEL]
  R = A[m:r] + [SENTINEL]

  i = 0
  j = 0
  for k in range(l, r):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
  global count
  count += r - l

def merge_sort(A, l, r):
  if l + 1 < r:
    m = (l + r) // 2
    merge_sort(A, l, m)
    merge_sort(A, m, r)
    merge(A, l, m, r)

SENTINEL = float('inf')
n = int(input())
A = list(map(int, input().split()))
count = 0
merge_sort(A, 0, len(A))
print(" ".join(map(str, A)))
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int, input().split()))

cnt = 0
for i in range(len(A) - 1):
  for j in range(i + 1, len(A)):
    if A[i] > A[j]: cnt += 1

print(cnt)

Fixed submission:
SENTINEL = 1000000001

def merge(A, l, m, r):
  L = A[l:m] + [SENTINEL]
  R = A[m:r] + [SENTINEL]
  i = 0
  j = 0
  cnt = 0
  for k in range(l, r):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
      cnt += len(L) - 1 - i
  return cnt

def merge_sort(A, l, r):
  if l + 1 < r:
    m = (l + r) // 2
    cnt = 0
    cnt += merge_sort(A, l, m)
    cnt += merge_sort(A, m, r)
    cnt += merge(A, l, m, r)
    return cnt
  else:
    return 0

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

print(merge_sort(A, 0, n))
Buggy python submission (verdict: Time Limit Exceeded):
def max_heapify(A, i):
  H = len(A) - 1
  l, r, m = i*2, i*2+1, i
  if l <= H and A[l] > A[i]: m = l
  if r <= H and A[r] > A[m]: m = r

  if m != i:
    A[i], A[m] = A[m], A[i]
    max_heapify(A, m)

def build_max_heap(A):
  H = len(A) - 1
  for i in range(H // 2, 0, -1):
    max_heapify(A, i)

A = [0]
cmd = input()
while cmd != "end":
  if cmd == "extract":
    if len(A) <= 2:
      print(A.pop())
    else:
      print(A[1])
      A[1] = A.pop()
      max_heapify(A, 1)
  else:
    cmd, k = cmd.split()
    if cmd == "insert":
      A.append(int(k))
      build_max_heap(A)
  cmd = input()

Fixed submission:
import sys

def max_heapify(A, H, i):
  target = A[i]

  m = i
  l = i * 2
  while l <= H:
    largest = target
    if A[l] > target:
      m = l
      largest = A[m]

    r = l + 1
    if r <= H and A[r] > largest:
      m = r
      largest = A[m]

    if m != i:
      A[i] = largest
      i = m
      l = i * 2
    else:
      break

  A[m] = target

def build_max_heap(A, i):
  if i < 2: return
  last = A[i]
  p = i // 2
  while p > 0 and A[p] < last:
    A[i] = A[p]
    i = p
    p = i // 2
  A[i] = last

A = [0]

for line in sys.stdin.readlines():
  if line[0] == 'i':
    A.append(int(line[7:]))
    build_max_heap(A, len(A) - 1)
  elif line[1] == 'x':
    if len(A) <= 1:
      pass
    elif len(A) <= 2:
      print(A.pop())
    else:
      print(A[1])
      A[1] = A.pop()
      max_heapify(A, len(A) -1, 1)
  else:
    exit()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def max_heapify(A, i):
  H = len(A) - 1
  l, r, m = i*2, i*2+1, i
  if l <= H and A[l] > A[i]: m = l
  if r <= H and A[r] > A[m]: m = r

  if m != i:
    A[i], A[m] = A[m], A[i]
    max_heapify(A, m)

def build_max_heap(A):
  H = len(A) - 1
  for i in range(H // 2, 0, -1):
    max_heapify(A, i)

A = [0]

for line in sys.stdin.readlines():
  if line[0] == 'i':
    A.append(int(line[7:]))
    build_max_heap(A)
  elif line[1] == 'x':
    if len(A) <= 2:
      print(A.pop())
    else:
      print(A[1])
      A[1] = A.pop()
      max_heapify(A, 1)
  else:
    exit()

Fixed submission:
import sys

def max_heapify(A, H, i):
  target = A[i]

  m = i
  l = i * 2
  while l <= H:
    largest = target
    if A[l] > target:
      m = l
      largest = A[m]

    r = l + 1
    if r <= H and A[r] > largest:
      m = r
      largest = A[m]

    if m != i:
      A[i] = largest
      i = m
      l = i * 2
    else:
      break

  A[m] = target

def build_max_heap(A, i):
  if i < 2: return
  last = A[i]
  p = i // 2
  while p > 0 and A[p] < last:
    A[i] = A[p]
    i = p
    p = i // 2
  A[i] = last

A = [0]

for line in sys.stdin.readlines():
  if line[0] == 'i':
    A.append(int(line[7:]))
    build_max_heap(A, len(A) - 1)
  elif line[1] == 'x':
    if len(A) <= 1:
      pass
    elif len(A) <= 2:
      print(A.pop())
    else:
      print(A[1])
      A[1] = A.pop()
      max_heapify(A, len(A) -1, 1)
  else:
    exit()
Buggy python submission (verdict: Runtime Error):
def makeFibonacci(n):
    F = [None]*n
    F[0] = 1
    F[1] = 1
    for i in range(2, n):
        F[i] = F[i-1] + F[i - 2]
    return str(F[n-1])

n = int(input())
print(makeFibonacci(n))

Fixed submission:
def makeFibonacci(n):
    if n <= 1:
        return str(1)
    F = [None]*(n+1)
    F[0] = 1
    F[1] = 1
    for i in range(2, n+1):
        F[i] = F[i-1] + F[i - 2]
    return str(F[n])

n = int(input())
print(makeFibonacci(n))