// Slower C++ solution:
#pragma GCC optimize(3)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<string>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<list>

#include<queue>

#include<stack>

#include<bitset>

#include<deque>

using namespace std;

#define ll long long

// #define inf 0x3f3f3f3f

#define ri register int

#define il inline

#define fi first

#define se second

#define mp make_pair

#define pi pair<int,int>

#define mem0(x) memset((x),0,sizeof (x))

#define mem1(x) memset((x),0x3f,sizeof (x))

il char gc()

{

    static const int BS = 1 << 22;

    static unsigned char buf[BS], *st, *ed;

    if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);

    return st == ed ? EOF : *st++;

}

#define gc getchar

template<class T>void in(T &x)

{

    x = 0;

    bool f = 0;

    char c = gc();

    while (c < '0' || c > '9')

    {

        if (c == '-') f = 1;

        c = gc();

    }

    while ('0' <= c && c <= '9')

    {

        x = (x << 3) + (x << 1) + (c ^ 48);

        c = gc();

    }

    if (f) x = -x;

}

#undef gc

#define pb push_back

#define N 100010

#define M N<<1

int n, m;

int v[M], nx[M];

int cnt, head[N];

il void add(int uu, int vv)

{

    v[++cnt] = vv, nx[cnt] = head[uu];

    head[uu] = cnt;

}

int col[N];

bool ok = 1;

int sz;

void dfs(int x)

{

    if (col[x] == 2) ++sz;

    for (ri i = head[x]; i; i = nx[i])

    {

        if (col[v[i]])

        {

            if (col[v[i]] == col[x])

            {

                ok = 0;

                return;

            }

        }

        else

        {

            col[v[i]] = col[x] ^ 1;

            dfs(v[i]);

        }

    }

}

signed main()

{

#ifndef ONLINE_JUDGE

    //freopen("in.in", "r", stdin);

#endif

    in(n), in(m);

    for (ri i = 1, a, b; i <= m; ++i)

    {

        in(a), in(b);

        add(a, b);

        add(b, a);

    }

    col[1] = 2;

    dfs(1);

    if (ok == 0)

    {

        printf("%lld", (ll)n * (n - 1) / 2 - m);

    }

    else

    {

        printf("%lld", (ll)sz * (n - sz) - m);

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6838894617851674x):
#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;



namespace io {

#define gc() (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++)

	const int SIZ = 1 << 21 | 1;

	char *iS, *iT, ibuff[SIZ], obuff[SIZ], *oS = obuff, *oT = oS + SIZ - 1, fu[110], c;

	int fr;

	inline void out() {

		fwrite(obuff, 1, oS - obuff, stdout);

		oS = obuff;

	}

	template<class Type>

	inline void read(Type &x) {

		x = 0;

		Type y = 1;

		for (c = gc(); (c > '9' || c < '0') && c != '-'; c = gc());

		c == '-' ? y = -1 : x = (c & 15);

		for (c = gc(); c >= '0' && c <= '9'; c = gc())

			x = x * 10 + (c & 15);

		x *= y;

	}

	template<class Type>

	inline void print(Type x, char text = '\n') {

		if (x < 0)

			*oS++ = '-', x *= -1;

		if (x == 0)

			*oS++ = '0';

		while (x)

			fu[++fr] = x % 10 + '0', x /= 10;

		while (fr)

			*oS++ = fu[fr--];

		*oS++ = text;

		out();

	}

}

using namespace io;

#define ll long long

const int maxn = 100010;



int n, m, a, b;

int col[maxn + 5], lnk[maxn + 5], son[maxn << 1], nxt[maxn << 1];

int u;



inline void Add(int x, int y) {

	son[++u] = y;

	nxt[u] = lnk[x];

	lnk[x] = u;

}



void dfs(int x, int now = 0, int fa = 0) {

	col[x] = now; now ^= 1;

	for (int j = lnk[x]; j; j = nxt[j]) {

		if (col[son[j]] == -1)

			dfs(son[j], now, x);

		if (col[son[j]] != now)

			print((ll)n*(n - 1) / 2 - m), exit(0);

	}

}



int main() {

	read(n);

	read(m);

	memset(col, 255, sizeof(col));

	for (int i = 1, x, y; i <= m; i++)

		read(x), read(y), Add(x, y), Add(y, x);

	dfs(1);

	for (int i = 1; i <= n; i++)

		col[i] ? ++a : ++b;

	print((ll)a * b - m);

	return 0;

}