#include <bits/stdc++.h>
using namespace std;
// #include "../head.cpp"

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a), i##_len = (b); i < i##_len; ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define _repr(i, n) repri(i, n, 0)
/* loop in [n,m] step -1 */
#define repri(i, a, b) for(int i = int(a), i##_len = (b); i >= i##_len; --i)
/* loop in [n,0] step -1 or [n,m] step -1 */
#define repr(...) _overload3(__VA_ARGS__, repri, _repr, )(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << ": " << (x) << '\n'
typedef long long lint;
#define int lint
const int INF = (int)(1 << 30) - 1;
int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const lint LINF = (lint)(1LL << 62) - 1;
typedef vector<int> vint;
typedef pair<int, int> pint;

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
        cerr << fixed << setprecision(20);
    }
} iosetup;

#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define SZ(x) ((int)(x).size())

template <typename F>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
    [[nodiscard]]
#elif defined(__GNUC__) && __GNUC_PREREQ(3, 4)
__attribute__((warn_unused_result))
#endif  // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
    FixPoint :
    F { public : explicit constexpr FixPoint(F &&f) noexcept :
            F(std::forward<F>(f)) {}

        template <typename... Args> constexpr decltype(auto)
        operator()(Args &&... args) const {
            return F::operator()(*this, std::forward<Args>(args)...);
}
}
;  // class FixPoint

template <typename F>
static inline constexpr decltype(auto) makeFixPoint(F &&f) noexcept {
    return FixPoint<F>{std::forward<F>(f)};
}

/* range macro. usage: for(int i:range(n)) */
class range {
   private:
    struct I {
        int x;
        int operator*() { return x; }
        bool operator!=(I &lhs) { return x < lhs.x; }
        void operator++() { ++x; }
    };
    I i, n;

   public:
    range(int n) : i({0}), n({n}) {}
    range(int i, int n) : i({i}), n({n}) {}
    I &begin() { return i; }
    I &end() { return n; }
};

/* keep a max,min */
template <class T>
bool chmax(T &a, const T &b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}

template <class T>
bool chmin(T &a, const T &b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}

/* input,output operator for pair and vector */
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    for(int i = 0; i < (int)v.size(); i++) {
        os << v[i] << (i + 1 != v.size() ? ", " : "");
    }
    os << "]";
    return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for(T &in : v) is >> in;
    return is;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp) {
    for(auto x = mp.begin(); x != mp.end(); ++x) {
        os << x->first << ": " << x->second
           << (x != prev(mp.end()) ? "\n" : "");
    }
    return os;
}

/* initialize vector. usage: auto v = male_v<int>(N,0); */
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

/* fill vector. usage: fill_v(v,0); */
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
    t = v;
}

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
    for(auto &e : t) fill_v(e, v);
}

/* sum */
template <typename T>
T sum(vector<T> &v) {
    T ret = 0;
    for(T x : v) {
        ret += x;
    }
    return ret;
}
template <typename T>
auto sum(const T &a) {
    return a;
}
template <typename T, typename... A>
auto sum(const T &first, const A &... rest) {
    return sum(first) + sum(rest...);
}

/* mod */
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while(n > 0) {
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while(b) {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if(u < 0) u += m;
    return u;
}

/* print */
template <typename T>
void print(const T &first) {
    cout << first << endl;
}
template <typename T, typename... A>
void print(const T &first, const A &... rest) {
    cout << first << " ";
    print(rest...);
}
template <typename... A>
void print(const A &... rest) {
    print(rest...);
}

/* Graph template */
template <typename T>
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template <typename T>
using Matrix = vector<vector<T>>;

// v: 現在探索中の頂点、p: v の親 (v が根のときは -1)
void dfs(const UnWeightedGraph &G, int v, int p) {
    for(auto nv : G[v]) {
        if(nv == p) continue;  // nv が親 p だったらダメ
        dfs(G, nv, v);         // v は新たに nv の親になります
    }
}

// d: 頂点 v の深さ
vector<int> depth;
void dfs(const UnWeightedGraph &G, int v, int p, int d) {
    depth[v] = d;
    for(auto nv : G[v]) {
        if(nv == p) continue;  // nv が親 p だったらダメ
        dfs(G, nv, v, d + 1);  // d を 1 増やして子ノードへ
    }
}

int BipartiteGraph(const UnWeightedGraph &g) {
    int n = g.size();
    vector<int> color(n, -1);
    int white_cnt = 0;
    auto t = makeFixPoint([&](auto dfs, int v, int prev, int c) -> int {
        color[v] = c;
        if(c == 1) white_cnt++;
        for(auto nv : g[v]) {
            if(nv == prev) continue;

            if(color[nv] == -1) {
                if(!dfs(nv, v, 1 - c)) return false;
            } else if(color[nv] != 1 - c) {
                return false;
            }
        }
        return true;
    })(0, -1, 0);
    if(!t) return -1;
    return white_cnt;
}

signed main() {
    /* https://atcoder.jp/contests/abc126/tasks/abc126_d */
    int N, M;
    cin >> N >> M;
    UnWeightedGraph G(N);
    for(int i : range(M)) {
        int A, B;
        cin >> A >> B;
        A--, B--;
        G[A].emplace_back(B);
        G[B].emplace_back(A);
    }
    auto t = BipartiteGraph(G);
    if(t == -1) {
        print(N * (N - 1) / 2 - M);
    } else {
        print(t * (N - t) - M);
    }
}

Measured memory_bytes: 7552