Submission #2545137

---

Source Code Expand

#include <queue>
#include <vector>
#include <iostream>
using namespace std;
int n, m, col[100009]; vector<int> g[100009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b; --a, --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	fill(col, col + n, -1); col[0] = 0;
	queue<int> que; que.push(0);
	bool f = true; int sum = 0;
	while (!que.empty()) {
		int u = que.front(); que.pop();
		for (int i : g[u]) {
			if (col[i] == col[u]) f = false;
			if (col[i] == -1) {
				col[i] = col[u] ^ 1;
				sum += col[i];
				que.push(i);
			}
		}
	}
	cout << (f ? 1LL * sum * (n - sum) : 1LL * n * (n - 1) / 2) - m << '\n';
	return 0;
}

Submission Info

Judge Result