Problem: Example

Input

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


Output

11

Solution (in CPP):

Solution:
#include<iostream>
#include<vector>
#include<bitset>
#include<utility>

using namespace std;

vector<int> G[123456];
int c[123456];

pair<int,int> color(int v,int cc){
  if(c[v]){
    if(cc!=c[v])throw 0;
    return make_pair(0,0);
  }else{
    c[v]=cc;
    pair<int,int> p(cc==1,cc==-1);
    for(auto e:G[v]){
      auto r=color(e,cc*-1);
      p.first+=r.first;
      p.second+=r.second;
    }
    return p;
  }
}

int main(){
  int V,E;
  cin>>V>>E;
  for(int i=0;i<E;i++){
    int a,b;
    cin>>a>>b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  bitset<123456> dp(1);
  try{
    for(int i=1;i<=V;i++){
      if(!c[i]){
	auto r=color(i,1);
	dp=dp<<r.first|dp<<r.second;
      }
    }
    long long ans=0;
    for(int i=0;i<=V;i++){
      if(dp[i]){
	ans=max(ans,1LL*i*(V-i)-E);
      }
    }
    cout<<ans<<endl;
  }catch(...){
    cout<<-1<<endl;
  }
}