#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int n, m;
vector<int>G[maxn];
int b, w;
int color[maxn];
bool bipartite(int u, int c){
    if(color[u] != 0 && color[u] != c) return false;
    if(color[u] != 0 && color[u] == c) return true;
    color[u] = c;
    if(c == 1) b++;
    else w++;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(!bipartite(v, 3 - c)) return false;
    }
    return true;

}
int main(){
    cin >> n >> m;
    int u, v;
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    if(!bipartite(u,1)){
        cout <<(ll) n * (n-1) / 2 - m <<"\n";
    }
    else cout << (ll)b*w-m <<"\n";
    return 0;
}
