Buggy python submission (verdict: Time Limit Exceeded):
def bipartite():
    color = {v: None for v in V}
    stack = [(V[0], 0)]
    parts = {0: set([]), 1: set([])}
    while stack:
        v, c = stack.pop()
        color[v] = c
        parts[c].add(v)
        for u in E[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    return (parts[0], parts[1])
            
N, M = map(int, input().split())
V = range(1, N+1)
E = {v: [] for v in V}
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
p1, p2 = bipartite()
if p1 is None:
    print(N * (N-1) // 2 - M)
else:
    print(len(p1) * len(p2) - M)

Fixed submission:
def bipartite():
    color = {v: None for v in V}
    stack = [(V[0], 0)]
    parts = {0: [], 1:[]}
    while stack:
        v, c = stack.pop()
        if color[v] is not None: # consistent
            continue
        color[v] = c
        parts[c].append(v)
        for u in E[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    return (parts[0], parts[1])
            
N, M = map(int, input().split())
V = range(1, N+1)
E = {v: [] for v in V}
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
p1, p2 = bipartite()
if p1 is None:
    print(N * (N-1) // 2 - M)
else:
    print(len(p1) * len(p2) - M)

Buggy python submission (verdict: Time Limit Exceeded):
class Graph:
    def __init__(self, V, directed=False):
        self.V = V
        self.directed = directed
        self.adj_list = {i: [] for i in self.V}
        
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        if not self.directed:
            self.adj_list[v].append(u)

def bipartite(graph):
    color = {v: None for v in graph.V}
    stack = [(graph.V[0], 0)]
    while stack:
        v, c = stack.pop()
        color[v] = c
        for u in graph.adj_list[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    parts = {0: [], 1:[]}
    for v in graph.V:
        parts[color[v]].append(v)
    return (parts[0], parts[1])
            
N, M = map(int, input().split())
g = Graph(range(1, N+1))
for _ in range(M):
    a, b = map(int, input().split())
    g.add_edge(a, b)
p1, p2 = bipartite(g)
if p1 is None:
    print(N * (N-1) // 2 - M)
else:
    print(len(p1) * len(p2) - M)

Fixed submission:
def bipartite():
    color = {v: None for v in V}
    stack = [(V[0], 0)]
    parts = {0: [], 1:[]}
    while stack:
        v, c = stack.pop()
        if color[v] is not None: # consistent
            continue
        color[v] = c
        parts[c].append(v)
        for u in E[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    return (parts[0], parts[1])
            
N, M = map(int, input().split())
V = range(1, N+1)
E = {v: [] for v in V}
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
p1, p2 = bipartite()
if p1 is None:
    print(N * (N-1) // 2 - M)
else:
    print(len(p1) * len(p2) - M)