// Slower C++ solution:
#include<ctime>

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstdlib>

#include<cmath> 

#include<cstring> 

#include<cassert>

#include<string>

#include<sstream>

#include<fstream>

#include<deque>

#include<queue>

#include<vector>

#include<map>

#include<list>

#include<stack>

#include<set>

#include<bitset>

#include<iomanip>

#include<utility>

#include<functional>

#include<cctype>

#include<cerrno>

#include<cfloat>

#include<ciso646>

#include<climits>

#include<clocale>

#include<complex>

#include<csetjmp>

#include<csignal>

#include<cstdarg>

#include<cstddef>

#include<cwchar>

#include<cwctype>

#include<exception>

#include<locale>

#include<numeric>

#include<new>

#include<stdexcept>

#include<limits>

using namespace std;



#define ll long long

#define INF 1e9

#define rep(i,n) for(int (i)=0;(i)<n;i++)

#define REP(i,n) for(int (i)=1;(i)<=n;i++)

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

inline void Fail(){

	printf("0");

	exit(0);

}



const int maxn=100005;

int n,m,cnt[2];

bool ok=true;

vector<int>edge[maxn];

int vis[maxn];



void dfs(int x,int col){

	if(vis[x]!=-1){

		if(vis[x]!=col)ok=false;

		return;

	}

	vis[x]=col;

	rep(i,edge[x].size()){

		int y=edge[x][i];

		dfs(y,col^1);

	}

}



int main(){

	scanf("%d%d",&n,&m);

	rep(i,m){

		int u,v;

		scanf("%d%d",&u,&v);

		edge[u].push_back(v);

		edge[v].push_back(u);

	}

	memset(vis,-1,sizeof(vis));

	dfs(1,1);

	if(ok){

		REP(i,n)cnt[vis[i]]++;

		printf("%lld",1LL*cnt[0]*cnt[1]-m);

	}

	else{

		printf("%lld",1LL*n*(n-1)/2LL-m);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.971475427256743x):
#include<ctime>

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstdlib>

#include<cmath> 

#include<cstring> 

#include<cassert>

#include<string>

#include<sstream>

#include<fstream>

#include<deque>

#include<queue>

#include<vector>

#include<map>

#include<list>

#include<stack>

#include<set>

#include<bitset>

#include<iomanip>

#include<utility>

#include<functional>

#include<cctype>

#include<cerrno>

#include<cfloat>

#include<ciso646>

#include<climits>

#include<clocale>

#include<complex>

#include<csetjmp>

#include<csignal>

#include<cstdarg>

#include<cstddef>

#include<cwchar>

#include<cwctype>

#include<exception>

#include<locale>

#include<numeric>

#include<new>

#include<stdexcept>

#include<limits>

using namespace std;



#define ll long long

#define INF 1e9

#define rep(i,n) for(int (i)=0;(i)<n;i++)

#define REP(i,n) for(int (i)=1;(i)<=n;i++)

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

inline void Fail(){

	printf("0");

	exit(0);

}



const int maxn=100005;

int n,m,cnt[2];

bool ok=true;

int f[maxn*2];



int Find(int x){

	return f[x]==x?x:f[x]=Find(f[x]);

}



void Union(int x,int y){

	x=Find(x);y=Find(y);

	if(x!=y)f[x]=y;

}



int main(){

	scanf("%d%d",&n,&m);

	REP(i,2*n)f[i]=i;

	rep(i,m){

		int u,v;

		scanf("%d%d",&u,&v);

		Union(u,v+n);

		Union(u+n,v);

	}

	REP(i,n)if(Find(i)==Find(i+n))ok=false;

	if(ok){

		REP(i,n*2)if(Find(1)==Find(i)){

			if(i<=n)cnt[0]++;

			else cnt[1]++;

		}

		printf("%lld",1LL*cnt[0]*cnt[1]-m);

	}

	else{

		printf("%lld",1LL*n*(n-1)/2LL-m);

	}

	return 0;

}