 #include <bits/stdc++.h>
 using namespace std;
 const int maxn=100005;
 int n,m,u,v,res1,res2,col[maxn];
 vector<int> G[maxn];
 bool dfs(int u,int c) {
    col[u]=c;
    for (int i=0;i<(int)G[u].size();++i) {
        int v=G[u][i];
        if (!col[v]) {
            if (!dfs(v,3-c))
                return false;
        } else if (col[v]==col[u])
            return false;
    }
    return true;
 }
 int main()
 {
     scanf("%d%d",&n,&m);
     for (int i=0;i<m;++i) {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
     }
     if (dfs(1,1)) {
        for (int i=1;i<=n;++i)
            (col[i]==1)?++res1:++res2;
        printf("%lld\n",1LL*res1*res2-m);
     } else
        printf("%lld\n",1LL*n*(n-1)/2-m);
     return 0;
 }
