#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<functional>
#include<cmath>
#include<map>
using namespace std;
int n, m, a, b; vector<int>x[100009]; int used[100009]; bool OK = false;
void dfs(int pos, int dep) {
	if (used[pos] != -1) {
		if (dep != used[pos])OK = true;
		return;
	}
	used[pos] = dep;
	for (int i = 0; i < x[pos].size(); i++)dfs(x[pos][i], dep ^ 1);
}
int main() {
	cin >> n >> m; for (int i = 1; i <= n; i++)used[i] = -1;
	for (int i = 0; i < m; i++) { cin >> a >> b; x[a].push_back(b); x[b].push_back(a); }
	dfs(1, 0);
	int V1 = 0, V2 = 0;
	for (int i = 1; i <= n; i++) { if (used[i] == 0)V1++; else V2++; }
	if (OK == false)cout << 1LL * V1*V2 - m << endl;
	else cout << (1LL * n*(n - 1) / 2LL) - (1LL * m) << endl;
	return 0;
}