Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from math import sqrt
from scipy.special import comb

n, m = map(int, input().split())
mod = 10 ** 9 + 7


def sieve(x):
    primes = []
    li = list(range(2, x + 1))

    while li[0] <= sqrt(x):
        p = li[0]
        primes.append(p)
        li = [e for e in li if e % p != 0]

    primes += li
    return primes


def prime_fact(x):
    primes = sieve(int(sqrt(x)) + 1)
    d = {}

    for p in primes:
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1

        if cnt:
            d[p] = cnt

    if x != 1:
        d[x] = 1

    return d


pf = prime_fact(m)
ans = 1
for v in pf.values():
    ans *= comb(v + n - 1, v, exact=True)
    ans %= mod

print(ans)


Fixed submission:
from math import sqrt
from scipy.misc import comb

n, m = map(int, input().split())
mod = 10 ** 9 + 7


def sieve(x):
    primes = []
    li = list(range(2, x + 1))

    while li[0] <= sqrt(x):
        p = li[0]
        primes.append(p)
        li = [e for e in li if e % p != 0]

    primes += li
    return primes


def prime_fact(x):
    primes = sieve(int(sqrt(x)) + 1)
    d = {}

    for p in primes:
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1

        if cnt:
            d[p] = cnt

    if x != 1:
        d[x] = 1

    return d


pf = prime_fact(m)
ans = 1
for v in pf.values():
    ans *= comb(v + n - 1, v, exact=True)
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

sq = [[0] * n for _ in range(n)]

for i in range(m):
    l = lr[i][0]
    r = lr[i][1]
    sq[l-1][r-1] += 1

c = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if j == 0:
            c[i][j] = sq[i][j]
        else:
            c[i][j] = sq[i][j] + c[i][j-1]
            
for i in range(q):
    p = pq[i][0]
    q = pq[i][1]
    ans = 0
    for j in range(p, q + 1):
        if p != 1:
            ans += c[j-1][q-1] - c[j-1][p-2]
        else:
            ans += c[j-1][q-1]
    print(ans)



Fixed submission:
n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

sq = [[0] * n for _ in range(n)]

for i in range(m):
    l = lr[i][0]
    r = lr[i][1]
    sq[l-1][r-1] += 1

c = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if j == 0:
            c[i][j] = sq[i][j]
        else:
            c[i][j] = sq[i][j] + c[i][j-1]
            
for i in range(q):
    p = pq[i][0]
    q = pq[i][1]
    ans = 0
    for j in range(p, q + 1):
        if p != 1:
            ans += c[j-1][q-1] - c[j-1][p-2]
        else:
            ans += c[j-1][q-1]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

sq = [[0] * n for _ in range(n)]

for i in range(m):
    l = lr[i][0]
    r = lr[i][1]
    sq[l-1][r-1] += 1

for i in range(q):
    p = pq[i][0]
    q = pq[i][1]
    ans = 0
    for j in range(p, q + 1):
        ans += sum(sq[j-1][:q]) - sum(sq[j-1][:p-1])
    print(ans)



Fixed submission:
n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

sq = [[0] * n for _ in range(n)]

for i in range(m):
    l = lr[i][0]
    r = lr[i][1]
    sq[l-1][r-1] += 1

c = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if j == 0:
            c[i][j] = sq[i][j]
        else:
            c[i][j] = sq[i][j] + c[i][j-1]
            
for i in range(q):
    p = pq[i][0]
    q = pq[i][1]
    ans = 0
    for j in range(p, q + 1):
        if p != 1:
            ans += c[j-1][q-1] - c[j-1][p-2]
        else:
            ans += c[j-1][q-1]
    print(ans)
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())

def f(x):
    if x == 0:
        return x
    return x + f(x - 1)

diff = b - a
east = f(diff)
print(east - b)


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

import sys

sys.setrecursionlimit(2000)

def f(x):
    if x == 0:
        return x
    return x + f(x - 1)

diff = b - a
east = f(diff)
print(east - b)
Buggy python submission (verdict: Time Limit Exceeded):
N, C = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

mod = [[], [], []]

for i in range(N):
    for j in range(N):
        mod[(i+j)%3].append(c[i][j])

ans = float("inf")
for c_i in range(C):
    for c_j in range(C):
        if c_j == c_i:
            continue
        for c_k in range(C):
            if c_k == c_i or c_k == c_j:
                continue
            li = [c_i, c_j, c_k]
            sm = 0
            for i in range(3):
                for clr in mod[i]:
                    sm += d[clr-1][li[i]]

            ans = min(ans, sm)

print(ans)


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

mod = [[], [], []]

for i in range(N):
    for j in range(N):
        mod[(i+j)%3].append(c[i][j])

from collections import Counter

c = []
for i in range(3):
    c.append(Counter(mod[i]))

ans = float("inf")
for c_i in range(C):
    for c_j in range(C):
        if c_j == c_i:
            continue
        for c_k in range(C):
            if c_k == c_i or c_k == c_j:
                continue
            li = [c_i, c_j, c_k]
            sm = 0
            for i in range(3):
                counter = c[i]
                for k, v in counter.items():
                    sm += d[k-1][li[i]] * v

            ans = min(ans, sm)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, C = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

ans = float("inf")
for c_i in range(C):
    for c_j in range(C):
        if c_i == c_j:
            continue
        for c_k in range(C):
            if c_i == c_k or c_j == c_k:
                continue
            sm = 0
            for i in range(N):
                for j in range(N):
                    mod = (i + j + 2) % 3
                    clr = c[i][j]
                    if mod == 2:
                        sm += d[clr-1][c_i]
                    elif mod == 0:
                        sm += d[clr-1][c_j]
                    else:
                        sm += d[clr-1][c_k]
            ans = min(ans, sm)

print(ans)


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

mod = [[], [], []]

for i in range(N):
    for j in range(N):
        mod[(i+j)%3].append(c[i][j])

from collections import Counter

c = []
for i in range(3):
    c.append(Counter(mod[i]))

ans = float("inf")
for c_i in range(C):
    for c_j in range(C):
        if c_j == c_i:
            continue
        for c_k in range(C):
            if c_k == c_i or c_k == c_j:
                continue
            li = [c_i, c_j, c_k]
            sm = 0
            for i in range(3):
                counter = c[i]
                for k, v in counter.items():
                    sm += d[k-1][li[i]] * v

            ans = min(ans, sm)

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

r = -1
s = 0

ans = 0
for l in range(n):
    while r < n and not (s & a[r+1]):
        s ^= a[r+1]
        r += 1
    ans += r - l + 1
    s ^= a[l]

print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

r = 0
s = 0

ans = 0
for l in range(n):
    while r < n and not (s & a[r]):
        s ^= a[r]
        r += 1
    ans += r - l
    s ^= a[l]

print(ans)

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

import numpy as np

bit_cnt = np.zeros(20, dtype=np.int8)

def get_bit(x):
    bit = np.zeros(20, dtype=np.int8)
    idx = 0
    while x:
        bit[idx] = x % 2
        x //= 2
        idx += 1

    return bit

def sum_patterns(x):
    return x * (x + 1) // 2

l = 0
r = 1
cnt = 0
bit_cnt += get_bit(a[0])
while r != n:
    expand = bit_cnt + get_bit(a[r])
    if all(expand < 2):
        bit_cnt = expand
        r += 1
    else:
        bit_cnt -= get_bit(a[l])
        cnt += r - l
        l += 1

cnt += sum_patterns(r - l)
print(cnt)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

r = 0
s = 0

ans = 0
for l in range(n):
    while r < n and not (s & a[r]):
        s ^= a[r]
        r += 1
    ans += r - l
    s ^= a[l]

print(ans)

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

x = [0, a[0]]
s = [0, a[0]]
for i in range(1, n):
    x.append(x[-1] ^ a[i])
    s.append(s[-1] + a[i])

cnt = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        xor = x[j] ^ x[i-1]
        sm = s[j] - s[i-1]
        if xor == sm:
            cnt += 1
        else:
            break

print(cnt)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

r = 0
s = 0

ans = 0
for l in range(n):
    while r < n and not (s & a[r]):
        s ^= a[r]
        r += 1
    ans += r - l
    s ^= a[l]

print(ans)

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

x = [0, a[0]]
s = [0, a[0]]
for i in range(1, n):
    x.append(x[-1] ^ a[i])
    s.append(s[-1] + a[i])

cnt = 0
for i in range(1, n + 1):
    for j in range(i, n + 1):
        xor = x[j] ^ x[i-1]
        sm = s[j] - s[i-1]
        if xor == sm:
            cnt += 1

print(cnt)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

r = 0
s = 0

ans = 0
for l in range(n):
    while r < n and not (s & a[r]):
        s ^= a[r]
        r += 1
    ans += r - l
    s ^= a[l]

print(ans)
Buggy python submission (verdict: Runtime Error):
n, k, q = map(int, input().split())
a = list(map(int, input().split()))

ans = 10 ** 10
for i, y in enumerate(a):
    li = []
    l = 0
    cnd = []
    for j, x in enumerate(a + [-1]):
        if i == j:
            continue
        if x < y:
            if l - k + 1 >= 0:
                li.sort()
                cnd += li[:l-k+1]
            li = []
            l = 0
        else:
            li.append(x)
            l += 1

    if len(cnd) >= q - 1:
        cnd.sort()
        sub = cnd[q-2] - y
        ans = min(ans, sub)

print(ans)


Fixed submission:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))

if q == 1:
    print(0)
    exit()

ans = 10 ** 10
for i, y in enumerate(a):
    li = []
    l = 0
    cnd = []
    for j, x in enumerate(a + [-1]):
        if i == j:
            continue
        if x < y:
            if l - k + 1 >= 0:
                li.sort()
                cnd += li[:l-k+1]
            li = []
            l = 0
        else:
            li.append(x)
            l += 1

    if len(cnd) >= q - 1:
        cnd.sort()
        sub = cnd[q-2] - y
        ans = min(ans, sub)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = [list(ord(e) - ord("a") for e in input()) for _ in range(n)]

ans = 0
for b in range(n):
    t = [[-1] * n for _ in range(n)]
    for hi in range(n):
        for wi in range(n):
            nh = hi
            nw = (wi + b) % n
            t[nh][nw] = s[hi][wi]

    bl = True
    for i in range(n):
        for j in range(n):
            if t[i][j] != t[j][i]:
                bl = False

    ans += bl

ans *= n
print(ans)


Fixed submission:
n = int(input())
s = [list(ord(e) - ord("a") for e in input()) for _ in range(n)]

ans = 0
for b in range(n):
    t = [[-1] * n for _ in range(n)]
    for hi in range(n):
        for wi in range(n):
            nh = hi
            nw = (wi + b) % n
            t[nh][nw] = s[hi][wi]

    bl = True
    for i in range(n):
        for j in range(n):
            if t[i][j] != t[j][i]:
                bl = False

    ans += bl

ans *= n
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m, x = map(int, input().split())
a = list(map(int, input().split()))

li = [0] * (n - 1)
for a_ele in a:
    li[a_ele] = 1

print(min(sum(li[:x]), sum(li[x+1:])))


Fixed submission:
n, m, x = map(int, input().split())
a = list(map(int, input().split()))

l = 0
r = 0
for a_ele in a:
    if a_ele < x:
        l += 1
    else:
        r += 1

print(min(l, r))
Buggy python submission (verdict: Runtime Error):
a, b, c, d = map(int, input().split())

print(min(a, b) + min(c, d))


Fixed submission:
a = int(input())
b = int(input())
c = int(input())
d = int(input())

print(min(a, b) + min(c, d))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())), dtype=np.int32)
b = np.array(list(map(int, input().split())), dtype=np.int32)

ans = 0
mod = 1
for k in range(30):
    mod *= 2
    t = mod // 2
    cnt = 0
    bb = np.sort(b % mod)
    for e in a:
        e %= mod
        for i in range(2):
            l = (2 * i + 1) * t - e
            r = (2 * i + 2) * t - e
            il = np.searchsorted(bb, l)
            ir = np.searchsorted(bb, r)
            cnt += ir - il

    if cnt % 2:
        ans += t

print(ans)


Fixed submission:
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())), dtype=np.int32)
b = np.array(list(map(int, input().split())), dtype=np.int32)

ans = 0
mod = 1
for k in range(30):
    mod *= 2
    t = mod // 2
    cnt = 0
    bb = np.sort(b % mod)
    aa = a % mod
    l1, r1, l2, r2 = (np.searchsorted(bb, v - aa).sum() for v in (t, 2*t, 3*t, 4*t))
    cnt += r1 - l1
    cnt += r2 - l2

    if cnt % 2:
        ans += t

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = list(map(int, input().split()))

print("Four" if "Y" in s else "Three")


Fixed submission:
n = int(input())
s = list(input().split())

print("Four" if "Y" in s else "Three")
Buggy python submission (verdict: Runtime Error):
def main():
    n = input()

    l = len(n)

    nines = "9" * (l - 1)
    num = int(nines)

    for i in range(1, 10):
        tmp = str(i) + nines
        if int(tmp) <= int(n):
            num = tmp

    ans = sum(map(int, num))
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    n = input()

    l = len(n)

    nines = "0" + "9" * (l - 1)
    nines = int(nines)

    num = nines
    for i in range(1, 10):
        tmp = i * 10 ** (l - 1) + nines
        if tmp <= int(n):
            num = tmp

    ans = sum(map(int, str(num)))
    print(ans)


if __name__ == "__main__":
    main()

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

    l = len(n)
    diff = ""
    for i, e in enumerate(n):
        if i == 0:
            c = 0
        elif i == l - 1:
            c = int(e) + 1
        else:
            c = int(e)

        c = str(c)
        diff += c

    num = int(n) - int(diff)
    num = str(num)
    ans = sum(map(int, num))
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
def main():
    n = input()

    l = len(n)

    nines = "0" + "9" * (l - 1)
    nines = int(nines)

    num = nines
    for i in range(1, 10):
        tmp = i * 10 ** (l - 1) + nines
        if tmp <= int(n):
            num = tmp

    ans = sum(map(int, str(num)))
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

a.sort(reversed=True)
score = [0, 0]
for i in range(n):
    score[i%2] += a[i]

print(score[0] - score[1])


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
score = [0, 0]
for i in range(n):
    score[i%2] += a[i]

print(score[0] - score[1])

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

a.sort(reversed=True)
score = [0, 0]
for i in range(n):
    score[i&2] += a[i]

print(score[0] - score[1])


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
score = [0, 0]
for i in range(n):
    score[i%2] += a[i]

print(score[0] - score[1])
Buggy python submission (verdict: Runtime Error):
c = [list(map(int, input().split())) for _ in range(3)]

a = [0] * 3
b = [0] * 3
ans = "Yes"
a[0] = 0
b[0] = c[0][0] - a1
b[1] = c[0][1] - a1
b[2] = c[0][2] - a1
a[1] = c[1][0] - b[0]
a[2] = c[2][0] - b[0]
for i in range(3):
    for j in range(3):
        if a[i] + b[j] != c[i][j]:
            ans = "No"

print(ans)


Fixed submission:
c = [list(map(int, input().split())) for _ in range(3)]

a = [0] * 3
b = [0] * 3
ans = "Yes"
for a1 in range(101):
    a[0] = a1
    b[0] = c[0][0] - a1
    b[1] = c[0][1] - a1
    b[2] = c[0][2] - a1
    a[1] = c[1][0] - b[0]
    a[2] = c[2][0] - b[0]
    for i in range(3):
        for j in range(3):
            if a[i] + b[j] != c[i][j]:
                ans = "No"

print(ans)
Buggy python submission (verdict: Runtime Error):
n, a, b = map(int, input().split())

ans = 0
for num in range(1, n + 1):
    s = str(num)
    sm = 0
    for let in s:
        sm += int(let)
    if a <= sm <= b:
        ans += num

print(cnt)


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

ans = 0
for num in range(1, n + 1):
    s = str(num)
    sm = 0
    for let in s:
        sm += int(let)
    if a <= sm <= b:
        ans += num

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))

from collections import Counter, OrderedDict

c = Counter(a)
d = OrderedDict(sorted(c.items(), key=lambda x: x[1]))

if len(d) <= k:
    print(0)

else:
    ans = 0
    while len(d) > k:
        item = list(d.items())[0]
        ans += item[1]
        del d[item[0]]
    print(ans)


Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))

from collections import Counter

c = Counter(a)
d = c.most_common()

if len(d) <= k:
    print(0)

else:
    ans = 0
    while len(d) > k:
        item = d.pop()
        ans += item[1]
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

from itertools import accumulate

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

clock = [0] + list(accumulate(T))
t_sum = sum(T)
mn_f = 0
ans = 0
for t in range(2 * t_sum):
    t /= 2
    mn = min(t, t_sum - t)
    for i in range(1, len(clock)):
        v = V[i-1]
        if t < clock[i-1]:
            v_max = v + clock[i-1] - t
        elif clock[i-1] <= t <= clock[i]:
            v_max = v
        else:
            v_max = v + t - clock[i]
        mn = min(mn, v_max)
    ans += (mn_f + mn) * 0.25
    mn_f = mn

ans += mn_f * 0.25

print(ans)


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

from itertools import accumulate

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

clock = [0] + list(accumulate(T))
t_sum = sum(T)
mn_f = 0
ans = 0
for t in range(2 * t_sum):
    t /= 2
    mn = min(t, t_sum - t)
    for i in range(1, len(clock)):
        v = V[i-1]
        if t < clock[i-1]:
            v_max = v + clock[i-1] - t
        elif clock[i-1] <= t <= clock[i]:
            v_max = v
        else:
            v_max = v + t - clock[i]
        mn = min(mn, v_max)
    ans += (mn_f + mn) * 0.25
    mn_f = mn

ans += mn_f * 0.25

print(ans)

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

from itertools import accumulate

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

clock = [0] + list(accumulate(T))
t_sum = sum(T)
v_li = []
for t in range(2 * t_sum):
    t /= 2
    mn = min(t, t_sum - t)
    for i in range(1, len(clock)):
        if t < clock[i-1]:
            v = V[i-1] + clock[i-1] - t
        elif clock[i-1] <= t <= clock[i]:
            v = V[i-1]
        else:
            v = V[i-1] + t - clock[i]
        mn = min(mn, v)
    v_li.append(mn)

v_li.append(0)

ans = 0
for i in range(1, len(v_li)):
    ans += (v_li[i-1] + v_li[i]) * 0.5 * 0.5

print(ans)


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

from itertools import accumulate

N = int(input())
T = list(map(int, input().split()))
V = list(map(int, input().split()))

clock = [0] + list(accumulate(T))
t_sum = sum(T)
mn_f = 0
ans = 0
for t in range(2 * t_sum):
    t /= 2
    mn = min(t, t_sum - t)
    for i in range(1, len(clock)):
        v = V[i-1]
        if t < clock[i-1]:
            v_max = v + clock[i-1] - t
        elif clock[i-1] <= t <= clock[i]:
            v_max = v
        else:
            v_max = v + t - clock[i]
        mn = min(mn, v_max)
    ans += (mn_f + mn) * 0.25
    mn_f = mn

ans += mn_f * 0.25

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

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

g = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)


class Tree:
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += 1
                self.dfs(v)
                self.depth -= 1
            elif (self.depths[u] - self.depths[v]) % 2 == 0:
                return False

        self.colors[u] = self.BLACK

        return True


tree = Tree(g)
if tree.dfs(0):
    black = len([x for x in tree.depths if x % 2])
    white = len([x for x in tree.depths if x % 2 == 0])
    ans = black * white - m

else:
    raise Exception
    ans = n * (n - 1) // 2 - m

print(ans)


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

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

g = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

import sys

sys.setrecursionlimit(10 ** 6)


class Tree:
    WHITE = 0
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u):
        if self.colors[u] == self.BLACK:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v, w in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.depth += w
                self.dfs(v)
                self.depth -= w

        self.colors[u] = self.BLACK

    def bipartite_graph(self, u, c):
        self.colors[u] = c
        for v in self.adj[u]:
            if self.colors[v] == c:
                return False
            if self.colors[v] == self.WHITE and not self.bipartite_graph(v, -c):
                return False

        return True


tree = Tree(g)
if tree.bipartite_graph(0, tree.GRAY):
    black = tree.colors.count(tree.GRAY)
    white = tree.colors.count(tree.BLACK)
    ans = black * white - m

else:
    ans = n * (n - 1) // 2 - m

print(ans)