from collections import deque



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

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

clr = [-1 for _ in range(N)]



#グラフ構築

for _ in range(1,M+1):

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

  u -= 1

  v -= 1

  adj[u].append((v,1))

  adj[v].append((u,1))



#二部グラフか否か判定  

vis = [0 for _ in range(N)]

q = deque([(0,0)])

is_bip = True

#print(clr)

while q:

  p, c = q.popleft()

  clr[p] = c

  vis[p] = 1

  for x, w in adj[p]:

    if vis[x] == 0:

      q.append((x,(w+c)%2))

      #print((x,(w+c)%2))

    else: 

      if (clr[x] + c) % 2 == 0:

        is_bip = False

        break

  if not is_bip:

    break

    

#ここから問題特有の処理

if is_bip:#二部グラフの場合

  apple = clr.count(0)

  orange = clr.count(1)

  #print(apple,orange,M)

  print((apple*orange-M))

  

else:#二部グラフでない場合

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

  
import sys



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

sys.setrecursionlimit(10**6)

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

for i in range(M):

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

  a -= 1

  b -= 1

  I[a].append(b)

  I[b].append(a)



C = [-1 for _ in range(N)] 

visited = set()



def DFS(p, c):

  C[p] = c

  flag = True

  for q in I[p]:

    #print(p,q)

    if C[q] == c:

      return False

    elif C[q] == -1:

      if not DFS(q, 1-c):

        return False

  return True



#print(DFS(0, 0))

#print(C)

print((C.count(0)*C.count(1)-M if DFS(0, 0) else N*(N-1)//2-M))

      

      

  

  

  

  
from collections import deque

N, M = list(map(int, input().split()))
adj = [[] for _ in range(N)]
clr = [-1 for _ in range(N)]
# グラフ構築
for _ in range(1, M + 1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    adj[u].append((v, 1))
    adj[v].append((u, 1))
# 二部グラフか否か判定
vis = [0 for _ in range(N)]
q = deque([(0, 0)])
is_bip = True
# print(clr)
while q:
    p, c = q.popleft()
    clr[p] = c
    vis[p] = 1
    for x, w in adj[p]:
        if vis[x] == 0:
            q.append((x, (w + c) % 2))
            # print((x,(w+c)%2))
        else:
            if (clr[x] + c) % 2 == 0:
                is_bip = False
                break
    if not is_bip:
        break
# ここから問題特有の処理
if is_bip:  # 二部グラフの場合
    apple = clr.count(0)
    orange = clr.count(1)
    # print(apple,orange,M)
    print((apple * orange - M))
else:  # 二部グラフでない場合
    print((N * (N - 1) // 2 - M))

import sys

N, M = list(map(int, input().split()))
sys.setrecursionlimit(10**6)
I = [[] for _ in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    I[a].append(b)
    I[b].append(a)
C = [-1 for _ in range(N)]
visited = set()


def DFS(p, c):
    C[p] = c
    flag = True
    for q in I[p]:
        # print(p,q)
        if C[q] == c:
            return False
        elif C[q] == -1:
            if not DFS(q, 1 - c):
                return False
    return True


# print(DFS(0, 0))
# print(C)
print((C.count(0) * C.count(1) - M if DFS(0, 0) else N * (N - 1) // 2 - M))

-from collections import deque +import sys -adj = [[] for _ in range(N)] -clr = [-1 for _ in range(N)] -# グラフ構築 -for _ in range(1, M + 1): -    u, v = list(map(int, input().split())) -    u -= 1 -    v -= 1 -    adj[u].append((v, 1)) -    adj[v].append((u, 1)) -# 二部グラフか否か判定 -vis = [0 for _ in range(N)] -q = deque([(0, 0)]) -is_bip = True -# print(clr) -while q: -    p, c = q.popleft() -    clr[p] = c -    vis[p] = 1 -    for x, w in adj[p]: -        if vis[x] == 0: -            q.append((x, (w + c) % 2)) -            # print((x,(w+c)%2)) -        else: -            if (clr[x] + c) % 2 == 0: -                is_bip = False -                break -    if not is_bip: -        break -# ここから問題特有の処理 -if is_bip:  # 二部グラフの場合 -    apple = clr.count(0) -    orange = clr.count(1) -    # print(apple,orange,M) -    print((apple * orange - M)) -else:  # 二部グラフでない場合 -    print((N * (N - 1) // 2 - M)) +sys.setrecursionlimit(10**6) +I = [[] for _ in range(N)] +for i in range(M): +    a, b = list(map(int, input().split())) +    a -= 1 +    b -= 1 +    I[a].append(b) +    I[b].append(a) +C = [-1 for _ in range(N)] +visited = set() + + +def DFS(p, c): +    C[p] = c +    flag = True +    for q in I[p]: +        # print(p,q) +        if C[q] == c: +            return False +        elif C[q] == -1: +            if not DFS(q, 1 - c): +                return False +    return True + + +# print(DFS(0, 0)) +# print(C) +print((C.count(0) * C.count(1) - M if DFS(0, 0) else N * (N - 1) // 2 - M))