#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
vector<int> bi[100005];
long long n,m,i,j,col[100005],x,y,cnt[3],bo;
void dfs(int x,int y)
{
	if (col[x]!=0) {if (col[x]!=y) bo=1;return;}
	col[x]=y,cnt[y]++;
	int i;
	for (i=0;i<bi[x].size();i++)
	{
		 dfs(bi[x][i],3-y);
	}
}
int main()
{
	cin>>n>>m;
	for (i=1;i<=m;i++)
	{
		cin>>x>>y;
		bi[x].push_back(y);
		bi[y].push_back(x);
	}
	dfs(1,1);
	if (bo) cout<<n*(n-1)/2-m; else cout<<cnt[1]*cnt[2]-m;
	return 0;
}