#include <bits/stdc++.h>
// #include <atcoder/maxflow> // #
using namespace std;
// // MaxFlow
// namespace atcoder {

// namespace internal {

// template <class T> struct simple_queue {
//     std::vector<T> payload;
//     int pos = 0;
//     void reserve(int n) { payload.reserve(n); }
//     int size() const { return int(payload.size()) - pos; }
//     bool empty() const { return pos == int(payload.size()); }
//     void push(const T& t) { payload.push_back(t); }
//     T& front() { return payload[pos]; }
//     void clear() {
//         payload.clear();
//         pos = 0;
//     }
//     void pop() { pos++; }
// };

// }  // namespace internal

// template <class Cap> struct mf_graph {
//   public:
//     mf_graph() : _n(0) {}
//     mf_graph(int n) : _n(n), g(n) {}

//     int add_edge(int from, int to, Cap cap) {
//         assert(0 <= from && from < _n);
//         assert(0 <= to && to < _n);
//         assert(0 <= cap);
//         int m = int(pos.size());
//         pos.push_back({from, int(g[from].size())});
//         g[from].push_back(_edge{to, int(g[to].size()), cap});
//         g[to].push_back(_edge{from, int(g[from].size()) - 1, 0});
//         return m;
//     }

//     struct edge {
//         int from, to;
//         Cap cap, flow;
//     };

//     edge get_edge(int i) {
//         int m = int(pos.size());
//         assert(0 <= i && i < m);
//         auto _e = g[pos[i].first][pos[i].second];
//         auto _re = g[_e.to][_e.rev];
//         return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
//     }
//     std::vector<edge> edges() {
//         int m = int(pos.size());
//         std::vector<edge> result;
//         for (int i = 0; i < m; i++) {
//             result.push_back(get_edge(i));
//         }
//         return result;
//     }
//     void change_edge(int i, Cap new_cap, Cap new_flow) {
//         int m = int(pos.size());
//         assert(0 <= i && i < m);
//         assert(0 <= new_flow && new_flow <= new_cap);
//         auto& _e = g[pos[i].first][pos[i].second];
//         auto& _re = g[_e.to][_e.rev];
//         _e.cap = new_cap - new_flow;
//         _re.cap = new_flow;
//     }

//     Cap flow(int s, int t) {
//         return flow(s, t, std::numeric_limits<Cap>::max());
//     }
//     Cap flow(int s, int t, Cap flow_limit) {
//         assert(0 <= s && s < _n);
//         assert(0 <= t && t < _n);

//         std::vector<int> level(_n), iter(_n);
//         internal::simple_queue<int> que;

//         auto bfs = [&]() {
//             std::fill(level.begin(), level.end(), -1);
//             level[s] = 0;
//             que.clear();
//             que.push(s);
//             while (!que.empty()) {
//                 int v = que.front();
//                 que.pop();
//                 for (auto e : g[v]) {
//                     if (e.cap == 0 || level[e.to] >= 0) continue;
//                     level[e.to] = level[v] + 1;
//                     if (e.to == t) return;
//                     que.push(e.to);
//                 }
//             }
//         };
//         auto dfs = [&](auto self, int v, Cap up) {
//             if (v == s) return up;
//             Cap res = 0;
//             int level_v = level[v];
//             for (int& i = iter[v]; i < int(g[v].size()); i++) {
//                 _edge& e = g[v][i];
//                 if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
//                 Cap d =
//                     self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
//                 if (d <= 0) continue;
//                 g[v][i].cap += d;
//                 g[e.to][e.rev].cap -= d;
//                 res += d;
//                 if (res == up) break;
//             }
//             return res;
//         };

//         Cap flow = 0;
//         while (flow < flow_limit) {
//             bfs();
//             if (level[t] == -1) break;
//             std::fill(iter.begin(), iter.end(), 0);
//             while (flow < flow_limit) {
//                 Cap f = dfs(dfs, t, flow_limit - flow);
//                 if (!f) break;
//                 flow += f;
//             }
//         }
//         return flow;
//     }

//     std::vector<bool> min_cut(int s) {
//         std::vector<bool> visited(_n);
//         internal::simple_queue<int> que;
//         que.push(s);
//         while (!que.empty()) {
//             int p = que.front();
//             que.pop();
//             visited[p] = true;
//             for (auto e : g[p]) {
//                 if (e.cap && !visited[e.to]) {
//                     visited[e.to] = true;
//                     que.push(e.to);
//                 }
//             }
//         }
//         return visited;
//     }

//   private:
//     int _n;
//     struct _edge {
//         int to, rev;
//         Cap cap;
//     };
//     std::vector<std::pair<int, int>> pos;
//     std::vector<std::vector<_edge>> g;
// };

// }  // namespace atcoder

using namespace std;
// using namespace atcoder; // #
#define rep(CNT, GOAL) for (int CNT = 0; CNT < (int)(GOAL); CNT++)
#define rep2(CNT, START, GOAL) for (int CNT = (int)(START); CNT < (int)(GOAL); CNT++)

struct Graph{
	int V; // 0-ind
	vector<vector<int>> adj;
	vector<bool> r; // reached
	vector<int> dis; // struct内に置く
	Graph(int _V) {
		V = _V;
		adj = vector<vector<int>>(V);
		r = vector<bool>(V);
		dis = vector<int>(V);
	}
	void add_edge(int u, int v) { // u-v (indirected)
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	// 連結成分ごとに，番号の最も若い頂点からの距離を求めるBFS(struct内に置く)
	void bfs_dis(int s) {
		dis[s] = 0; // 値と到達フラグを分ける
		queue<int> q; q.push(s); r[s] = true;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int v : adj[u]) {
				if (r[v]) continue;
				q.push(v); r[v] = true;
				dis[v] = dis[u] + 1;
			}
		}
	}
	void bfs_dis() {
		r = vector<bool>(V, false); // 到達フラグ初期化
		dis = vector<int>(V, -1); // 距離初期化
		for (int s = 0; s < V; s++) {
			if (r[s]) continue;
			bfs_dis(s); // sを始点としてBFS
		}
	}
	bool is_bipartite(int s) {
		queue<int> q; q.push(s); r[s] = true;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int v : adj[u]) {
				if ((dis[v] - dis[u]) % 2 == 0) return false;
				if (!r[v]) {
					q.push(v); r[v] = true;
				}
			}
		}
		return true;
	}
	bool is_bipartite() {
		bfs_dis();
		r = vector<bool>(V, false);
		for (int s = 0; s < V; s++) {
			if (r[s]) continue;
			if (!is_bipartite(s)) return false;
		}
		return true;
	}
	vector<vector<int>> parts() {
		assert(is_bipartite());
		vector<vector<int>> p(2);
		for (int i = 0; i < V; i++) {
			p[dis[i] % 2].push_back(i);
		}
		return p;
	}
	void show() {
		for (int i = 0; i < V; i++) {
			cout << i << ": { ";
			for (int j : adj[i]) cout << j << ", ";
			cout << "}" << endl;
		}
	}
	template <typename T> // #defineに移す
	void show(vector<T> &val) {
		cout << "{ ";
		for (int i = 0; i < val.size(); i++) cout << val[i] << ", ";
		cout << "}" << endl;
	}
};

int main() {
	// 0-ind
	long long N; int M; cin >> N >> M;
	Graph g(N);
	rep(i, M) {
		int A, B; cin >> A >> B;
		g.add_edge(--A, --B);
	}
	// g.show();
	// cout << g.is_bipartite() << endl;
	if (g.is_bipartite()) {
		auto p = g.parts();
		// g.show(p[0]); g.show(p[1]);
		long long B = p[0].size(), W = p[1].size();
		long long ans = B * W - M;
		cout << ans << endl;
	} else {
		long long ans = N * (N - 1) / 2 - M;
		cout << ans << endl;
	}
}

Measured memory_bytes: 9724