#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

bool flag;
int col[100005];
ll cnt[2];

vector<int> G[100001];
void dfs(int v){
	cnt[col[v]]++;
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i];
		if(col[nv]==-1){
			col[nv]=1-col[v];
			dfs(nv);
		}else if(col[v]==col[nv]){
			flag=true;
		}
	}
}

int n,m;

int main(void){
	scanf("%d%d",&n,&m);
	flag=false;
	memset(col,-1,sizeof(col));
	for(int i=0;i<m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u--;
		v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	col[0]=0;
	dfs(0);
	if(!flag)printf("%lld\n",(ll)cnt[0]*cnt[1]-m);
	else printf("%lld\n",(ll)n*(n-1LL)/2LL-m);
	return 0;
}