#include<bits/stdc++.h>
using namespace std;
int n,m,A;
vector<int> e[111111];
int col[111111];
long long int c2(long long int x){
	return x*(x-1)/2;
}
bool dfs(int x,int c){
	if(col[x] == 0){
		col[x] = c;
		if(c==1)A++;
	}else
	return col[x] == c;
	for(int y : e[x]){
		if(!dfs(y, -c))
			return false;
	}
	return true;
}
long long int calc(){
	if(dfs(1,1))
		return (long long int)A*(n-A);
	return c2(n);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0; i<m; i++){
		int x,y;
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	printf("%lld\n",calc()-m);
	return 0;
}
