Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N, K = list(map(int, input().split()))
count = 0
poss = [n for n in range(1, N+1) if (2*n)%K==0]

poss2 = list(itertools.product(poss, repeat=3))

count = len([comb for comb in poss2 if (comb[0]+comb[1])%K==0 and (comb[1]+comb[2])%K==0])
print(count)

Fixed submission:
N, K = map(int, input().split())
num = {i%K:N//K for i in range(1, K+1)}
mod = N % K
for i in range(1, mod+1):
    num[i] += 1

ans = 0
for i in range(K):
    if (2*i) % K == 0:
        cnt = num[i]
        cnt *= num[(K-i)%K] * num[(K-i)%K]
        ans += cnt
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N, K = list(map(int, input().split()))
count = 0
poss = [n for n in range(1, N+1) if (2*n)%K==0]

poss2 = list(itertools.product(poss, repeat=3))

def c(data):
    global count
    if (data[0]+data[1])%K==0 and (data[1]+data[2])%K==0:
        count += 1

for comb in poss2:
    c(comb)

print(count)

Fixed submission:
N, K = map(int, input().split())
num = {i%K:N//K for i in range(1, K+1)}
mod = N % K
for i in range(1, mod+1):
    num[i] += 1

ans = 0
for i in range(K):
    if (2*i) % K == 0:
        cnt = num[i]
        cnt *= num[(K-i)%K] * num[(K-i)%K]
        ans += cnt
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N, K = list(map(int, input().split()))
poss = []
count = 0
poss = [n for n in range(1, N+1) if (2*n)%K==0]

poss2 = list(itertools.product(poss, repeat=3))

for comb in poss2:
    if (comb[0]+comb[1])%K==0 and (comb[1]+comb[2])%K==0: #and (comb[2]+comb[0])%K==0:
        count += 1

print(count)


Fixed submission:
N, K = map(int, input().split())
num = {i%K:N//K for i in range(1, K+1)}
mod = N % K
for i in range(1, mod+1):
    num[i] += 1

ans = 0
for i in range(K):
    if (2*i) % K == 0:
        cnt = num[i]
        cnt *= num[(K-i)%K] * num[(K-i)%K]
        ans += cnt
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N, K = list(map(int, input().split()))
poss = []
result = []
count = 0
for n in range(1, N+1):
    if (2 * n) % K == 0:
        poss.append(n)

#print(poss)
poss2 = list(itertools.product(poss, repeat=3))
#print(poss2)

for comb in poss2:
    if (comb[0]+comb[1])%K==0 and (comb[1]+comb[2])%K==0 and (comb[2]+comb[0])%K==0:
        count += 1

print(count)

Fixed submission:
N, K = map(int, input().split())
num = {i%K:N//K for i in range(1, K+1)}
mod = N % K
for i in range(1, mod+1):
    num[i] += 1

ans = 0
for i in range(K):
    if (2*i) % K == 0:
        cnt = num[i]
        cnt *= num[(K-i)%K] * num[(K-i)%K]
        ans += cnt
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
candles = list(map(int, input().split()))
abs_c = [abs(c) for c in candles]
result = []
for n in range(N-K+1):
    route = candles[n:n+K]
    r1 = abs(route[0]) + abs(route[-1]-route[0])
    r2 = abs(route[-1]) + abs(route[0]-route[-1])
    result.append(min(r1, r2))

print(min(result))

Fixed submission:
N, K = list(map(int, input().split()))
candles = list(map(int, input().split()))
abs_c = [abs(c) for c in candles]
result = []
for n in range(N-K+1):
    r1 = abs(candles[n]) + abs(candles[n+K-1]-candles[n])
    r2 = abs(candles[n+K-1]) + abs(candles[n]-candles[n+K-1])
    result.append(min(r1, r2))

print(min(result))

Buggy python submission (verdict: Time Limit Exceeded):
N, K = list(map(int, input().split()))
candles = list(map(int, input().split()))
abs_c = [abs(c) for c in candles]
result = []
for n in range(N-K+1):
    result.append(sum(abs_c[n:n+K]))

idx = result.index(min(result))
route = candles[idx:idx+K]

r1 = abs(route[0]) + abs(route[-1]-route[0])
r2 = abs(route[-1]) + abs(route[0]-route[-1])
print(min(r1, r2))

Fixed submission:
N, K = list(map(int, input().split()))
candles = list(map(int, input().split()))
abs_c = [abs(c) for c in candles]
result = []
for n in range(N-K+1):
    r1 = abs(candles[n]) + abs(candles[n+K-1]-candles[n])
    r2 = abs(candles[n+K-1]) + abs(candles[n]-candles[n+K-1])
    result.append(min(r1, r2))

print(min(result))
Buggy python submission (verdict: Runtime Error):

S = list(map(int, input()))
K = int(input())
if S[0] == 1:
    print(S[1])
else:
    print(S[0])

Fixed submission:
import math
S = list(map(int, input()))
K = int(input())
count = 0
after_S = 0
days = 5000000000000000-1
for n in S:
    if n == 1:
        count += 1
    else:
        break
if count > 0 and math.log(count) >= math.log(K):
    print(1)
else:
    for n in S:
        after_S += days * math.log(n)
        if after_S >= math.log(K):
            print(n)
            break
Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for _ in range(M)]
questions = [list(map(int, input().split())) for _ in range(Q)]
for q in questions:
    print(len([t for t in trains if q[0] <= t[0] and q[1] >= t[1]]))


Fixed submission:
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())

sum_table = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l, r = map(int, input().split())
    sum_table[l][r] += 1

for i in range(1, N+1):
    for j in range(1, N+1):
        sum_table[i][j] += sum_table[i-1][j] + sum_table[i][j-1] - sum_table[i-1][j-1]

for _ in range(Q):
    p, q = map(int, input().split())
    print(sum_table[q][q] - sum_table[q][p-1] - sum_table[p-1][q] + sum_table[p-1][p-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for _ in range(M)]
questions = [list(map(int, input().split())) for _ in range(Q)]
for q in questions:
    count = 0
    for train in trains:
        if q[0] <= train[0] and q[1] >= train[1]:
            count += 1
    print(count)

Fixed submission:
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())

sum_table = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l, r = map(int, input().split())
    sum_table[l][r] += 1

for i in range(1, N+1):
    for j in range(1, N+1):
        sum_table[i][j] += sum_table[i-1][j] + sum_table[i][j-1] - sum_table[i-1][j-1]

for _ in range(Q):
    p, q = map(int, input().split())
    print(sum_table[q][q] - sum_table[q][p-1] - sum_table[p-1][q] + sum_table[p-1][p-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
treat = list(map(int, input().split()))

print(len([(n, m) for n in range(N) \
        for m in range(n, N) if sum(treat[n:m+1]) % M == 0]))


Fixed submission:
from collections import Counter
N, M = map(int, input().split())
A = list(map(lambda x:int(x)%M, input().split()))
B = A[:]
for i in range(N-1):
    B[i+1] += B[i]
    B[i+1] %= M
c = Counter(B)


ans = 0
for k, v in c.items():
    if k == 0:
        ans += v
    if v >= 2:
        ans += v*(v-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
treat = list(map(int, input().split()))
count = 0
for n in range(N):
    for m in range(n, N):
        if sum(treat[n:m+1]) % M == 0:
            count += 1


print(count)

Fixed submission:
from collections import Counter
N, M = map(int, input().split())
A = list(map(lambda x:int(x)%M, input().split()))
B = A[:]
for i in range(N-1):
    B[i+1] += B[i]
    B[i+1] %= M
c = Counter(B)


ans = 0
for k, v in c.items():
    if k == 0:
        ans += v
    if v >= 2:
        ans += v*(v-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
S = list(input())
m = []
n = []
for i in range(N):
    if S[i] == 'E':
        S[i] = 1
    else:
        S[i] = 0
for i in range(1, N):
    ls = sum(S[:i-1])
    rs = sum(S[i+1:])
    n.append(i-1-ls+rs)
print(min(n))


Fixed submission:
import numpy as np
N = int(input())
S = np.array(list(input()))
n = []
for i in range(N):
    if S[i] == 'E':
        S[i] = 1
    else:
        S[i] = 0
S = np.array(S, dtype=int)
S = np.cumsum(S)
last = S[N-1]
n.append(last-S[0])
for i in range(1, N):
    ls = i - S[i-1]
    rs = last - S[i]
    n.append(ls+rs)
print(min(n))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
S = list(input())
m = []
for i in range(N):
    if S[i] == 'E':
        S[i] = 1
    else:
        S[i] = -1
for i in range(1, N):
    l = S[:i-1].count(-1)
    r = S[i+1:].count(1)
    m.append(l+r)
print(min(m))


Fixed submission:
import numpy as np
N = int(input())
S = np.array(list(input()))
n = []
for i in range(N):
    if S[i] == 'E':
        S[i] = 1
    else:
        S[i] = 0
S = np.array(S, dtype=int)
S = np.cumsum(S)
last = S[N-1]
n.append(last-S[0])
for i in range(1, N):
    ls = i - S[i-1]
    rs = last - S[i]
    n.append(ls+rs)
print(min(n))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N = int(input())
A = list(map(int, input().split()))

def dd_cost(L):
    c = 0
    M = L[:]
    for i in range(len(L)):
        if L[i] < 0:
            L[i] = -1
        elif L[i] > 0:
            L[i] = 1
        else:
            L[i] = 0
    L = np.array(L)
    L = L[1:]-L[:-1]
    for i in range(len(L)):
        if L[i] < 0 or L[i] > 0:
            c += abs(M[i]) * 2
    c += abs(M[-1]) * 2
    print(c)

for i in range(len(A)):
    dd_cost(A[:i]+A[i+1:])


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
A.append(0)
a = 0
cost = 0
for i in A:
    b = i
    cost += abs(a-b)
    a = b
cost += abs(A[-1])

ori = cost
for i in range(1, len(A)-1):
    cost += abs(A[i-1]-A[i+1])
    cost -= abs(A[i-1]-A[i])+abs(A[i+1]-A[i])
    print(cost)
    cost  = ori

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

def dd_cost(L):
    c = 0
    M = L[:]
    for i in range(len(L)):
        if L[i] < 0:
            L[i] = -1
        elif L[i] > 0:
            L[i] = 1
        else:
            L[i] = 0
    L = np.array(L)
    L = L[1:]-L[:-1]
    for i in range(len(L)):
        if L[i] < 0 or L[i] > 0:
            c += abs(M[i]) * 2
    c += abs(M[-1]) * 2
    print(c)

for i in range(len(A)):
    dd_cost(A[:i]+A[i+1:])


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
A.append(0)
a = 0
cost = 0
for i in A:
    b = i
    cost += abs(a-b)
    a = b
cost += abs(A[-1])

ori = cost
for i in range(1, len(A)-1):
    cost += abs(A[i-1]-A[i+1])
    cost -= abs(A[i-1]-A[i])+abs(A[i+1]-A[i])
    print(cost)
    cost  = ori

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

def d_cost(L):
    ori = L[0]
    cost = 0
    for i in range(1, len(L)):
        if ori < 0 and L[i] > 0:
            cost += abs(ori) * 2
        elif ori > 0 and L[i] < 0:
            cost += abs(ori) * 2
        elif L[i] == 0:
            cost += abs(ori) * 2
        else:
            pass
        ori = L[i]
    cost += abs(L[-1]) * 2
    print(cost)


for i in range(len(A)):
    d_cost(A[:i]+A[i+1:])


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
A.append(0)
a = 0
cost = 0
for i in A:
    b = i
    cost += abs(a-b)
    a = b
cost += abs(A[-1])

ori = cost
for i in range(1, len(A)-1):
    cost += abs(A[i-1]-A[i+1])
    cost -= abs(A[i-1]-A[i])+abs(A[i+1]-A[i])
    print(cost)
    cost  = ori
Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())

p = {}
for i in range(H):
    for j in range(W):
        p[A[i][j]-1] = (i, j)

dp = [[float('inf')]*(H*W) for _ in range(H*W)]
for i in range(H*W):
    dp[i][i] = 0
    for j in range(i+D, H*W, D):
        dp[i][j] = dp[i][j-D] + abs(p[j][0]-p[j-D][0]) + abs(p[j][1] - p[j-D][1]) 

for _ in range(Q):
    L, R = map(lambda x:int(x)-1, input().split())
    print(dp[L][R])

Fixed submission:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())

p = {}
for i in range(H):
    for j in range(W):
        p[A[i][j]-1] = (i, j)

d = [0]*(H*W)
for i in range(D, H*W):
    d[i] = d[i-D] + abs(p[i][0]-p[i-D][0]) + abs(p[i][1]-p[i-D][1])

for _ in range(Q):
    L, R = map(lambda x:int(x)-1, input().split())
    print(d[R]-d[L])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())

p = {}
for i in range(H):
    for j in range(W):
        p[A[i][j]] = (i, j)

d = [[float('inf')]*(H*W) for _ in range(H*W)]

for i in range(1, H*W+1):
    for j in range(1, H*W+1):
        dist = abs(p[i][0]-p[j][0]) + abs(p[i][1]-p[j][1])
        d[i-1][j-1] = dist
        d[j-1][i-1] = dist


dp = [[float('inf')]*(H*W) for _ in range(H*W)]
for i in range(H*W):
    dp[i][i] = 0
    for j in range(i+D, H*W, D):
        dp[i][j] = dp[i][j-D] + d[j][j-D]

for _ in range(Q):
    L, R = map(lambda x:int(x)-1, input().split())
    print(dp[L][R])

Fixed submission:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())

p = {}
for i in range(H):
    for j in range(W):
        p[A[i][j]-1] = (i, j)

d = [0]*(H*W)
for i in range(D, H*W):
    d[i] = d[i-D] + abs(p[i][0]-p[i-D][0]) + abs(p[i][1]-p[i-D][1])

for _ in range(Q):
    L, R = map(lambda x:int(x)-1, input().split())
    print(d[R]-d[L])
Buggy python submission (verdict: Runtime Error):
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(sy, sx):
    q = deque([[sy, sx]])
    dist = [[float('inf')]*(W) for _ in range(H)]
    dist[sy][sx] = 0

    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and s[ny][nx] == '.' and dist[ny][nx] == float('inf'):
                dist[ny][nx] = dist[y][x] + 1
                q += [[ny, nx]]

    return dist

d = bfs(0, 0)

if d[-1][-1] == float('inf'):
    print(-1)
    exit()

ans = H*W 
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            ans -= 1

ans -= d[-1][-1] + 1
print(ans

Fixed submission:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
cnt = [[float('inf') for _ in range(w)] for _ in range(h)]
cnt[0][0] = 0

def bfs():
    q = deque([(0, 0)])
    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            if 0 <= y+dy < h and 0 <= x+dx < w and s[y+dy][x+dx] != '#' and cnt[y+dy][x+dx] == float('inf'):
                q.append([y+dy, x+dx])
                cnt[y+dy][x+dx] = cnt[y][x] + 1
    
bfs()
if cnt[h-1][w-1] != float('inf'):
    short_path = cnt[h-1][w-1]
    ans = 0
    ans += short_path + 1
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                ans += 1

    ans = h*w - ans 
    print(ans)
else:
    print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
n, y = map(int, input().split())
y /= 1000
ans = (-1, -1, -1)
flag = True
for i in range(int(y/10)+1):
    for j in range(int(y-10*i+1)):
        if 10*i+5*j+(n-i-j) == y and n-i-j>=0:
            ans = (i, j, n-i-j)
            flag = False
            break
    if not flag:
        break
print(*ans)

Fixed submission:
N, Y = map(int, input().split())
l = []
flag = False
for i in range(N+1):
    for j in range(N-i+1):
        if 10000 * i + 5000 * j + 1000 * (N-i-j) == Y:
            l = [i, j, N-i-j]
            flag = True
        if flag:
            break
if flag:
    print(*l)
else:
    print(-1, -1, -1)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
B = list(set(A[:]))
count = 0

for i in B:
    j = A.count(i)
    if j > i:
        count += j-i
    elif j < i:
        count += j
print(count)


Fixed submission:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
B = list(set(A[:]))
count = 0

B = Counter(A).most_common()
for k, v in B:

    if k < v:
        count += v-k
    elif k > v:
        count += v
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
B = list(set(A[:]))
dict = defaultdict(int)
for i in range(len(B)):
    dict[B[i]] = A.count(B[i])
count = 0
for k, v in dict.items():
    if k > v:
        count += v
    elif k < v:
        count += v-k
print(count)


Fixed submission:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
B = list(set(A[:]))
count = 0

B = Counter(A).most_common()
for k, v in B:

    if k < v:
        count += v-k
    elif k > v:
        count += v
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from collections import defaultdict
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = Counter(A).most_common()
dict = []
for l in B:
    dict.append([l[0], l[1]])
dict.sort(key=lambda x:x[1])
count = 0
l = len(B)
if l <= K:
    print(0)
else:
    while l != K:
        count += dict[0][1]
        del dict[0]
        dict.sort(key=lambda x:x[1])
        l = len(dict)
        if l == K:
            break
    print(count)


Fixed submission:
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))

ca = Counter(A)
ca = sorted(ca.items(), key=lambda x:x[1], reverse=True)

ans = 0
for i in range(min(K, len(ca))):
    ans += ca[i][1]

print(N-ans)
Buggy python submission (verdict: Runtime Error):
N, C = map(int, input().split())
stc = [list(map(lambda x:2*int(x), input().split())) for _ in range(N)]

stc = sorted(stc, key=lambda x:(x[2], x[0], x[1]))
l = []
i = N-1
s, t, c = 0, 0, 0
while i >= 0:
    if stc[i][2] == stc[i-1][2] and stc[i][0] == stc[i-1][1]:
        s = stc[i-1][0]
        if t == 0:
            t = stc[i][1]
        c = stc[i][2]
    else:
        if s != 0:
            l += [[s, t, c]]
            s, t, c = 0, 0, 0
        else:
            l += [stc[i]]

    i -= 1
        
imos = [0]*(10**5+1)
for s, t, c in l:
    imos[s-1] += 1
    imos[t] -= 1

for i in range(len(imos)-1):
    imos[i] = imos[i] + imos[i-1]

print(max(imos))





Fixed submission:
N, C = map(int, input().split())
stc = [list(map(lambda x:int(x), input().split())) for _ in range(N)]

stc = sorted(stc, key=lambda x:(x[2], x[0], x[1]))
l = []
i = N-1
s, t, c = 0, 0, 0
while i >= 0:
    if stc[i][2] == stc[i-1][2] and stc[i][0] == stc[i-1][1]:
        s = stc[i-1][0]
        if t == 0:
            t = stc[i][1]
        c = stc[i][2]
    else:
        if s != 0:
            l += [[s, t, c]]
            s, t, c = 0, 0, 0
        else:
            l += [stc[i]]

    i -= 1
        
imos = [0]*(2*10**5+1)
for s, t, c in l:
    imos[s-1] += 1
    imos[t] -= 1

for i in range(len(imos)-1):
    imos[i] = imos[i] + imos[i-1]

print(max(imos))
Buggy python submission (verdict: Runtime Error):

#include <bits/stdc++.h>
using namespace std;

int main() {

  int n, m;
  cin >> n >> m;
  cout << (1900*m + 100 * (n-m)) * pow(2, m);
}

Fixed submission:
n, m = map(int, input().split())
t = 1900*m + 100*(n-m)
p = (2)**m
print(t*p)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]

ans = float('inf')
for i in range(N):
  for j in range(N):
    for k in range(N):
      for l in range(N):
        x1= xy[i][0]
        x2 = xy[j][0]
        y1 = xy[k][1]
        y2 = xy[l][1]
        cnt = 0
        if x1 < x2 and y1 < y2:
          for n in range(N):
            if x1 <= xy[n][0] <= x2 and y1 <= xy[n][1] <= y2:
              cnt += 1

          if cnt >= K:
            ans = min(ans, (x2-x1)*(y2-y1))
print(ans)

Fixed submission:
N, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(N)]

ans = float('inf')
for i in range(N):
  for j in range(N):
    for k in range(N):
      for l in range(N):
        x1= xy[i][0]
        x2 = xy[j][0]
        y1 = xy[k][1]
        y2 = xy[l][1]
        cnt = 0
        if x1 < x2 and y1 < y2:
          for n in range(N):
            if x1 <= xy[n][0] <= x2 and y1 <= xy[n][1] <= y2:
              cnt += 1

          if cnt >= K:
            ans = min(ans, (x2-x1)*(y2-y1))
print(ans)
Buggy python submission (verdict: Runtime Error):

import numpy as np 
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
  u, v = map(lambda x: int(x)-1, input().split())
  g[u] += [v]
  g[v] += [u]

col = [0]*n 
def dfs(u, c):
  col[u] = c 
  for v in g[u]:
    if col[v] == c:
      return False
    if (col[v] == 0 and not dfs(v, -c)):
      return False

  return True


if dfs(0, 1):
  col = np.array(col)
  b = len(col[col==1])
  w = len(col) - b
  print(b*w-m)
else:
  print(n*(n-1)//2-m)

Fixed submission:
from collections import Counter
import sys
sys.setrecursionlimit(1000000)

global color 
global adlist

def make_adlist(N, AB):
  global adlist
  for a, b in AB:
    adlist[a] += [b]
    adlist[b] += [a]

def dfs(v, c):
  color[v] = c
  for u in adlist[v]:
    if color[u] == c:
      return False
    if color[u] == 0 and dfs(u, -c)==False:
      return False
  return True

def main():
  global color 
  global adlist
  N, M = map(int, input().split())
  AB = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
  color = [0 for _ in range(N)]
  adlist = [[] for _ in range(N)]
  make_adlist(N, AB)
  if dfs(0, 1):
    B = color.count(-1)
    W = color.count(1)
    print(B*W-M)
  else:
    print(N*(N-1)//2-M)

if __name__ == "__main__":
  main()