#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

typedef pair<int, int> ii;

int n, m, cnt[2];
bool f[N][2];
vector<int> G[N];

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v), G[v].push_back(u);
	}
	queue<ii> qu;
	f[1][0] = 1, qu.push(ii(1, 0));
	while (qu.size()) {
		ii u = qu.front(); qu.pop();
		for (auto v : G[u.first]) {
			if (f[v][u.second ^ 1]) continue;
			f[v][u.second ^ 1] = 1, qu.push(ii(v, u.second ^ 1));
		}
	}
	long long res = 1LL * n * (n - 1) / 2 - m;
	for (int i = 1; i <= n; ++i) {
		if (f[i][0] && !f[i][1]) cnt[0]++;
		if (f[i][1] && !f[i][0]) cnt[1]++;
	}
	res -= 1LL * cnt[0] * (cnt[0] - 1) / 2;
	res -= 1LL * cnt[1] * (cnt[1] - 1) / 2;
	cout << res;
}