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>
#define N 100005
using namespace std;
typedef pair<int,int> P;
typedef long long ll;

int n,e,s[2];
vector<int> G[N];
int color[N];

void dfs(int x,int c){
  
  color[x]=c;
  s[c]++;
  
  for(int i=0;i<G[x].size();i++){

    int nx=G[x][i];
    if(color[nx]!=-1){
      
      if(color[x]==color[nx]){
	cout<<-1<<endl;
	exit(0);
      }
      
    }else dfs(nx,!c);

  }
  
}

ll dp[N];
map<int,int> S;

int main(){
    
  cin>>n>>e;
 
  for(int i=0;i<e;i++){
    
    int a,b;
    cin>>a>>b;
    
    G[a-1].push_back(b-1);
    G[b-1].push_back(a-1);
  }

  memset(color,-1,sizeof(color));

  ll sum=0,sum2=0;
  
  for(int i=0;i<n;i++)
    if(color[i]==-1){
      s[0]=s[1]=0;
      dfs(i,0);
      if(s[0]>s[1]) swap(s[0],s[1]);
      sum+=s[1];
      S[abs(s[0]-s[1])]++;
      sum2+=abs(s[0]-s[1]);
    }

  map<int,int>::iterator ite=S.begin();
  
  memset(dp,-1,sizeof(dp));
  
  while(ite!=S.end()){
    
    dp[0]=0;
    
    ll x=(*ite).first;
    
    for(int i=0;i<n;i++)
      if(dp[i]>=0) dp[i]=(*ite).second;
    
    for(int i=0;i<n;i++)

      if(dp[i]>0&&i+x<=n) dp[i+x]=max(dp[i+x],dp[i]-1);

    ite++;
  }
  
  ll ans=0;
  
  for(ll i=0;i<=n;i++)
    if(dp[i]>=0) ans=max(ans,(sum-i)*(sum-(sum2-i)));
  
  cout<<ans-e<<endl;
  
  return 0;
}