#include<bits/stdc++.h>

using namespace std;

vector<int> adj[100001];
int dist[100001];
bool oc = 0;
void dfs(int u){
    for(int i = 0; i < (int)adj[u].size(); i++){
        int v = adj[u][i];
        if(dist[v] == -1){
            dist[v] = dist[u] + 1;
            dfs(v);
        }
        else{
            if(abs(dist[v] - dist[u]) % 2 == 0){
                oc = 1;
                return ;
            }
        }
    }
}
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; i++)
        dist[i] = -1;
    dist[1] = 0;
    dfs(1);
    if(oc == 1){
        long long ans = (n - 1) * n / 2 - m;
        cout << ans;
    }
    else{
        int cnto = 0, cnte = 0;
        for(int i = 1; i <= n; i++){
            if(dist[i] % 2 == 0) cnte++;
            else cnto ++;
        }
        long long ans = cnte * cnto - m;
        cout << ans;
    }
}