Rng has a connected undirected graph with N vertices. Currently, there are M edges in the graph, and the i-th edge connects Vertices A_i and B_i.  Rng will add new edges to the graph by repeating the following operation:    * Operation: Choose u and v (u \neq v) such that Vertex v can be reached by traversing exactly three edges from Vertex u, and add an edge connecting Vertices u and v. It is not allowed to add an edge if there is already an edge connecting Vertices u and v.  Find the maximum possible number of edges that can be added.
N, M = map(int, input().split())
for _ in range(M):
    A, B = map(int, input().split())
    
print(N*(N-1) // 2 - M)
from collections import deque
N, M = map(int, input().split())
G = dict()
for i in range(N):
    G[i+1] = []
color_list = [0] * N

close = False

for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
    

# color
color_list[0] = 1
for q in G[1]:
    color_list[q-1] = -1

que = deque(G[1])

while len(que) > 0:
    p = que.popleft()
    for q in G[p]:
        if color_list[q-1] == 0:
            color_list[q-1] = - color_list[p-1]
            que.append(q)
        elif color_list[q-1] == color_list[p-1]:
            close = True
            break

if close == True:
    print(N*(N-1) // 2 - M)
else:
    print(color_list.count(1)*color_list.count(-1) - M)