//
//  main.cpp
//
 
#include <algorithm>
#include <array>
#include <assert.h>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
 
template<typename T>
vector<T> make_vec_nd(T init, size_t size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, size_t size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}

#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,a,b) for(ll i=(a)-1;i>=(b);i--)

vector<vector<ll>> graph;
vector<bool> visited;

void dfs(ll now) {
	visited[now] = true;
	for (ll to : graph[now]) {
		if (!visited[to]) {
			dfs(to);
		}
	}
}

int main() {
	ll N, M;
	cin >> N >> M;
	graph.resize(2*N);
	rep(i,0,M) {
		ll a, b;
		cin >> a >> b;
		a--;
		b--;
		graph[2*a].push_back(2*b+1);
		graph[2*b+1].push_back(2*a);
		graph[2*a+1].push_back(2*b);
		graph[2*b].push_back(2*a+1);
	}
	visited.resize(2*N);
	dfs(0);
	ll cnt = 0;
	rep(i,0,N) {
		if (visited[2*i]) {
			cnt++;
		}
	}
	ll ans = 0;
	rep(i,0,N) {
		bool have_true = false;
		bool have_false = false;
		for (ll to : graph[2*i]) {
			to /= 2;
			if (visited[2*to]) {
				have_true = true;
			} else {
				have_false = true;
			}
		}
		ll ans_loc = 0;
		if (have_true) {
			ans_loc += cnt;
			if (visited[2*i]) {
				ans_loc--;
			}
		}
		if (have_false) {
			ans_loc += N - cnt;
			if (!visited[2*i]) {
				ans_loc--;
			}
		}
		// cout << i+1 << ":" << ans_loc << endl;
		ans += ans_loc;
	}
	cout << ans / 2 - M << endl;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cassert>
#include<numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
const int INF = 1001001001;
const long long LINF = 1001002003004005006ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int,int> P;

using Graph = vector<vector<int>>;

// 二部グラフ判定
vector<int> color;
bool dfs(const Graph &G, int v, int cur = 0) {
    color[v] = cur;
    for (auto next_v : G[v]) {
        // 隣接頂点がすでに色確定していた場合
        if (color[next_v] != -1) {
            if (color[next_v] == cur) return false; // 同じ色が隣接したらダメ
            continue;
        }

        // 隣接頂点の色を変えて、再帰的に探索 (一回でも false が返ってきたら false)
        if (!dfs(G, next_v , 1 - cur)) return false;
    }
    return true;
}

int main(){
    int n,m;
    cin >> n >> m;
    Graph G(n);
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--,b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    color.assign(n, -1);
    bool is_bipartite = dfs(G,0);
    if(is_bipartite){
        int b=0;int w=0;
        rep(i,n){
            if(color[i]==0)b++;
            else w++;
        }
        cout << (ll)b*w - m << endl;
    }else{
        cout << (ll)n*(n-1)/2 - m << endl;
    }
}