#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int long long
typedef long long ll;

int color[200000];

int n,m;
vector<vector<int>> v(200000);
/*
bool dfs(int nn, int pre, int c){
    for(int x:v[nn]){
        if(x==pre) continue;
        if(color[x]==-1) color[x]=1-c;
        //if(color[x]!=c) continue;
        if(color[x]==c) return false;
        
        if(!dfs(x,nn,color[x])) return false;
    }

    return true;
}*/

bool dfs(int vv,int c){
    color[vv]=c;
    for(auto x:v[vv]){
        if(color[x]==c) return false;
        if(color[x]==0 && !dfs(x,-c)) return false;
    }
    return true;
}


signed main(){
    cin >> n >> m;
    memset(color,0,sizeof(color));
    rep(i,m){
        int aa,bb;
        cin >> aa >> bb;
        v[aa-1].push_back(bb-1);
        v[bb-1].push_back(aa-1);
    }

    //color[0]=0;
    rep(i,n){
        if(color[i]==0){
            if(!dfs(i,1)){
                cout << ((n*(n-1))/2)-m << endl;
                return 0;
            }
        }
    }


    int white=0;
    int black=0;
    rep(i,n){
        if(color[i]==1) white++;
        else black++;
    }
    //cout << white << black << endl;
    cout << white*black-m << endl;
    


    


}
#include <bits/stdc++.h>

using namespace std;

class UnionFind {
 public:
  std::vector<int> parent;

  UnionFind(int n) : parent(n, -1) {}

  int root(int x) {
    if (parent[x] < 0) return x;
    return parent[x] = root(parent[x]);
  }

  bool issame(int x, int y) { return root(x) == root(y); }

  int size(int x) { return -parent[root(x)]; }

  bool unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if (rx == ry) return false;
    if (parent[rx] > parent[ry]) std::swap(rx, ry);
    parent[rx] += parent[ry];
    parent[ry] = rx;
    return true;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  UnionFind uf(2 * N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    uf.unite(a, b + N);
    uf.unite(a + N, b);
  }
  if (uf.issame(0, N)) {
    cout << 1LL * N * (N - 1) / 2 - M << '\n';
  } else {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
      if (uf.issame(0, i)) cnt++;
    }
    // cout << cnt << '\n';
    cout << 1LL * cnt * (N - cnt) - M << '\n';
  }
  return 0;
}
