#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;
const int INFTY = (1 << 21); // 2097152
// const ll INFTY = (1LL << 60);
const ll MD = 1000000007LL;
// fprintf(stderr, "%d %lld \n", x, xll);


int N, M;

class Edge{
public:
    int from, to, cost;
    Edge(int from = 0, int to = 0, int cost = 0) :
            from(from), to(to), cost(cost){}

    bool operator < (const Edge &e) const{
        return cost < e.cost;
    }
    bool operator >(const Edge &e) const{
        return cost > e.cost;
    }

};

class Node{
public:
    vector<Edge> edges;
    int sign;
    Node(){
        sign = 0;
    }
};

class Graph{
public:
    vector<Node> nodes;
    Graph(int n) {
        rep(i, n) { Node n;  nodes.push_back(n); }
    }
    Node& operator[](int i){
        return nodes[i];
    }
};

class Data{
public:
    int from, to, sign;
    Data(int from, int to, int sign) {
        this-> from = from;
        this-> to   = to;
        this-> sign = sign;
    }
};

Graph G(0);

bool dfs(int to, int sign){

    G[to].sign = sign;

    int s = sign * -1;
    for(auto &ee: G[to].edges){
        if(G[ee.to].sign != 0){
            if(G[ee.to].sign != s) return true;
        }
        else{
            bool extra = dfs(ee.to, s);
            if(extra) return true;
        }
    }

    return false;
}

bool dfs_run(){
    rep(i, N) G[i].sign = 0;
    return dfs(0, 1);
}

bool bfs(){

    queue<Data> q;
    q.push(Data(-1, 0, 1));

    rep(i, N) G[i].sign = 0;

    bool flg = false;

    ll NN = 0;

    while(!q.empty()){
        Data &d = q.front(); q.pop();
        fprintf(stderr, "%d->%d %d\n", d.from, d.to, d.sign);
        Node &n = G[d.to];
        n.sign = d.sign;

        for(auto &ee : n.edges){
            NN++;

            int s = d.sign * -1;
            Node &nn = G[ee.to];
            if(nn.sign != 0 && nn.sign != s){
                flg = true;
                continue;
            }
            if(nn.sign != 0 && nn.sign == s) {
                continue;
            }
            if(nn.sign == 0){
                nn.sign = s;
                q.push(Data(ee.from, ee.to, s));
            }
        }
    }

    cerr  << NN << endl;
    return flg;
}

int main() {

    // input
	cin >> N >> M;
    G = Graph(N);

	rep(i, M){
		int a, b;
        cin >> a >> b; a--; b--;
        G[a].edges.push_back(Edge(a, b, 0));
        G[b].edges.push_back(Edge(b, a, 0));
	}

    // run
    bool extra = dfs_run(); // bfs();

    if(extra){
        ll all = (ll)(N) * (ll)(N-1) / 2LL;
        ll ret = all - M;
        cout << ret << endl;
    }
    else{
        ll countP = 0;
        ll countM = 0;
        rep(i, N){
            if(G[i].sign == 1) countP++;
            if(G[i].sign == -1) countM++;
        }

        ll all = countP * countM;
        ll ret = all - M;
        cout << ret << endl;
    }

}

Measured memory_bytes: 8172