二部グラフの判定

問題：CODE FESTIVAL 2017 qual B 3steps
https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c

from collections import defaultdict, deque, Counter
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))


def bipartite_or_not(G, s=0):
    n = len(G)
    global color
    color = [0] * n
    color[s] = 1
    dq = deque([s])
    while dq:
        u = dq.popleft()
        for v in G[u]:
            if color[v] == 0:
                color[v] = -color[u]
                dq += [v]
            else:
                if color[u] == color[v]:
                    return False
    return True


n, m = LI()
G = [[] for _ in range(n)]
for a, b in LIR(m):
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


if bipartite_or_not(G):
    print(color.count(1) * color.count(-1) - m)
else:
    print(n * (n - 1) // 2 - m)