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: v 
  N,M = map(int, input().split())
  es = [[] for i in range(N)]
  for i in range(M):
      a,b = map(int, input().split())
      a,b = a-1,b-1
          es[a].append(b)
          es[b].append(a)
  
  colors = [0 for i in range(N)]
  
  def is_bipartite():
      stack = [(0,1)]
      while stack:
          v,color = stack.pop()
          colors[v] = color
          for to in es[v]:
              if colors[to] == color:
                   return False
              if colors[to] == 0:
                   stack.append((to, -color))
      return True
  
  if is_bipartite():
      b = (sum(colors) + N) // 2
      w = N-b
      print(b*w - M)
  else:
      all = N*(N-1) // 2
      print(all - M)
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."}]