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

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

for i in range(M):

    a,b = [int(x)-1 for x in input().split()]

    e_list[a].append(b)

    e_list[b].append(a)

bin_or_not = True

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

w_or_b = [-1]*N

stack = [0]

w_or_b[0] = 0

while stack:

    x = stack.pop()

    for i in e_list[x]:

        if w_or_b[i] >= 0:

            bin_or_not = w_or_b[x]^w_or_b[i]

        else:

            w_or_b[i] = (w_or_b[x] + 1)%2

            stack.append(i)

        if not bin_or_not:

            break

    if not bin_or_not:

        break

if bin_or_not:

    w =  w_or_b.count(0)

    b = w_or_b.count(1)

    ans = w*b - M

print(ans)
import sys

sys.setrecursionlimit(10**7)

class BinPartite:

    def __init__(self, N, es):

        self.colors = [0 for i in range(N)]

        self.es = es



    def dfs(self, v, color):

        self.colors[v] = color

        for to in self.es[v]:

            if self.colors[to] == color:

                return False

            if self.colors[to] == 0 and not self.dfs(to, -color):

                return False

        return True



    def color_cnt(self, color):

        return self.colors.count(color)



    def is_bipartite(self):

        return self.dfs(0, 1)





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

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

for i in range(M):

    a, b = [int(x)-1 for x in input().split()]

    e_list[a].append(b)

    e_list[b].append(a)



Bp = BinPartite(N, e_list)

if Bp.is_bipartite():

    b = Bp.color_cnt(1)

    w = Bp.color_cnt(-1)

    print((b*w-M))

else:

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

N, M = list(map(int, input().split()))
e_list = [[] for i in range(N)]
for i in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    e_list[a].append(b)
    e_list[b].append(a)
bin_or_not = True
ans = (N - 1) * N // 2 - M
w_or_b = [-1] * N
stack = [0]
w_or_b[0] = 0
while stack:
    x = stack.pop()
    for i in e_list[x]:
        if w_or_b[i] >= 0:
            bin_or_not = w_or_b[x] ^ w_or_b[i]
        else:
            w_or_b[i] = (w_or_b[x] + 1) % 2
            stack.append(i)
        if not bin_or_not:
            break
    if not bin_or_not:
        break
if bin_or_not:
    w = w_or_b.count(0)
    b = w_or_b.count(1)
    ans = w * b - M
print(ans)

import sys

sys.setrecursionlimit(10**7)


class BinPartite:
    def __init__(self, N, es):
        self.colors = [0 for i in range(N)]
        self.es = es

    def dfs(self, v, color):
        self.colors[v] = color
        for to in self.es[v]:
            if self.colors[to] == color:
                return False
            if self.colors[to] == 0 and not self.dfs(to, -color):
                return False
        return True

    def color_cnt(self, color):
        return self.colors.count(color)

    def is_bipartite(self):
        return self.dfs(0, 1)


N, M = list(map(int, input().split()))
e_list = [[] for i in range(N)]
for i in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    e_list[a].append(b)
    e_list[b].append(a)
Bp = BinPartite(N, e_list)
if Bp.is_bipartite():
    b = Bp.color_cnt(1)
    w = Bp.color_cnt(-1)
    print((b * w - M))
else:
    print((N * (N - 1) // 2 - M))

+import sys + +sys.setrecursionlimit(10**7) + + +class BinPartite: +    def __init__(self, N, es): +        self.colors = [0 for i in range(N)] +        self.es = es + +    def dfs(self, v, color): +        self.colors[v] = color +        for to in self.es[v]: +            if self.colors[to] == color: +                return False +            if self.colors[to] == 0 and not self.dfs(to, -color): +                return False +        return True + +    def color_cnt(self, color): +        return self.colors.count(color) + +    def is_bipartite(self): +        return self.dfs(0, 1) + + -bin_or_not = True -ans = (N - 1) * N // 2 - M -w_or_b = [-1] * N -stack = [0] -w_or_b[0] = 0 -while stack: -    x = stack.pop() -    for i in e_list[x]: -        if w_or_b[i] >= 0: -            bin_or_not = w_or_b[x] ^ w_or_b[i] -        else: -            w_or_b[i] = (w_or_b[x] + 1) % 2 -            stack.append(i) -        if not bin_or_not: -            break -    if not bin_or_not: -        break -if bin_or_not: -    w = w_or_b.count(0) -    b = w_or_b.count(1) -    ans = w * b - M -print(ans) +Bp = BinPartite(N, e_list) +if Bp.is_bipartite(): +    b = Bp.color_cnt(1) +    w = Bp.color_cnt(-1) +    print((b * w - M)) +else: +    print((N * (N - 1) // 2 - M))