[1] グラフ \(G\) が連結な場合

まず、\(G\) が二部グラフかどうかを判定します。 二部グラフである場合は、さらに、同じ色の頂点同士を結ぶ辺がないように各頂点を黒と白で塗り分けます。

これは、深さ優先探索などのグラフ探索アルゴリズムによって \(O(N + M)\) 時間で行えます。 具体的には、まず \(1\) つの頂点を黒で塗り、それに隣接する頂点を白で塗り、さらにそれらに隣接する頂点を黒で塗り…と繰り返していけば良いです。また、その過程で同色に塗った頂点同士が隣接した場合は、\(G\) が二部グラフではないと判定できます。

\(G\) が二部グラフではない場合は、それに辺を \(1\) 本追加して得られるグラフも二部グラフではないので、本問題の答えは \(0\) です。

\(G\) が二部グラフである場合は、辺で結んでも二部グラフであり続けるような頂点のペアは、異なる色で塗られた頂点のペアです。 よって、頂点のペアの個数 \(N(N-1)/2\) から、同じ色で塗られた頂点同士のペアの個数と、初めから辺で結ばれている頂点のペアの個数 \(M\) を引いたものが答えです。

[2] グラフ \(G\) が連結とは限らない場合

まず、それぞれの連結成分について、「[1] グラフ \(G\) が連結な場合」で述べたように二部グラフかの判定と頂点の塗り分けを行います。 どれか一つの連結成分が二部グラフでなかった場合、\(G\) 全体も二部グラフではないので、本問題の答えは \(0\) です。

以下、すべての連結成分が二部グラフの場合を考えます。

同じ連結成分に属する頂点のペアについては、「[1] グラフ \(G\) が連結な場合」で述べた通りです。 一方、異なる連結成分に属する頂点同士のペアについては、その間に辺を追加して得られるグラフは必ず二部グラフとなります。 （例えば、連結成分 \(A\) の黒い頂点と連結成分 \(B\) の黒い頂点を辺で結ぶ場合、連結成分 \(B\) の白と黒を反転すれば、辺を追加後のグラフに対する色分けが得られます。）

よって、辺で結ぶことで二部グラフでなくなってしまうような頂点のペアとは、同じ連結成分に属する同じ色の頂点同士のペアです。

以上より本問題の答えは、頂点のペアの個数 \(N(N-1)/2\) から、各連結成分の同じ色に塗られた頂点同士のペアの個数を引き、さらに、初めから辺で結ばれている頂点のペアの個数 \(M\) を引いた

\[ \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 \]

です。ここで、\(C\) は連結成分の個数であり、\(B_i, W_i\) は \(i\) 番目の連結成分で黒、白に塗られた頂点の個数です。

以下に、C++ 言語による本問題の正解例を記載します。

#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;
}