Submission #1833882

---

Source Code Expand

#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
using namespace std;
typedef long long ll;
typedef vector<int> vertex;
typedef vector<vertex> graph;
 
ll n, m;
graph g;
 
void add_edge(int a, int b){
	g[a].push_back(b);
	g[b].push_back(a);
}
 
int used[100000];
 
ll cnt(ll u, ll d, bool &tr){
	if(used[u]){
		if(used[u]!=2-d) tr = true;
		return 0;
	}
	used[u] = 2-d;
	ll res = 0;
	if(d==0) res++;
	for(int v: g[u]){
		res += cnt(v, !d, tr);
	}
	return res;
}
 
int main(){
	cin>>n>>m;
	g = graph(n);
	rep(i, m){
		int a, b;
		cin>>a>>b;
		a--; b--;
		add_edge(a, b);
	}
	bool tr = false;
	ll t = cnt(0, 0, tr);
	if(tr) cout<<n*(n-1)/2-m<<endl;
	else cout<<t*(n-t)-m<<endl;
	return 0;
}

Submission Info

Judge Result