n,m = list(map(int,input().split()))

g = [list() for _ in range(n+1)]

for _ in range(m):

  a,b = list(map(int,input().split()))

  g[a].append(b)

  g[b].append(a)

bw = [-1]*(n+1)

bw[1] = 0

q = [1]

f = 0

while q:

  v = q.pop()

  for x in g[v]:

    if bw[x] >= 0:

      if bw[x] == bw[v]:

        f = 1

        break

      continue

    else:

      bw[x] = 1-bw[v]

      q.append(x)

if f:

  print((n*(n-1)//2 - m))

else:

  b = sum(bw)+1

  w = n - b

  print((b*w-m))
import sys

from collections import deque



readline = sys.stdin.buffer.readline

ni = lambda: int(readline().rstrip())

nm = lambda: list(map(int, readline().split()))

nl = lambda: list(map(int, readline().split()))





def solve():

    mod = 10**9 + 7

    n, m = nm()

    G = [list() for _ in range(n)]

    for _ in range(m):

        u, v = nm()

        u -= 1; v -= 1

        G[u].append(v)

        G[v].append(u)

    col = [-1]*n

    q = deque([0])

    col[0] = 1

    while q:

        v = q.popleft()

        for x in G[v]:

            if col[x] < 0:

                col[x] = col[v] ^ 1

                q.append(x)

            elif col[x] == col[v]:

                print((n * (n-1) // 2 - m))

                return

    bl = sum(col)

    wh = n - bl

    print((bl * wh - m))

    return



solve()



# T = ni()

# for _ in range(T):

#     solve()

n, m = list(map(int, input().split()))
g = [list() for _ in range(n + 1)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    g[a].append(b)
    g[b].append(a)
bw = [-1] * (n + 1)
bw[1] = 0
q = [1]
f = 0
while q:
    v = q.pop()
    for x in g[v]:
        if bw[x] >= 0:
            if bw[x] == bw[v]:
                f = 1
                break
            continue
        else:
            bw[x] = 1 - bw[v]
            q.append(x)
if f:
    print((n * (n - 1) // 2 - m))
else:
    b = sum(bw) + 1
    w = n - b
    print((b * w - m))

import sys
from collections import deque

readline = sys.stdin.buffer.readline
ni = lambda: int(readline().rstrip())
nm = lambda: list(map(int, readline().split()))
nl = lambda: list(map(int, readline().split()))


def solve():
    mod = 10**9 + 7
    n, m = nm()
    G = [list() for _ in range(n)]
    for _ in range(m):
        u, v = nm()
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)
    col = [-1] * n
    q = deque([0])
    col[0] = 1
    while q:
        v = q.popleft()
        for x in G[v]:
            if col[x] < 0:
                col[x] = col[v] ^ 1
                q.append(x)
            elif col[x] == col[v]:
                print((n * (n - 1) // 2 - m))
                return
    bl = sum(col)
    wh = n - bl
    print((bl * wh - m))
    return


solve()
# T = ni()
# for _ in range(T):
#     solve()

-n, m = list(map(int, input().split())) -g = [list() for _ in range(n + 1)] -for _ in range(m): -    a, b = list(map(int, input().split())) -    g[a].append(b) -    g[b].append(a) -bw = [-1] * (n + 1) -bw[1] = 0 -q = [1] -f = 0 -while q: -    v = q.pop() -    for x in g[v]: -        if bw[x] >= 0: -            if bw[x] == bw[v]: -                f = 1 -                break -            continue -        else: -            bw[x] = 1 - bw[v] -            q.append(x) -if f: -    print((n * (n - 1) // 2 - m)) -else: -    b = sum(bw) + 1 -    w = n - b -    print((b * w - m)) +import sys +from collections import deque + +readline = sys.stdin.buffer.readline +ni = lambda: int(readline().rstrip()) +nm = lambda: list(map(int, readline().split())) +nl = lambda: list(map(int, readline().split())) + + +def solve(): +    mod = 10**9 + 7 +    n, m = nm() +    G = [list() for _ in range(n)] +    for _ in range(m): +        u, v = nm() +        u -= 1 +        v -= 1 +        G[u].append(v) +        G[v].append(u) +    col = [-1] * n +    q = deque([0]) +    col[0] = 1 +    while q: +        v = q.popleft() +        for x in G[v]: +            if col[x] < 0: +                col[x] = col[v] ^ 1 +                q.append(x) +            elif col[x] == col[v]: +                print((n * (n - 1) // 2 - m)) +                return +    bl = sum(col) +    wh = n - bl +    print((bl * wh - m)) +    return + + +solve() +# T = ni() +# for _ in range(T): +#     solve()