import sys

sys.setrecursionlimit(10**9)



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

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

for i in range(M):

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

    a, b = a-1, b-1

    G[a].append(b)

    G[b].append(a)



# 0は未着色を表す

color = [0] * N





# 二部グラフ判定dfs

def dfs(v, c):

    color[v] = c

    for to in G[v]:

        if color[to] == c:

            return False



        if color[to] == 0 and not dfs(to, -c):

            return False



    return True





print((N * (N - 1) // 2 - M if not dfs(0, 1) else color.count(1) * color.count(-1) - M))

# 忘れないように

import sys

sys.setrecursionlimit(10**9)

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

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

for i in range(M):

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

    a, b = a - 1, b - 1

    G[a].append(b)

    G[b].append(a)





# 0は未着色を表す

color = [0] * N





# 二部グラフ判定dfs

def dfs(v, c):

    color[v] = c

    for to in G[v]:

        if color[to] == c:

            return False



        if color[to] == 0 and not dfs(to, -c):

            return False



    return True





Bipartite = dfs(0, 1)



if Bipartite:

    White = color.count(1)

    Black = color.count(-1)

    print((White * Black - M))



else:

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

import sys

sys.setrecursionlimit(10**9)
N, M = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)
# 0は未着色を表す
color = [0] * N
# 二部グラフ判定dfs
def dfs(v, c):
    color[v] = c
    for to in G[v]:
        if color[to] == c:
            return False
        if color[to] == 0 and not dfs(to, -c):
            return False
    return True


print((N * (N - 1) // 2 - M if not dfs(0, 1) else color.count(1) * color.count(-1) - M))

# 忘れないように
import sys

sys.setrecursionlimit(10**9)
N, M = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)
# 0は未着色を表す
color = [0] * N
# 二部グラフ判定dfs
def dfs(v, c):
    color[v] = c
    for to in G[v]:
        if color[to] == c:
            return False
        if color[to] == 0 and not dfs(to, -c):
            return False
    return True


Bipartite = dfs(0, 1)
if Bipartite:
    White = color.count(1)
    Black = color.count(-1)
    print((White * Black - M))
else:
    print((N * (N - 1) // 2 - M))

+# 忘れないように -print((N * (N - 1) // 2 - M if not dfs(0, 1) else color.count(1) * color.count(-1) - M)) +Bipartite = dfs(0, 1) +if Bipartite: +    White = color.count(1) +    Black = color.count(-1) +    print((White * Black - M)) +else: +    print((N * (N - 1) // 2 - M))