#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath> // 変数名にy1が使えなくなるかも…。
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <string>

typedef __int128_t int128_t;
std::istream &operator>>(std::istream& input, int128_t& value) { // int128_tの入力。入力が64bitに収まる前提。
    long long tmp; input >> tmp; value = tmp;
    return input;
}
std::ostream &operator<<(std::ostream& output, const int128_t value) { // int128_tの出力。出力が64bitに収まる前提。
    output << (long long)value;
    return output;
}

class Direct_Graph {
    public:
    struct Edge { 
        int to; long long cost;
    };
    std::vector<std::vector<Edge>> G;
    int node_num;
    Direct_Graph() {}
    Direct_Graph(const int node_num_in) {
        node_num = node_num_in;
        G.resize(node_num);
    }
    void add_edge(const int from, const int to, const long long cost) {
        Edge edge; edge.to = to; edge.cost = cost;
        G[from].push_back(edge);
    }
    void add_edge_both(const int node1, const int node2, const long long cost) {
        add_edge(node1, node2, cost);
        add_edge(node2, node1, cost);
    }

    std::vector<long long> Dijkstra(int s, const long long dist_inf) {
        std::vector<long long> dist; dist.resize(node_num);
        for (int i = 0; i < dist.size(); i++) {
            dist[i] = dist_inf;
        }
        typedef std::pair<long long, int> Pair;

        std::priority_queue <Pair, std::vector<Pair>, std::greater<Pair>> que;
        dist[s] = 0;
        que.push(Pair(0, s));

        while (!que.empty()) {
            Pair pair = que.top(); que.pop();
            int v = pair.second;
            if (dist[v] < pair.first) { continue; }
            for (Edge edge : G[v]) {
                if (dist[v] + edge.cost < dist[edge.to]) {
                    dist[edge.to] = dist[v] + edge.cost;
                    que.push(Pair(dist[edge.to], edge.to));
                }
            }
        }
        return dist;
    }

    std::vector<std::vector<long long>> Warshall_Floyd(const long long dist_inf) {
        std::vector<std::vector<long long>> dist; dist.resize(node_num);
        for (int i = 0; i < dist.size(); i++) {
            dist[i].resize(node_num);
            for (int j = 0; j < dist[i].size(); j++) {
                dist[i][j] = dist_inf;
            }
            dist[i][i] = 0;
            for (auto e : G[i]) {
                dist[i][e.to] = std::min(dist[i][e.to], e.cost);
            }
        }
        for (int k = 0; k < node_num; k++) {
            for (int i = 0; i < node_num; i++) {
                for (int j = 0; j < node_num; j++) {
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        return dist;
    }
};

const int MAX_N = 100010;
const int MAX_M = 100010;
int64_t N, M;
int A[MAX_M], B[MAX_M];

Direct_Graph dg = Direct_Graph(MAX_N);

bool bipartite_search(const int node, const int c, std::vector<int>& ret) {
    assert(c == 1 || c == -1);
    if (ret[node] == -c) { return false; }
    if (ret[node] == c) { return true; }
    assert(ret[node] == 0);
    ret[node] = c;
    for (auto e : dg.G[node]) {
        if (!bipartite_search(e.to, -c, ret)) {
            return false;
        }
    }
    return true;
}

std::pair<bool, std::vector<int>> is_bipartite(const int begin, const int end) {
    std::vector<int> ret; ret.resize(end+1, 0);
    for (int i = begin; i <= end; i++) {
        if (ret[i] == 0 && !bipartite_search(i, 1, ret)) {
            return std::pair<bool, std::vector<int>>({false, ret});
        }
    }
    return std::pair<bool, std::vector<int>>({true, ret});
}

int main(int argc, char **argv) {
    std::cin >> N >> M;

    for (int i = 1; i <= M; i++) {
        std::cin >> A[i] >> B[i];
    }

    for (int i = 1; i <= M; i++) {
        dg.add_edge_both(A[i], B[i], 1);
    }

    auto is_bp = is_bipartite(1, N);

    if (is_bp.first) {
        int64_t cnt1 = 0;
        int64_t cnt2 = 0;
        for (int i = 1; i <= N; i++) {
            if (is_bp.second[i] == 1) {
                cnt1++;
            } else {
                cnt2++;
            }
        }
        std::cout << cnt1 * cnt2 - M << std::endl;
    } else {
        std::cout << N * (N - 1) / 2 - M << std::endl;
    }

    return 0;
}

Measured memory_bytes: 9600