Problem: Example

Input

8 5
1 2
6 5
6 4
1 3
4 7


Output

11

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

bool dfs(const vvi& g,int u,int c,vi& color,int& x,int& y)
{
	if(color[u]!=-1)
		return color[u]==c;
	color[u]=c;
	(c==0?x:y)++;
	for(int v:g[u])
		if(!dfs(g,v,!c,color,x,y))
			return false;
	return true;
}

ll solve(const vvi& g)
{
	int n=g.size();
	
	vector<pii> ps;
	{
		vi color(n,-1);
		rep(i,n) if(color[i]==-1){
			int x=0,y=0;
			if(!dfs(g,i,0,color,x,y))
				return -1;
			ps.emplace_back(x,y);
		}
	}
	
	bitset<100001> b;
	b[0]=1;
	for(pii p:ps)
		b=(b<<p.first)|(b<<p.second);
	
	ll mx=0;
	rep(i,b.size()) if(b[i])
		mx=max(mx,ll(i)*(n-i));
	
	int e=0;
	rep(i,n) e+=g[i].size();
	
	return mx-e/2;
}

int main()
{
	for(int n,m;cin>>n>>m && n|m;){
		vvi g(n);
		for(int i=0;i<m;i++){
			int u,v; cin>>u>>v; u--,v--;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		cout<<solve(g)<<endl;
	}
}