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
  
  sys.setrecursionlimit(10**7)
  
  N, M = map(int, input().split())
  
  AB = [list(map(int, input().split())) for _ in range(M)]
  
  graph = [[] for _ in range(N)]
  for a, b in AB:
      graph[a−1].append(b - 1)
      graph[b - 1].append(a - 1)
  
  # 二部グラフかどうかの判定
  color = [None] * N
  color[0] = 0
  q = [0]
  while q:
      x = q.pop()
      for y in graph[x]:
          if color[y] is None:
              color[y] = 1 - color[x]
              q.append(y)
  
  # 二部グラフかどうか
  bg = all(color[a] != color[b] for a, b in AB)
  
  if bg:
      # 完全二部グラフにする
      x = sum(color)
      y = N - x
      answer = x * y - M
  else:
      # 完全グラフにする(奇数長のパスがある場合は必ず2ずつ減らしていけば長さが3になる)
      answer = N * (N - 1) // 2 - M
  
  print(answer)
  
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."}]