import sys

sys.setrecursionlimit(10 ** 7)



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

AB = [list(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N)]



for a, b in AB:

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

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



# 二部グラフかどうかの判定

color = [None] * N

color[0] = 0

q = [0]

while q:

    x = q.pop()

    for y in graph[x]:

        if color[y] is None:

            color[y] = 1 - color[x]

            q.append(y)



# 二部グラフかどうか

is_bg = all(color[a-1] != color[b-1] for a, b in AB)



if is_bg:

    # 完全二部グラフにする

    x = sum(color)

    y = N - x

    answer = x*y - M

else:

    # 完全グラフにする(奇数長のパスがある場合は必ず2ずつ減らしていけば長さが3になる)

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



print(answer)
# C - 3 Steps

import sys

sys.setrecursionlimit(10 ** 7)



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

AB = [list(map(int, input().split())) for _ in range(M)]

graph = [[] for _ in range(N)]



for a, b in AB:

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

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



# 二部グラフかどうかの判定

colors = [None] * N

colors[0] = 0

q = [0]

while q:

    x = q.pop()

    for y in graph[x]:

        if colors[y] is None:

            colors[y] = 1 - colors[x]

            q.append(y)



# 二部グラフかどうか

is_bg = all(colors[a-1] != colors[b-1] for a, b in AB)



if is_bg:

    # 完全二部グラフにする

    x = sum(colors)

    y = N - x

    answer = x*y - M

else:

    # 完全グラフにする(奇数長のパスがある場合は必ず2ずつ減らしていけば長さが3になる)

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



print(answer)
import sys

sys.setrecursionlimit(10**7)
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
graph = [[] for _ in range(N)]
for a, b in AB:
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
# 二部グラフかどうかの判定
color = [None] * N
color[0] = 0
q = [0]
while q:
    x = q.pop()
    for y in graph[x]:
        if color[y] is None:
            color[y] = 1 - color[x]
            q.append(y)
# 二部グラフかどうか
is_bg = all(color[a - 1] != color[b - 1] for a, b in AB)
if is_bg:
    # 完全二部グラフにする
    x = sum(color)
    y = N - x
    answer = x * y - M
else:
    # 完全グラフにする(奇数長のパスがある場合は必ず2ずつ減らしていけば長さが3になる)
    answer = N * (N - 1) // 2 - M
print(answer)

# C - 3 Steps
import sys

sys.setrecursionlimit(10**7)
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
graph = [[] for _ in range(N)]
for a, b in AB:
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
# 二部グラフかどうかの判定
colors = [None] * N
colors[0] = 0
q = [0]
while q:
    x = q.pop()
    for y in graph[x]:
        if colors[y] is None:
            colors[y] = 1 - colors[x]
            q.append(y)
# 二部グラフかどうか
is_bg = all(colors[a - 1] != colors[b - 1] for a, b in AB)
if is_bg:
    # 完全二部グラフにする
    x = sum(colors)
    y = N - x
    answer = x * y - M
else:
    # 完全グラフにする(奇数長のパスがある場合は必ず2ずつ減らしていけば長さが3になる)
    answer = N * (N - 1) // 2 - M
print(answer)

+# C - 3 Steps -color = [None] * N -color[0] = 0 +colors = [None] * N +colors[0] = 0 -        if color[y] is None: -            color[y] = 1 - color[x] +        if colors[y] is None: +            colors[y] = 1 - colors[x] -is_bg = all(color[a - 1] != color[b - 1] for a, b in AB) +is_bg = all(colors[a - 1] != colors[b - 1] for a, b in AB) -    x = sum(color) +    x = sum(colors)