#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
const int mx=1e5+10;
vector<int>g[mx];
int color[mx];
bool bip=true;
uli cnt[2];
void dfs(int u){
  cnt[color[u]]++;
  for(int v:g[u]){
    if(color[v]==-1){
      color[v]=(color[u]^1);
      dfs(v);
    }
    else if(color[v]!=(color[u]^1)) bip=false;
  }
}
int main(){
  int n,m;
  scanf("%d %d",&n,&m);
  for(int i=0;i<m;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    g[--u].push_back(--v);
    g[v].push_back(u);
  }
  memset(color,-1,sizeof color);
  color[0]=0;
  dfs(0);
  if(bip)printf("%lld\n",cnt[0]*cnt[1]-m);
  else printf("%lld\n",(uli(n)*uli(n-1))/2ll-m);
  return 0;
}
