import sys

sys.setrecursionlimit(10**7)



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



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

for i in range(M):

  tempa, tempb = list(map(int,input().split()))

  michi[tempa-1].append(tempb-1)

  michi[tempb-1].append(tempa-1)

#print(michi)

  

colors = [0 for i in range(N)]



def dfs(v,color):

  colors[v] = color

  for to in michi[v]:

    if colors[to] == color:

      return False

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

      return False

  return True



if dfs(0,1):

  a = colors.count(1)

  b = colors.count(-1)

  #print(colors)

  print((a*b-M))

else:

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

sys.setrecursionlimit(10**7)



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

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

for i in range(M):

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

  a-=1;b-=1

  edge[a].append(b)

  edge[b].append(a)

#print(edge)

colors = [0 for i in range(N)]



def dfs(v,color):

  colors[v] = color

  for u in edge[v]:

    if colors[u] == color:

      return False

    if colors[u] == 0 and not dfs(u, -color):

      return False

  return True



#print(dfs(0,1),colors)

if dfs(0,1): #もし二部グラフなら

  one = 0; zero = 0

  for x in colors:

    if x == 1:

      one += 1

    else:

      zero += 1

  ans = one*zero-M

else:

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

print(ans)
import sys

sys.setrecursionlimit(10**7)
N, M = list(map(int, input().split()))
michi = [[] for i in range(N)]
for i in range(M):
    tempa, tempb = list(map(int, input().split()))
    michi[tempa - 1].append(tempb - 1)
    michi[tempb - 1].append(tempa - 1)
# print(michi)
colors = [0 for i in range(N)]


def dfs(v, color):
    colors[v] = color
    for to in michi[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True


if dfs(0, 1):
    a = colors.count(1)
    b = colors.count(-1)
    # print(colors)
    print((a * b - M))
else:
    print((N * (N - 1) // 2 - M))

import sys

sys.setrecursionlimit(10**7)
N, M = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
# print(edge)
colors = [0 for i in range(N)]


def dfs(v, color):
    colors[v] = color
    for u in edge[v]:
        if colors[u] == color:
            return False
        if colors[u] == 0 and not dfs(u, -color):
            return False
    return True


# print(dfs(0,1),colors)
if dfs(0, 1):  # もし二部グラフなら
    one = 0
    zero = 0
    for x in colors:
        if x == 1:
            one += 1
        else:
            zero += 1
    ans = one * zero - M
else:
    ans = N * (N - 1) // 2 - M
print(ans)

-michi = [[] for i in range(N)] +edge = [[] for _ in range(N)] -    tempa, tempb = list(map(int, input().split())) -    michi[tempa - 1].append(tempb - 1) -    michi[tempb - 1].append(tempa - 1) -# print(michi) +    a, b = list(map(int, input().split())) +    a -= 1 +    b -= 1 +    edge[a].append(b) +    edge[b].append(a) +# print(edge) -    for to in michi[v]: -        if colors[to] == color: +    for u in edge[v]: +        if colors[u] == color: -        if colors[to] == 0 and not dfs(to, -color): +        if colors[u] == 0 and not dfs(u, -color): -if dfs(0, 1): -    a = colors.count(1) -    b = colors.count(-1) -    # print(colors) -    print((a * b - M)) +# print(dfs(0,1),colors) +if dfs(0, 1):  # もし二部グラフなら +    one = 0 +    zero = 0 +    for x in colors: +        if x == 1: +            one += 1 +        else: +            zero += 1 +    ans = one * zero - M -    print((N * (N - 1) // 2 - M)) +    ans = N * (N - 1) // 2 - M +print(ans)