Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
dp = [-1] * (10 ** 5 + 7)

def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for u in E[v]:
        res = max(res, rec(u) + 1)
    dp[v] = res
    return dp[v]

E = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    E[x-1].append(y-1)

ans = 0
for v in range(N):
    ans = max(ans, rec(v))

print(ans)

Fixed submission:
from collections import deque

N, M = map(int, input().split())

dp = [0] * N
E = [[] for _ in range(N)]
deg = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    E[x-1].append(y-1)
    deg[y-1] += 1

que = deque(v for v in range(N) if deg[v] == 0)
while que:
    v = que.pop()
    for u in E[v]:
        deg[u] -= 1
        if deg[u] == 0:
            que.appendleft(u)
            dp[u] = max(dp[u], dp[v] + 1)

print(max(dp))
Buggy python submission (verdict: Runtime Error):
N = int(input())
K = int(input())
X = list(map(int, input().split()))
res = 0
for x in X:
    res += 2 * min(x, K - x)
print(res)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
print(sum(A[::2]) - sum(A[1::2]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
 
N, Z, W = map(int, input().split())
A = list(map(int, input().split()))
inf = 10 ** 9 + 7
 
sys.setrecursionlimit(inf)
 
def calc(a, b):
  return abs(a - b)
 
def alphaBeta(X, Y, turn, depth, alpha, beta):
    if depth == N:
        return calc(X, Y)
    if turn:
        for i in range(depth, N):
            alpha = max(alpha, alphaBeta(A[i], Y, False, i+1, alpha, beta))
            if alpha >= beta:
                break
        return alpha
    else:
        for i in range(depth, N):
            beta = min(beta, alphaBeta(X, A[i], True, i+1, alpha, beta))
            if alpha >= beta:
                break
        return beta
 
print(alphaBeta(Z, W, True, 0, -1, inf))

Fixed submission:
import sys

N, Z, W = map(int, input().split())
A = list(map(int, input().split()))

ans = abs(A[-1] - W)
if N != 1:
    ans = max(ans, abs(A[-1] - A[-2]))
print(ans)

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

N, Z, W = map(int, input().split())
A = list(map(int, input().split()))
inf = 10 ** 9 + 7

sys.setrecursionlimit(inf)

def calc(a, b):
  return abs(a - b)

def alphaBeta(X, Y, turn, depth, alpha, beta):
    if depth == N:
        return calc(X, Y)
    if turn:
        for i in range(depth, N):
            alpha = max(alpha, alphaBeta(A[i], Y, False, i+1, alpha, beta))
            if alpha >= beta:
                break
        return alpha
    else:
        for i in range(depth, N):
            beta = min(beta, alphaBeta(X, A[i], True, i+1, alpha, beta))
            if alpha >= beta:
                break
        return beta

print(alphaBeta(Z, W, True, 0, -1, inf))

Fixed submission:
import sys

N, Z, W = map(int, input().split())
A = list(map(int, input().split()))

ans = abs(A[-1] - W)
if N != 1:
    ans = max(ans, abs(A[-1] - A[-2]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
def is_bipartite(s=0):
    visited = [False] * N
    colors = [-1] * N
    stack = deque([(0, 0)])
    while stack:
        c, v = stack.pop()
        visited[v] = True
        colors[v] = c
        for u in E[v]:
            if visited[u] == True and (c ^ 1) != colors[u]:
                return False, colors
            if visited[u]:
                continue
            stack.append((c ^ 1, u))
    return True, colors

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
f, bi = is_bipartite()
if f:
    b = sum(bi)
    w = N - b
    print(b * w - M)
else:
    print(N * (N - 1) // 2 - M)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

def is_bipartite(v, d):
    color[v] = d
    for u in E[v]:
        if color[u] == d:
            return False
        elif color[u] != -1:
            continue
        if not is_bipartite(u, (d + 1) % 2):
            return False
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
color = [-1] * N

for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

if is_bipartite(0, 0):
    b = sum(color)
    w = N - b
    print(b * w - M)
else:
    print(N * (N - 1) // 2 - M)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 6)

def is_bipartite(v, r, d):
    color[v] = d
    for u in E[v]:
        if u == r:
            continue
        if color[u] == d:
            return False
        is_bipartite(u, v, (d + 1) % 2)
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
color = [-1] * N

for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

if is_bipartite(0, -1, 0):
    b = sum(color)
    w = N - b
    print(b * w - M)
else:
    print(N * (N - 1) // 2 - M)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)

def is_bipartite(v, d):
    color[v] = d
    for u in E[v]:
        if color[u] == d:
            return False
        elif color[u] != -1:
            continue
        if not is_bipartite(u, (d + 1) % 2):
            return False
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
color = [-1] * N

for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

if is_bipartite(0, 0):
    b = sum(color)
    w = N - b
    print(b * w - M)
else:
    print(N * (N - 1) // 2 - M)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations
MAX = 10 ** 9
def warshall_floyd(n, dist):
    for k in range(n):
        for i in range(n-1):
            for j in range(i, n):
                dist[i][j] = dist[j][i] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
E = [[MAX] * N for _ in range(N)]
for i in range(N):
    E[i][i] = 0
for i in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a][b] = c
    E[b][a] = c
E = warshall_floyd(N, E)
res = MAX
for p in permutations(r):
    tmp = 0
    for i in range(R-1):
        tmp += E[p[i]-1][p[i+1]-1]
    res = min(res, tmp)
print(res)

Fixed submission:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def warshallFloyd():
    for k in range(N):
        for i in range(N-1):
            for j in range(i, N):
                tmp = min(E[i][j], E[i][k] + E[k][j])
                E[i][j] = E[j][i] = tmp

def dfs(c, p, d):
    if c == R:
        ans[0] = min(ans[0], d)
        return
    for i in range(R):
        if used[i]:
            continue
        used[i] = True
        if p == -1:
            dfs(c+1, i, 0)
        else:
            dfs(c+1, i, d + E[S[p]-1][S[i]-1])
        used[i] = False

N, M, R = map(int, input().split())
S = list(map(int, input().split()))
E = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    E[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    E[a][b] = E[b][a] = c
warshallFloyd()
ans = [float('inf')]
used = [False] * R
dfs(0, -1, 0)
print(*ans)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

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

[print(A+B) if A+B < 10 else print('error')]

Fixed submission:
# -*- coding: utf-8 -*-

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

[print(A+B) if A+B < 10 else print('error')]

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

A = int(input())
B = int(input())

[print(A+B) if A+B < 10 else print('error')]

Fixed submission:
# -*- coding: utf-8 -*-

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

[print(A+B) if A+B < 10 else print('error')]
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

N, A, B = map(int, input().split())
H = [int(input()) for x in range(N)] 
c = 0

while H:
    index = max(enumerate(H), key=lambda x: x[1])[0]
    H[index] -= A
    H = [H[x]-B for x in range(len(H)) if x!=index]
    I = [x for x in range(len(H)) if H[x] <= 0]
    [H.pop(x) for x in I]
    c += 1

print(c)

Fixed submission:
import math

def bs(n, a, b, hp, min=0, max=10**9):
    left = min
    right = max
    def count(num):
        base = b * num
        attackcount = 0
        diff = a-b
        for i in range(n):
            tmp = math.ceil((hp[i] - base) / diff)
            if tmp <= 0:
                pass
            else:
                attackcount += tmp
        if attackcount <= num:
            return True
        else:
            return False
    while left != right:
        mid = (left + right) // 2
        if count(mid):
            right = mid
        else:
            left = mid + 1
    return left

if __name__ == '__main__':
    n, a, b = map(int, input().split())
    hp = [int(input()) for i in range(n)]
    print(bs(n, a, b, hp))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

N, A, B = map(int, input().split())
H = []
c = 0
for i in range(N):
    H.append(int(input()))

while max(H) > 0:
    index = max(enumerate(H), key=lambda x: x[1])[0]
    H[index] -= A
    for i in range(len(H)):
        if i != index:
            H[i] -= B
    c += 1

print(c)

Fixed submission:
import math

def bs(n, a, b, hp, min=0, max=10**9):
    left = min
    right = max
    def count(num):
        base = b * num
        attackcount = 0
        diff = a-b
        for i in range(n):
            tmp = math.ceil((hp[i] - base) / diff)
            if tmp <= 0:
                pass
            else:
                attackcount += tmp
        if attackcount <= num:
            return True
        else:
            return False
    while left != right:
        mid = (left + right) // 2
        if count(mid):
            right = mid
        else:
            left = mid + 1
    return left

if __name__ == '__main__':
    n, a, b = map(int, input().split())
    hp = [int(input()) for i in range(n)]
    print(bs(n, a, b, hp))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

H, W = map(int, input().split())
A = []
for i in range(H):
    A.append("#")
    a = input()
    A[i] += a + "#"

A = ["#" * (W+2)] + A + ["#" * (W+2)]

for i in A:
    print(i)

Fixed submission:
# -*- coding: utf-8 -*-

A = set([1,3,5,7,8,10,12])
B = set([4,6,9,11])
C = set([2])

x, y = map(int, input().split())

if x in A and y in A:
    print("Yes")

elif x in B and y in B:
    print("Yes")

elif x in C and y in C:
    print("Yes")

else:
    print("No")
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

H, W = map(int, input().split())
A = []
for i in range(H):
    A.append("#")
    for j in range(W):
        a = input()
        A[i] += a
    A[i] += "#"

A = ["#" * (W+2)] + A + ["#" * (W+2)]

for i in A:
    print(i)

Fixed submission:
# -*- coding: utf-8 -*-

H, W = map(int, input().split())
A = []
for i in range(H):
    A.append("#")
    a = input()
    A[i] += a + "#"

A = ["#" * (W+2)] + A + ["#" * (W+2)]

for i in A:
    print(i)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

H, W = map(int, input().split())
A = []
for i in range(H):
    for j in range(W):
        A[i] += input()

A = ["#" * W+2] + A + ["#" * W+2]

for i in A:
    print(i)

Fixed submission:
# -*- coding: utf-8 -*-

H, W = map(int, input().split())
A = []
for i in range(H):
    A.append("#")
    a = input()
    A[i] += a + "#"

A = ["#" * (W+2)] + A + ["#" * (W+2)]

for i in A:
    print(i)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

H, W = map(int, input().split())
A = [H]

for i in range(1, H):
    a = input()
    A[i] = ['#' + a + '#']

fr = '#' * (W+2)
A = [fr] + A + [fr]

for i in A:
    print(i)

print('#' + 1 + '#')

Fixed submission:
# -*- coding: utf-8 -*-

H, W = map(int, input().split())
A = []
for i in range(H):
    A.append("#")
    a = input()
    A[i] += a + "#"

A = ["#" * (W+2)] + A + ["#" * (W+2)]

for i in A:
    print(i)
Buggy python submission (verdict: Runtime Error):
from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

def complement(c):
    if c=='1':
        return '0'
    else:
        return '1'

H = {}

def pop(n):
    return "{0:b}".format(n).count('1')
def toZero(n):
    if n==0:
        return 0
    if n==1:
        return 1
    if n in H:
        return H[n]
    r = 1 + toZero(n%pop(n))
    H[n] = r
    return r

[N] = getInts()
X = input()
Xi = int(X, 2)
X = list(X)

i=0
p = pop(Xi)
while 2**i < Xi:
    toZero(2**i%(p+1))
    toZero(2**i%(p-1))
    i+=1
for i in range(N):
    X[i] = complement(X[i])
    n = int("".join(X),2)
    print(toZero(n))
    X[i] = complement(X[i])

Fixed submission:
def getInts():
    return [ int(x) for x in input().split() ]

[L,R,d] = getInts()

c = 0
for i in range(L, R+1):
    if i%d==0:
        c+=1
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

[N] = getInts()
As = getInts()

maxV = max(As)
minV = min(As)

count = 0
for i in range(N):
    r2 = min(i+As[i]+minV, N-1)
    for j in range(r2, N):
        if As[j]+As[i] == abs(i-j):
            count += 1
print(count)

Fixed submission:
def getInts():
    return [ int(x) for x in input().split() ]

[N] = getInts()
As = getInts()
A = {}
for i in range(1, N+1):
    A[i] = As[i-1]

L = {}
R = {}
for i in range(1, N+1):
    if i - A[i] not in L:
        L[i-A[i]] = 1
    else:
        L[i-A[i]] += 1
    if i + A[i] not in R:
        R[i+A[i]] = 1
    else:
        R[i+A[i]] += 1
count = 0
for k in R.keys():
    if k in L:
        count += R[k]*L[k]
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def getInts():
    return [ int(x) for x in input().split() ]

[N] = getInts()
As = getInts()

maxV = max(As)
minV = min(As)

count = 0
for i in range(N):
    r1, r2 = max(0, i+1-As[i]-minV), min(i+1+As[i]+maxV, N-1)
    for j in range(r1, r2+1):
        if As[j]+As[i] == abs((j+1)-(i+1)):
            count += 1
print(count)


Fixed submission:
def getInts():
    return [ int(x) for x in input().split() ]

[N] = getInts()
As = getInts()
A = {}
for i in range(1, N+1):
    A[i] = As[i-1]

L = {}
R = {}
for i in range(1, N+1):
    if i - A[i] not in L:
        L[i-A[i]] = 1
    else:
        L[i-A[i]] += 1
    if i + A[i] not in R:
        R[i+A[i]] = 1
    else:
        R[i+A[i]] += 1
count = 0
for k in R.keys():
    if k in L:
        count += R[k]*L[k]
print(count)
Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

n = int(input())

res = 1
for i in range(n):
    a = int(input())
    g = gcd(res, a)
    res = int(res / g) * a

print(res)


Fixed submission:
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

n = int(input())

res = 1
for i in range(n):
    a = int(input())
    g = gcd(res, a)
    res = (res // g) * a

print(res)

Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

n = int(input())

res = 1
for i in range(n):
    a = int(input())
    g = gcd(res, a)
    res = int(res * a / g)

print(res)


Fixed submission:
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

n = int(input())

res = 1
for i in range(n):
    a = int(input())
    g = gcd(res, a)
    res = (res // g) * a

print(res)

Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

n = int(input())

res = 1
for i in range(n):
    a = int(input())
    g = gcd(res, a)
    res = int(res * a / g)

print(str(res))


Fixed submission:
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

n = int(input())

res = 1
for i in range(n):
    a = int(input())
    g = gcd(res, a)
    res = (res // g) * a

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=np.array(list(map(int,readline().split())),dtype=np.int64)

    cnt=0
    while cnt<k:
        s=[0]*n
        for i in range(n):
            x_min=i-a[i]
            x_max=i+a[i]+1
            s[max(0,x_min)]+=1
            if n-1<x_max:
                pass
            else:
                s[x_max]-=1
        a=np.cumsum(s)
        cnt+=1
        
        if a[a==n].size==n:
            break

    print(*a)

if __name__=="__main__":
    main()

Fixed submission:
from sys import stdin
from itertools import accumulate
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=list(map(int,readline().split()))

    cnt=0
    while cnt<k:
        s=[0]*n
        for i in range(n):
            x_min=i-a[i]
            x_max=i+a[i]+1
            s[max(0,x_min)]+=1
            if n-1<x_max:
                pass
            else:
                s[x_max]-=1
        a=list(accumulate(s))
        cnt+=1
        
        flag=True
        for i in range(n):
            if a[i]!=n:
                flag=False
                break
        if flag: break

    print(*a)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
a.sort()
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        break
else:
    print(ans)

Fixed submission:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))
    ans=1

    flag_zero=False
    for i in range(n):
        if a[i]==0:
            flag_zero=True

    if flag_zero:
        print(0)
    else:
        flag=True
        for i in range(n):
            ans*=a[i]
            if ans>10**18:
                flag=False
                break

        if flag:
            print(ans)
        else:
            print(-1)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from math import sin,cos,pi
def main():
    #入力
    readline=stdin.readline
    A,B,H,M=map(int,readline().split())

    s=M*pi/30
    t=(H/6)*pi+(M/360)*pi
    x_A=A*sin(t)
    y_A=A*cos(t)

    x_B=B*sin(s)
    y_B=B*cos(s)

    print(((x_A-x_B)**2+(y_A-y_B)**2)**0.5)
if __name__=="__main__":
    main()

Fixed submission:
from sys import stdin
from math import sin,cos,pi
def main():
    #入力
    readline=stdin.readline
    A,B,H,M=map(int,readline().split())

    s=M*pi/30
    t=(H/6)*pi+(M/360)*pi
    x_A=A*sin(t)
    y_A=A*cos(t)

    x_B=B*sin(s)
    y_B=B*cos(s)

    print(((x_A-x_B)**2+(y_A-y_B)**2)**0.5)
    
if __name__=="__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=list(map(lambda x:int(x)-1,readline().split()))

    d=[]
    x=0
    while pow(2,x)<k:
        li=[0]*n
        if x==0:
            for i in range(n):
                li[i]=a[i]
            d.append(li)
        else:
            for i in range(n):
                j=d[x-1][i]
                li[i]=d[x-1][j]
            d.append(li)
        x+=1

    l=bin(k)[2:]
    x=len(l)
    ans=0
    for i in range(x):
        j=x-i-1
        if l[i]=="1":
            ans=d[j][ans]

    print(ans+1)

if __name__=="__main__":
    main()

Fixed submission:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())
    a=list(map(lambda x:int(x)-1,readline().split()))

    flags=[False]*n

    now=0
    cnt=0
    while True:
        flags[now]=True
        cnt+=1
        nex=a[now]
        if flags[nex]:
            last=now
            break
        else:
            now=nex

    f_cnt=cnt
    cnt=0
    while True:
        nex=a[now]
        if nex==last:
            cnt+=1
            break
        else:
            now=nex
            cnt+=1

    l=k-(f_cnt-cnt)
    if l<0:
        now=0
        for _ in range(k):
            now=a[now]
        print(now+1)
    else:
        l%=cnt
        now=a[last]
        for _ in range(l):
            nex=a[now]
            now=nex

        print(now+1)
if __name__=="__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from sys import stdin
import itertools
import numpy as np
from numba import njit

def main():
#入力
    readline=stdin.readline
    N,M,Q=map(int,readline().split())
    a=np.zeros(Q,dtype=np.int64)
    b=np.zeros(Q,dtype=np.int64)
    c=np.zeros(Q,dtype=np.int64)
    d=np.zeros(Q,dtype=np.int64)
    for i in range(Q):
        a[i],b[i],c[i],d[i]=map(int,readline().split())

    arrays=np.array(list(itertools.combinations_with_replacement(range(1,M+1),N)),dtype=np.int64)
    l=len(arrays)

    print(f(l,Q,a,b,c,d,arrays))
    
@njit("i8(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:])",cache=True)
def f(l,Q,a,b,c,d,arrays):
    max_res=0
    for i in range(l):
        res=0
        for j in range(Q):
            if arrays[i][b[j]-1]-arrays[i][a[j]-1]==c[j]:
                res+=d[j]
        max_res=max(max_res,res)
    return max_res

if __name__=="__main__":
	main()

Fixed submission:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    K=int(readline())
    A,B=map(int,readline().split())
    if A%K==0:
        print("OK")
    elif A//K<B//K:
        print("OK")
    else:
        print("NG")
if __name__=="__main__":
    main()