#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
ll n,m;
vector<int> g[100000];
int color[100000];
int a[100000],b[100000];
ll cnt1=0,cnt2=0;
bool dfs(int v,int c){
  color[v]=c;
  if(c>0) cnt1++;
  else cnt2++;
  for(int i=0;i<g[v].size();i++){
    if(color[g[v][i]]==c) return false;
    if(color[g[v][i]]==0&&!dfs(g[v][i],-c)) return false;
  }
  return true;
}
int main(){
  cin >> n >> m;
  for(int i=0;i<m;i++) cin >> a[i] >> b[i];
  for(int i=0;i<m;i++){
    g[a[i]-1].push_back(b[i]-1);
    g[b[i]-1].push_back(a[i]-1);
  }
  memset(color,0,sizeof(color));
  if(dfs(a[0]-1,1)) cout << cnt1*cnt2-m << "\n";
  else cout << n*(n-1)/2-m << "\n";
  
  return 0;
}


