output_description: Find the maximum possible number of edges that can be added.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      A_1 B_1
      A_2 B_2
      :
      A_M B_M
attempt: # 設定
  import sys
  
  input = sys.stdin.buffer.readline
  
  # ライブラリインポート
  from collections import defaultdict
  import queue
  
  
  # 入力受け取り
  def getlist():
      return list(map(int, input().split()))
  
  
  INF = float("inf")
  
  
  class Graph(object):
      def __init__(self):
          self.graph = defaultdict(list)
  
      def __len__(self):
          return len(self.graph)
  
      def add_edge(self, a, b):
          self.graph[a].append(b)
  
      def get_nodes(self):
          return self.graph.keys()
  
  
  class BFS(object):
      def __init__(self, graph, s, N):
          self.g = graph.graph
          self.Q = queue.Queue()
          self.Q.put(0)
          self.W = [INF] * N  # sからの距離
          self.visit = ["No"] * N  # 見たか判定
          self.visit[s] = "Yes"
          self.W[s] = 0
          self.judge = "Yes"
          while not self.Q.empty():
              v = self.Q.get()
              for i in self.g[v]:
                  if self.visit[i] == "No":
                      self.W[i] = self.W[v] + 1
                      self.Q.put(i)
                      self.visit[i] = "Yes"
                  # 二部グラフ判定
                  else:
                      if (self.W[i] - self.W[v] - 1) % 2 == 1:
                          self.judge = "No"
                          break
  
  
  # 処理内容
  def main():
      N, M = getlist()
      G = Graph()
      for i in range(M):
          a, b = getlist()
          G.add_edge(a - 1, b - 1)
          G.add_edge(b - 1, a - 1)
      BF = BFS(G, 0, N)
      if BF.judge == "No":
          print(int(N * (N - 1) // 2) - M)
      else:
          even = 0
          odd = 0
          for i in BF.W:
              if i % 2 == 0:
                  even += 1
              else:
                  odd += 1
          print(even * odd - M)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  Rng has a connected undirected graph with N vertices. Currently, there are M
  edges in the graph, and the i-th edge connects Vertices A_i and B_i.
  
  Rng will add new edges to the graph by repeating the following operation:
  
    * Operation: Choose u and v (u \neq v) such that Vertex v can be reached by traversing exactly three edges from Vertex u, and add an edge connecting Vertices u and v. It is not allowed to add an edge if there is already an edge connecting Vertices u and v.
  
  Find the maximum possible number of edges that can be added.
samples: [{"input": "6 5\n    1 2\n    2 3\n    3 4\n    4 5\n    5 6", "output": "4\n    \n\nIf we add edges as shown below, four edges can be added, and no more.\n\n![](https://img.atcoder.jp/code-\nfestival-2017-qualb/6e99dccc06ac8b14d9ca2e297524bc0c.png)\n\n* * *"}, {"input": "5 5\n    1 2\n    2 3\n    3 1\n    5 4\n    5 1", "output": "5\n    \n\nFive edges can be added, for example, as follows:\n\n  * Add an edge connecting Vertex 5 and Vertex 3.\n  * Add an edge connecting Vertex 5 and Vertex 2.\n  * Add an edge connecting Vertex 4 and Vertex 1.\n  * Add an edge connecting Vertex 4 and Vertex 2.\n  * Add an edge connecting Vertex 4 and Vertex 3."}]