void main(){
  import std.stdio, std.string, std.conv, std.algorithm;
  
  int n, m; rd(n, m);
  auto g=new int[][](n, 0);
  foreach(_; 0..m){
    int a, b; rd(a, b);
    a--; b--;
    g[a]~=b; g[b]~=a;
  }

  auto c=new int[](n);
  fill(c, -1);
  bool dfs(int i, int w, int p=-1){
    c[i]=w;
    bool ret=true;
    foreach(j; g[i])if(j!=p){
      if(c[j]==-1) ret&=dfs(j, w^1, i);
      if((c[j]^w)==0) ret=false; 
    }
    return ret;
  }

  if(dfs(0, 0)){
    long w=0;
    foreach(e; c)if(e==0) w++;
    auto b=to!long(n)-w;
    writeln(w*b-m);
  }else{
    auto _n=to!long(n);
    writeln(_n*(_n-1)/2-m);
  }

}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}