[1] If graph \(G\) is connected

First, we determine if \(G\) is a bipartite graph. If it is, we paint each vertex black or white so that no edge connects vertices painted in the same color.

This can be done with a graph searching algorithm like Depth-First Search in an \(O(N + M)\) time. Specifically, first paint one vertex black, then paint adjacent vertices white, then paint white the vertices adjacent to those vertices, … and so on. If two vertices painted in the same color was found adjacent in the procedure, it appears that \(G\) is not a bipartite graph.

If \(G\) is not a bipartite graph, neither is a graph obtained by adding one edge to it, so the answer to this problem is \(0\).

If \(G\) is a bipartite graph, then the graph remains bipartite after adding an edge between two vertices if and only if they are painted in different colors. Therefore, the answer equals the number of pairs of vertices \(N(N-1)/2\) subtracted by the number of pairs of vertices painted in the same color, and by the number \(M\) of pairs of vertices that is initially connected by an edge.

[2] If the graph \(G\) is not necessarily connected

First, for each connected component, determine if it is bipartite and paint its vertices, just as we did in “[1] If graph \(G\) is connected.” If any connected component is not bipartite, neither is the whole \(G\), so the answer to this problem is \(0\).

We now assume that all the connected components are bipartite.

For the pair of vertices belonging to the same connected component, the situation is just as same as described in “[1] If graph \(G\) is connected.” On the other hand, for the pair belonging to different connected components, adding an edge between them always result in a bipartite graph. (For example, if you connect a black vertex of a connected component \(A\) and another black one of a connected component \(B\), then one can invert the colors of the connected component \(B\) to obtain the coloring after adding edges.)

Therefore, the graph becomes not bipartite by adding an edge between a pair of vertices if and only if they belongs to the same connected component and painted in the same color. Therefore, the answer equals the number of pairs of vertices \(N(N-1)/2\) subtracted by, for each connected component, the number of pairs of vertices painted in the same color, and by the number \(M\) of pairs of vertices that is initially connected by an edge:

\[ \frac{N(N-1)}{2} - \sum_{i = 1}^C \big(\frac{B_i(B_i-1)}{2} + \frac{W_i(W_i-1)}{2}\big) - M. \]

Here, \(C\) is the number of connected component, and \(B_i\) and \(W_i\) denote the number of vertices painted black and white in the \(i\)-th connected component.

The following is a sample code in C++ language:

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

ll n, m;
vector<int> G[200005];
int color[200005];

P dfs(int v, int p, int c){
  P ret = P(0, 0);
  color[v] = c;
  
  if(c == 1) ret.first++;
  else ret.second++;
  
  for(auto u : G[v]){
    if(u == p || color[u] == -c) continue;
    if(color[u] == c) return P(-1, -1);
    P res = dfs(u, v, -c);
    if(res.first == -1) return P(-1, -1);
    ret.first += res.first, ret.second += res.second;
  }
  return ret;
}

int main(void)
{
  cin >> n >> m;
  int u, v;
  for(int i = 1; i <= m; i++){
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  ll ans = n*(n-1)/2 - m;
  for(int i = 1; i <= n; i++){
    if(!color[i]){
      P res = dfs(i, -1, 1);
      if(res.first == -1){
        cout << 0 << endl;
        return 0;
      }
      ans -= res.first * (res.first-1) / 2;
      ans -= res.second * (res.second-1) / 2;
    }
  }
  cout << ans << endl;
  
  return 0;
}