import sys

sys.setrecursionlimit(10 ** 7)



N, M = list(map(int, input().split()))

AB = [[int(x) for x in input().split()] for _ in range(M)]

G = [[] for _ in range(N+1)]

for a,b in AB:  

  G[a].append(b)

  G[b].append(a)

color = [None]*(N+1)  

# 二部グラフ判定

def dfs(v, c):

  color[v] = c

  for e in G[v]:

    if color[e] == None:

      color[e] = 1 - color[v]      

      dfs(e, c^1) # c^1 == xor (0+1==True)

dfs(1, 0)      

bl = all(color[a] != color[b] for a, b in AB)      

# ans

if bl:

  # 二部グラフ

  x = sum(color[1:])

  y = N-x

  print((x*y-M))

else:

  # 完全グラフ

  print((N*(N-1)//2-M))
import sys

sys.setrecursionlimit(10 ** 7)



N, M = list(map(int, input().split()))

AB = [[int(x) for x in input().split()] for _ in range(M)]

G = [[] for _ in range(N+1)]

for a,b in AB:  

  G[a].append(b)

  G[b].append(a)

color = [None]*(N+1)  

color[1] = 0

q = [1]

# 二部グラフ判定

while q:

  x = q.pop()

  for y in G[x]:

    if color[y] is None:

      color[y] = 1 - color[x]

      q.append(y)

bl = all(color[a] != color[b] for a, b in AB)      

# ans

if bl:

  # 二部グラフ

  x = sum(color[1:])

  y = N-x

  print((x*y-M))

else:

  # 完全グラフ

  print((N*(N-1)//2-M))
import sys

sys.setrecursionlimit(10**7)
N, M = list(map(int, input().split()))
AB = [[int(x) for x in input().split()] for _ in range(M)]
G = [[] for _ in range(N + 1)]
for a, b in AB:
    G[a].append(b)
    G[b].append(a)
color = [None] * (N + 1)
# 二部グラフ判定
def dfs(v, c):
    color[v] = c
    for e in G[v]:
        if color[e] == None:
            color[e] = 1 - color[v]
            dfs(e, c ^ 1)  # c^1 == xor (0+1==True)


dfs(1, 0)
bl = all(color[a] != color[b] for a, b in AB)
# ans
if bl:
    # 二部グラフ
    x = sum(color[1:])
    y = N - x
    print((x * y - M))
else:
    # 完全グラフ
    print((N * (N - 1) // 2 - M))

import sys

sys.setrecursionlimit(10**7)
N, M = list(map(int, input().split()))
AB = [[int(x) for x in input().split()] for _ in range(M)]
G = [[] for _ in range(N + 1)]
for a, b in AB:
    G[a].append(b)
    G[b].append(a)
color = [None] * (N + 1)
color[1] = 0
q = [1]
# 二部グラフ判定
while q:
    x = q.pop()
    for y in G[x]:
        if color[y] is None:
            color[y] = 1 - color[x]
            q.append(y)
bl = all(color[a] != color[b] for a, b in AB)
# ans
if bl:
    # 二部グラフ
    x = sum(color[1:])
    y = N - x
    print((x * y - M))
else:
    # 完全グラフ
    print((N * (N - 1) // 2 - M))

+color[1] = 0 +q = [1] -def dfs(v, c): -    color[v] = c -    for e in G[v]: -        if color[e] == None: -            color[e] = 1 - color[v] -            dfs(e, c ^ 1)  # c^1 == xor (0+1==True) - - -dfs(1, 0) +while q: +    x = q.pop() +    for y in G[x]: +        if color[y] is None: +            color[y] = 1 - color[x] +            q.append(y)