import sys

sys.setrecursionlimit(100000)



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

adj_list = { i: [] for i in range(1, N+1) }



for i in range(M):

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

  adj_list[a].append(b)

  adj_list[b].append(a)



visited = [False]*(N+1)

colors = [None] * (N)

is_bipartite = True



## improved dfs ###

def dfs(node, c):

  colors[node-1] = c

  visited[node] = True

  for nei in adj_list[node]:

    if colors[nei-1] == c:

      return False

    if not visited[nei] and not dfs(nei, 1-c):

      return False



  return True



if dfs(1, 1):

  black = colors.count(1)

  print((black*(N-black) - M))

else:

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

sys.setrecursionlimit(100000)



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

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

for _ in range(M):

  u,v = list(map(int,input().split()))

  u -= 1

  v -= 1

  adj[u].append(v)

  adj[v].append(u)



color = [None] * N

def dfs(n, c):

  color[n] = c

  for nei in adj[n]:

    if color[nei] is not None:

      if color[nei] == c: 

        return False

    elif not dfs(nei, 1-c):

      return False

    # else:

    #   dfs(nei, 1-c)



  return True



if dfs(0,1):

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

else:

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

import sys

sys.setrecursionlimit(100000)
N, M = list(map(int, input().split()))
adj_list = {i: [] for i in range(1, N + 1)}
for i in range(M):
    a, b = list(map(int, input().split()))
    adj_list[a].append(b)
    adj_list[b].append(a)
visited = [False] * (N + 1)
colors = [None] * (N)
is_bipartite = True
## improved dfs ###
def dfs(node, c):
    colors[node - 1] = c
    visited[node] = True
    for nei in adj_list[node]:
        if colors[nei - 1] == c:
            return False
        if not visited[nei] and not dfs(nei, 1 - c):
            return False
    return True


if dfs(1, 1):
    black = colors.count(1)
    print((black * (N - black) - M))
else:
    print((N * (N - 1) // 2 - M))

import sys

sys.setrecursionlimit(100000)
N, M = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(M):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)
color = [None] * N


def dfs(n, c):
    color[n] = c
    for nei in adj[n]:
        if color[nei] is not None:
            if color[nei] == c:
                return False
        elif not dfs(nei, 1 - c):
            return False
        # else:
        #   dfs(nei, 1-c)
    return True


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

-adj_list = {i: [] for i in range(1, N + 1)} -for i in range(M): -    a, b = list(map(int, input().split())) -    adj_list[a].append(b) -    adj_list[b].append(a) -visited = [False] * (N + 1) -colors = [None] * (N) -is_bipartite = True -## improved dfs ### -def dfs(node, c): -    colors[node - 1] = c -    visited[node] = True -    for nei in adj_list[node]: -        if colors[nei - 1] == c: +adj = [[] for _ in range(N)] +for _ in range(M): +    u, v = list(map(int, input().split())) +    u -= 1 +    v -= 1 +    adj[u].append(v) +    adj[v].append(u) +color = [None] * N + + +def dfs(n, c): +    color[n] = c +    for nei in adj[n]: +        if color[nei] is not None: +            if color[nei] == c: +                return False +        elif not dfs(nei, 1 - c): -        if not visited[nei] and not dfs(nei, 1 - c): -            return False +        # else: +        #   dfs(nei, 1-c) -if dfs(1, 1): -    black = colors.count(1) -    print((black * (N - black) - M)) +if dfs(0, 1): +    print((color.count(1) * color.count(0) - M))