#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>

auto& in = std::cin;
auto& out = std::cout;

int32_t N;
std::vector<int32_t> num;
std::vector<int32_t> type;//0,+1,-1
int32_t dp[2][500000];
int32_t func(int back, int i)
{
	if (i + 1 > N) { return 0; }

	auto& memo = dp[state.to_ulong()][i];
	if (memo != -1) { return memo; }

	int32_t res = 0;
	if (state[1] == 1 && state[2] == 0 && S[i + 1] == '1') {
		//一回使う
		std::bitset<3> new_state;
		new_state[0] = new_state[2] = 0;
		new_state[1] = 1;
		res = func(new_state, i + 1) + 1;
		//二回
		if (state[0] == 1) {
			new_state[0] = 1;
			new_state[1] = new_state[2] = 0;
			res = std::max(res, func(new_state, i + 1) + 2);
		}
	}

	//スルー
	std::bitset<3> new_state = state >> 1;
	new_state[2] = (S[i + 1] == '1');
	res = std::max(res, func(new_state, i + 1));
	return memo = res;
}
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;

	return 0;
}
#endif

#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>

auto& in = std::cin;
auto& out = std::cout;

int32_t N;
std::string S;
int32_t dp[1<<3][500000];
int32_t func(std::bitset<3> state, int i)
{
	if (i + 1 > N) { return 0; }

	auto& memo = dp[state.to_ulong()][i];
	if (memo != -1) { return memo; }

	int32_t res = 0;
	if (state[1] == 1 && state[2] == 0 && S[i+1]=='1') {
		//一回使う
		std::bitset<3> new_state;
		new_state[0] = new_state[2] = 0;
		new_state[1] = 1;
		res = func(new_state, i + 1)+1;
		//二回
		if (state[0] == 1) {
			new_state[0] = 1;
			new_state[1] = new_state[2] = 0;
			res = std::max(res, func(new_state, i + 1)+2);
		}
	}

	//スルー
	std::bitset<3> new_state = state>>1;
	new_state[2] = (S[i + 1] == '1');
	res = std::max(res,func(new_state, i + 1));
	return memo = res;
}

template<typename T, typename U>
std::enable_if_t<std::rank<T>::value == 0> fill_all(T& arr, const U& v) {
	arr = v;
}
template<typename ARR, typename U>
std::enable_if_t<std::rank<ARR>::value != 0> fill_all(ARR& arr, const U& v) {
	for (auto& i : arr) {
		fill_all(i, v);
	}
}
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N>>S;
	fill_all(dp, -1);
	std::bitset<3> new_state;
	new_state[0] = 0;
	new_state[1] = 0;
	new_state[2] = (S[0] == '1');
	out << func(new_state, 0) << endl;


	return 0;
}
#endif

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>

auto& in = std::cin;
auto& out = std::cout;

int32_t N;

#include <queue>
#include <vector>
#include <functional>
#include <utility>
#include <algorithm>
#include <iterator>

using COST_T = uint32_t;
constexpr uint32_t N_MAX = 110000;
constexpr COST_T INF = 1000000000;//std::numeric_limits<double>::infinity()

#if defined(_MSC_VER) && defined(_DEBUG)
//static_assert(false, "リリースでコンパイルしないと遅いよ！！");
#endif

struct edge {
	uint32_t to;
	COST_T cost;
	edge() {}
	edge(uint32_t to_, COST_T cost_=1)
		:to(to_), cost(cost_) {}
};
std::vector<edge> graph[N_MAX];

int64_t M;
int32_t V_type[100000];
void func(int32_t type, int i)
{
	if (V_type[i] == type) {
		return;
	}
	if (V_type[i] != 0) {
		std::cout << (int64_t(N)*int64_t(N - 1) / 2 - M) << std::endl; exit(0);
	}
	V_type[i] = type;
	for (auto& e : graph[i])
	{
		func(-type, e.to);
	}
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);
	in >> N>>M;
	for (int32_t i = 0; i < M; i++)
	{
		int a, b;
		in >> a >> b; --a; --b;
		graph[a].emplace_back(b);
		graph[b].emplace_back(a);
	}
	func(1,0);

	int64_t ans = 0;
	int64_t num1=0, num2=0;
	for (int32_t i = 0; i < N; i++)
	{
		if (V_type[i] == 1) {
			num1++;
		}
		else {
			num2++;
		}
		for (auto& e : graph[i])
		{
			if (V_type[i] != V_type[e.to]) {
				--ans;
			}
		}
	}
	ans += (-ans) / 2;
	ans += num1*num2;
	out << ans << endl;


	return 0;
}
#endif


Measured memory_bytes: 7296