#include <vector>
#include <iostream>
using namespace std;
int N, M, a, b, ct, col[100009]; vector<int> g[100009];
bool dfs(int pos, int x) {
	if (col[pos] == -1) {
		col[pos] = x;
		ct += x;
	}
	else return col[pos] == x;
	bool ret = true;
	for (int i : g[pos]) {
		if (!dfs(i, x ^ 1)) return false;
	}
	return true;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b; a--, b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	fill(col, col + N, -1);
	bool ret = dfs(0, 0);
	if (!ret) cout << 1LL * N * (N - 1) / 2 - M << endl;
	else cout << 1LL * ct * (N - ct) - M << endl;
	return 0;
}