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

que = [0]

while que:

    x = que.pop()

    for y in graph[x]:

        if colors[y] == None:

            colors[y] = 1 - colors[x]

            que.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:

    # 完全グラフ

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



print(answer)



import sys



stdin = sys.stdin



ri = lambda: int(rs())

rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only

rs = lambda: stdin.readline().rstrip()  # ignores trailing space



N, M = rl()

graph = [[] for _ in range(N+1)] # 0は使わない、直接行ける頂点

for _ in range(M):

    a, b = rl()

    graph[a].append(b)

    graph[b].append(a)



# 二部グラフのチェック、各頂点に0か1の色を塗る、1の頂点に0の色

color = [None] * (N+1) # 0は使わない

color[1] = 0

stack = [1]

bool = True

while stack:

    node = stack.pop()

    for n in graph[node]:

        if color[n] == None:

            color[n] = 1 - color[node]

            stack.append(n)

        elif color[n] == color[node]:

            bool = False

        else:

            continue



if bool:

    # 二部グラフ

    print(((color.count(1) * color.count(0)) - M))

else:

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

#29

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
que = [0]
while que:
    x = que.pop()
    for y in graph[x]:
        if colors[y] == None:
            colors[y] = 1 - colors[x]
            que.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:
    # 完全グラフ
    answer = N * (N - 1) // 2 - M
print(answer)

import sys

stdin = sys.stdin
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignores trailing space
N, M = rl()
graph = [[] for _ in range(N + 1)]  # 0は使わない、直接行ける頂点
for _ in range(M):
    a, b = rl()
    graph[a].append(b)
    graph[b].append(a)
# 二部グラフのチェック、各頂点に0か1の色を塗る、1の頂点に0の色
color = [None] * (N + 1)  # 0は使わない
color[1] = 0
stack = [1]
bool = True
while stack:
    node = stack.pop()
    for n in graph[node]:
        if color[n] == None:
            color[n] = 1 - color[node]
            stack.append(n)
        elif color[n] == color[node]:
            bool = False
        else:
            continue
if bool:
    # 二部グラフ
    print(((color.count(1) * color.count(0)) - M))
else:
    print((N * (N - 1) // 2 - M))
# 29

-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 -que = [0] -while que: -    x = que.pop() -    for y in graph[x]: -        if colors[y] == None: -            colors[y] = 1 - colors[x] -            que.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 +stdin = sys.stdin +ri = lambda: int(rs()) +rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only +rs = lambda: stdin.readline().rstrip()  # ignores trailing space +N, M = rl() +graph = [[] for _ in range(N + 1)]  # 0は使わない、直接行ける頂点 +for _ in range(M): +    a, b = rl() +    graph[a].append(b) +    graph[b].append(a) +# 二部グラフのチェック、各頂点に0か1の色を塗る、1の頂点に0の色 +color = [None] * (N + 1)  # 0は使わない +color[1] = 0 +stack = [1] +bool = True +while stack: +    node = stack.pop() +    for n in graph[node]: +        if color[n] == None: +            color[n] = 1 - color[node] +            stack.append(n) +        elif color[n] == color[node]: +            bool = False +        else: +            continue +if bool: +    # 二部グラフ +    print(((color.count(1) * color.count(0)) - M)) -    # 完全グラフ -    answer = N * (N - 1) // 2 - M -print(answer) +    print((N * (N - 1) // 2 - M)) +# 29