/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Pine1999
 */

#include <bits/stdc++.h>
#ifndef ATCODER_DSU_HPP
#define ATCODER_DSU_HPP 1

#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
    struct dsu {
    public:
        dsu() : _n(0) {}
        dsu(int n) : _n(n), parent_or_size(n, -1) {}

        int merge(int a, int b) {
            assert(0 <= a && a < _n);
            assert(0 <= b && b < _n);
            int x = leader(a), y = leader(b);
            if (x == y) return x;
            if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
            parent_or_size[x] += parent_or_size[y];
            parent_or_size[y] = x;
            return x;
        }

        bool same(int a, int b) {
            assert(0 <= a && a < _n);
            assert(0 <= b && b < _n);
            return leader(a) == leader(b);
        }

        int leader(int a) {
            assert(0 <= a && a < _n);
            if (parent_or_size[a] < 0) return a;
            return parent_or_size[a] = leader(parent_or_size[a]);
        }

        int size(int a) {
            assert(0 <= a && a < _n);
            return -parent_or_size[leader(a)];
        }

        std::vector<std::vector<int>> groups() {
            std::vector<int> leader_buf(_n), group_size(_n);
            for (int i = 0; i < _n; i++) {
                leader_buf[i] = leader(i);
                group_size[leader_buf[i]]++;
            }
            std::vector<std::vector<int>> result(_n);
            for (int i = 0; i < _n; i++) {
                result[i].reserve(group_size[i]);
            }
            for (int i = 0; i < _n; i++) {
                result[leader_buf[i]].push_back(i);
            }
            result.erase(
                    std::remove_if(result.begin(), result.end(),
                                   [&](const std::vector<int>& v) { return v.empty(); }),
                    result.end());
            return result;
        }

    private:
        int _n;
        // root node: -1 * component size
        // otherwise: parent
        std::vector<int> parent_or_size;
    };

}  // namespace atcoder

#endif  // ATCODER_DSU_HPP

//#include "../library/fenwicktree.hpp"
//#include "../library/modint.hpp"
//#include "../library/segtree.hpp"

using namespace std;
using namespace atcoder;

void C3Steps(std::istream& in, std::ostream& out) {
    int n, m;
    in >> n >> m;
    dsu d(2 * n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        in >> u >> v;
        --u; --v;
        d.merge(u, v + n);
        d.merge(u + n, v);
    }
    if (d.same(0, n)) {
        out << 1LL * n * (n - 1) / 2 - m << '\n';
    } else {
        long long ans = 0;
        for (int i = 0; i < n; ++i) if (d.same(0, i)) ++ans;
        ans *= n - ans;
        out << ans - m << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    C3Steps(in, out);
    return 0;
}

Measured memory_bytes: 3976