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
  from collections import deque
  
  readline = sys.stdin.buffer.readline
  ni = lambda: int(readline().rstrip())
  nm = lambda: map(int, readline().split())
  nl = lambda: list(map(int, readline().split()))
  
  
  def solve():
      mod = 10**9 + 7
      n, m = nm()
      G = [list() for _ in range(n)]
      for _ in range(m):
          u, v = nm()
          u -= 1
          v -= 1
          G[u].append(v)
          G[v].append(u)
      col = [-1] * n
      q = deque([0])
      col[0] = 1
      while q:
          v = q.popleft()
          for x in G[v]:
              if col[x] < 0:
                  col[x] = col[v] ^ 1
                  q.append(x)
              elif col[x] == col[v]:
                  print(n * (n - 1) // 2 - m)
                  return
      bl = sum(col)
      wh = n - bl
      print(bl * wh - m)
      return
  
  
  solve()
  
  # T = ni()
  # for _ in range(T):
  #     solve()
  
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."}]