#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int p[N],noww[2*N],goal[2*N],col[N],c[5];
long long n,m,cnt,t1,t2,nb;
void link(int f,int t)
{
    noww[++cnt]=p[f];
    goal[cnt]=t,p[f]=cnt;
}
void dye(int nde,int cor)
{
    col[nde]=cor,c[cor]++;
    for(int i=p[nde];i;i=noww[i])
        if(!col[goal[i]]) dye(goal[i],3-cor);
        else if(col[goal[i]]==cor) {nb=true; return ;}
}
int main ()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld",&t1,&t2),link(t1,t2),link(t2,t1);
    for(int i=1;i<=n;i++)
        if(!col[i]) dye(i,1);
    if(nb) printf("%lld",1ll*n*(n-1)/2-m);
    else printf("%lld",1ll*c[1]*c[2]-m);
    return 0;
}