# -*- coding: utf-8 -*-



import sys

from collections import Counter



def input(): return sys.stdin.readline().strip()

def list2d(a, b, c): return [[c] * b for i in range(a)]

def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]

def ceil(x, y=1): return int(-(-x // y))

def INT(): return int(eval(input()))

def MAP(): return list(map(int, input().split()))

def LIST(): return list(map(int, input().split()))

def Yes(): print('Yes')

def No(): print('No')

def YES(): print('YES')

def NO(): print('NO')

sys.setrecursionlimit(10 ** 9)

INF = float('inf')

MOD = 10 ** 9 + 7



N,M=MAP()

nodes=[[] for i in range(N)]

for i in range(M):

    a,b=MAP()

    nodes[a-1].append(b-1)

    nodes[b-1].append(a-1)



visited=[False]*N

team=['']*N



def rec(u):

    if visited[u]:

        return True

    visited[u]=True

    for v in nodes[u]:

        if team[u]==team[v]:

            return False

        if team[u]=='a':

            team[v]='b'

        elif team[u]=='b':

            team[v]='a'

        if not rec(v):

            return False

    return True



# 1からnまでの等差数列の和

def get_sum(n):

    return (1+n)*n//2



team[0]='a'

if rec(0):

    C=Counter(team)

    ans=C['a']*C['b']-M

else:

    ans=get_sum(N-1)-M

print(ans)

# -*- coding: utf-8 -*-



import sys



def input(): return sys.stdin.readline().strip()

def list2d(a, b, c): return [[c] * b for i in range(a)]

def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1): return int(-(-x // y))

def INT(): return int(eval(input()))

def MAP(): return list(map(int, input().split()))

def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes(): print('Yes')

def No(): print('No')

def YES(): print('YES')

def NO(): print('NO')

sys.setrecursionlimit(10 ** 9)

INF = float('inf')

MOD = 10 ** 9 + 7



N, M = MAP()

nodes = tuple([] for i in range(N))

for i in range(M):

    a, b = MAP()

    a -= 1

    b -= 1

    nodes[a].append(b)

    nodes[b].append(a)



# 二部グラフ判定

color = [-1] * N

def rec(u, prev, c):

    if color[u] == -1:

        color[u] = c

    else:

        if color[u] == c:

            return True

        else:

            return False

    for v in nodes[u]:

        if v != prev:

            if not rec(v, u, 1-c):

                return False

    return True



if rec(0, -1, 0):

    a = sum(color)

    b = N - a

    ans = a*b - M

else:

    ans = N*(N-1) // 2 - M

print(ans)

# -*- coding: utf-8 -*-
import sys
from collections import Counter


def input():
    return sys.stdin.readline().strip()


def list2d(a, b, c):
    return [[c] * b for i in range(a)]


def list3d(a, b, c, d):
    return [[[d] * c for j in range(b)] for i in range(a)]


def ceil(x, y=1):
    return int(-(-x // y))


def INT():
    return int(eval(input()))


def MAP():
    return list(map(int, input().split()))


def LIST():
    return list(map(int, input().split()))


def Yes():
    print("Yes")


def No():
    print("No")


def YES():
    print("YES")


def NO():
    print("NO")


sys.setrecursionlimit(10**9)
INF = float("inf")
MOD = 10**9 + 7
N, M = MAP()
nodes = [[] for i in range(N)]
for i in range(M):
    a, b = MAP()
    nodes[a - 1].append(b - 1)
    nodes[b - 1].append(a - 1)
visited = [False] * N
team = [""] * N


def rec(u):
    if visited[u]:
        return True
    visited[u] = True
    for v in nodes[u]:
        if team[u] == team[v]:
            return False
        if team[u] == "a":
            team[v] = "b"
        elif team[u] == "b":
            team[v] = "a"
        if not rec(v):
            return False
    return True


# 1からnまでの等差数列の和
def get_sum(n):
    return (1 + n) * n // 2


team[0] = "a"
if rec(0):
    C = Counter(team)
    ans = C["a"] * C["b"] - M
else:
    ans = get_sum(N - 1) - M
print(ans)

# -*- coding: utf-8 -*-
import sys


def input():
    return sys.stdin.readline().strip()


def list2d(a, b, c):
    return [[c] * b for i in range(a)]


def list3d(a, b, c, d):
    return [[[d] * c for j in range(b)] for i in range(a)]


def list4d(a, b, c, d, e):
    return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]


def ceil(x, y=1):
    return int(-(-x // y))


def INT():
    return int(eval(input()))


def MAP():
    return list(map(int, input().split()))


def LIST(N=None):
    return list(MAP()) if N is None else [INT() for i in range(N)]


def Yes():
    print("Yes")


def No():
    print("No")


def YES():
    print("YES")


def NO():
    print("NO")


sys.setrecursionlimit(10**9)
INF = float("inf")
MOD = 10**9 + 7
N, M = MAP()
nodes = tuple([] for i in range(N))
for i in range(M):
    a, b = MAP()
    a -= 1
    b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
# 二部グラフ判定
color = [-1] * N


def rec(u, prev, c):
    if color[u] == -1:
        color[u] = c
    else:
        if color[u] == c:
            return True
        else:
            return False
    for v in nodes[u]:
        if v != prev:
            if not rec(v, u, 1 - c):
                return False
    return True


if rec(0, -1, 0):
    a = sum(color)
    b = N - a
    ans = a * b - M
else:
    ans = N * (N - 1) // 2 - M
print(ans)

-from collections import Counter +def list4d(a, b, c, d, e): +    return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)] + + -def LIST(): -    return list(map(int, input().split())) +def LIST(N=None): +    return list(MAP()) if N is None else [INT() for i in range(N)] -nodes = [[] for i in range(N)] +nodes = tuple([] for i in range(N)) -    nodes[a - 1].append(b - 1) -    nodes[b - 1].append(a - 1) -visited = [False] * N -team = [""] * N +    a -= 1 +    b -= 1 +    nodes[a].append(b) +    nodes[b].append(a) +# 二部グラフ判定 +color = [-1] * N -def rec(u): -    if visited[u]: -        return True -    visited[u] = True +def rec(u, prev, c): +    if color[u] == -1: +        color[u] = c +    else: +        if color[u] == c: +            return True +        else: +            return False -        if team[u] == team[v]: -            return False -        if team[u] == "a": -            team[v] = "b" -        elif team[u] == "b": -            team[v] = "a" -        if not rec(v): -            return False +        if v != prev: +            if not rec(v, u, 1 - c): +                return False -# 1からnまでの等差数列の和 -def get_sum(n): -    return (1 + n) * n // 2 - - -team[0] = "a" -if rec(0): -    C = Counter(team) -    ans = C["a"] * C["b"] - M +if rec(0, -1, 0): +    a = sum(color) +    b = N - a +    ans = a * b - M -    ans = get_sum(N - 1) - M +    ans = N * (N - 1) // 2 - M