\(d_i\) を操作前に頂点 \(i\) と繋がる黒で塗られた辺の本数とします。

操作の前後で各頂点と繋がる黒で塗られた辺の本数の偶奇は変わらないです。したがって、各頂点と繋がる黒で塗られた辺の本数の最大値は \(N-1-(N-1-d_i) \bmod 2\) となります。

よって、 答えの上界として \(\displaystyle \frac12\sum_{i=1}^N \left(N-1-(N-1-d_i) \bmod 2\right)\) が得られます。

この上界は達成可能です。

もし白で塗られた辺が \(2\) 本以上ある頂点が存在する場合、その頂点と白で塗られた辺で繋がれた \(2\) 頂点の \(3\) 頂点を操作として選ぶと黒で塗られた辺は必ず \(1\) 本以上増えます。したがって、黒で塗られた辺の本数が最大値となるような塗り方では、どの頂点と繋がる白で塗られた辺の本数も \(1\) 本以下です。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(M)\) です。

実装例(Python3)

n, m = map(int, input().split())
d = [0] * n
for i in range(m):
    u, v = map(int, input().split())
    d[u - 1] += 1
    d[v - 1] += 1
ans = n * (n - 1)
for i in range(n):
    ans -= (n - 1 - d[i]) % 2
print(ans // 2)