Let \(d_i\) be the number of black edges connected to vertex \(i\) before operations.

The operation preserves the parity of black edges at each vertex. Therefore, the maximum number of black edges connected to each vertex is \(N-1-(N-1-d_i) \bmod 2\).

Thus, we obtain \(\displaystyle \frac12\sum_{i=1}^N \left(N-1-(N-1-d_i) \bmod 2\right)\) as an upper bound for the answer.

This upper bound is achievable.

If there exists a vertex connected to two or more white edges, choosing the three vertices consisting of that vertex and two vertices connected by white edges as an operation will always increase the number of black edges by at least \(1\). Therefore, in a coloring where the number of black edges is maximized, the number of white edges connected to any vertex is at most \(1\).

By implementing this appropriately, we can solve this problem. The time complexity is \(O(M)\).

Implementation Example (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)