#include<bits/stdc++.h>

int main(){
    using namespace std;
    unsigned long N, M;
    cin >> N >> M;
    vector<unsigned long> uf(2 * N), sz(2 * N);
    iota(uf.begin(), uf.end(), 0UL);
    fill(sz.begin(), sz.begin() + N, 1);
    const auto& find = [&uf](unsigned long i) -> unsigned long {
        while(i != uf[i])i = uf[i] = uf[uf[i]];
        return i;
    };
    const auto& unite = [&uf, &sz, &find](unsigned long i, unsigned long j) -> unsigned long {
        i = find(i);
        j = find(j);
        if(i == j)return 0;
        if(sz[i] < sz[j])swap(i, j);
        sz[i] += sz[j];
        uf[j] = i;
        return 1;
    };
    const auto& add_edge = [&N, &unite](unsigned long i, unsigned long j) -> void { unite(i, j + N); unite(i + N, j); };
    for(unsigned long i{0}, u, v; i < M; ++i){
        cin >> u >> v;
        add_edge(u - 1, v - 1);
    }
    if(find(0) == find(N))cout << N * (N - 1) / 2 - M << endl;
    else cout << sz[find(0)] * sz[find(N)] - M << endl;
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("in.txt", "r", stdin);
	int n, m;
	cin >> n >> m;
	vector<vi> adj(n);
	rep(i,0,m) {
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	vi side(n, -1);
	bool is_bipartite = true;
	queue<int> q;
	q.push(0);
	side[0] = 0;
	while(!q.empty()) {
		int v = q.front();
		q.pop();
		for(int u : adj[v]) {
			if(side[u] == -1) {
				side[u] = (side[v] ^ 1);
				q.push(u);
			} else {
				is_bipartite &= (side[u] != side[v]);
			}
		}
	}
	if(is_bipartite) {
		int b, w;
		b = w = 0;
		rep(i,0,n) {
			if(side[i] == 0) {
				b++;
			} else {
				w++;
			}
		}
		cout << (ll)b * w - m << '\n';
	} else {
		cout << (ll)(n-1)*n / 2 - m << '\n';
	}
	return 0;
}
