#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

long long N,M;
int color[100010] = {0};
bool judge = true;
vector<vector<int>> v(100010);

bool dfs(long long n,long long c){
	color[n] = c;
	for(int i=0;i<v[n].size();i++){
		if(color[v[n][i]] == c) return false;
		else if(color[v[n][i]] == 0 && !dfs(v[n][i],-c)) return false;
	}
	return true;
}

int main(){
	cin >> N >> M;
	for(int i=0;i<M;i++){
		int a,b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	//for(int i=1;i<=N;i++) color[i] = 0;
	if(dfs(1,1)){
		long long b = 0,m = 0;
		for(int i=1;i<=N;i++){
			if(color[i] == 1) b++;
			else if(color[i] == -1) m++;
		}
		cout << b*m - M << endl;
	}else cout << N*(N-1)/2-M << endl;
}