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;

int V,E;
vector<int> G[100005];
vector<int> A,B;
bool flg=false;
bool visited[100005];
int depth[100005];
int cnt[2];

void dfs(int pos,int d){
  
  if(visited[pos]){
    if(depth[pos]!=d)flg=true;
    return;
  }
  
  visited[pos]=true;
  depth[pos]=d;
  cnt[d]++;
  
  for(int i=0;i<(int)G[pos].size();i++){
    int to=G[pos][i];
    dfs(to,1-d);
  }
}

typedef long long ll;
int dp[2][100005];

int cc[100005];

ll solve(){
  if(flg)return -1;
  
  map<int,int> mp;
  int sum=0;
  for(int i=0;i<(int)A.size();i++){
    int mn=min(A[i],B[i]);
    int mx=max(A[i],B[i]);
    sum+=mn;
    mp[mx-mn]++;
  }
  
  dp[0][0]=1;
  dp[1][0]=1;
  
  map<int,int>::iterator it;

  int ai=0,bi=1;
  for(it=mp.begin();it!=mp.end();it++){
    swap(ai,bi);
    
    int a=it->first,b=it->second;
    if(a==0)continue;
    
    
    memset(cc,0,sizeof(cc));    
    for(int i=0;i<=V;i++){
      int k=0;
      if(i-a>=0)k+=cc[i-a];
      if(i-a*b-a>=0)k-=cc[i-a*b-a];
      if(k>0 || dp[bi][i]==1)dp[ai][i]=1;
      
      cc[i]=dp[bi][i];
      if(i-a>=0)cc[i]+=cc[i-a];
    }
  }
  ll ans=0;
  for(int i=0;i<=V;i++){
    if(dp[ai][i]>0 || dp[bi][i]>0){
      ans=max(ans, (ll)(i+sum)*(ll)(V-i-sum) );
    }
  }
  return ans-(ll)E;
}

int main(){
  scanf("%d %d",&V,&E);
  for(int i=0;i<E;i++){
    int a,b;
    scanf("%d %d",&a,&b);
    a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);    
  }
  for(int i=0;i<V;i++){
    if(visited[i])continue;
    cnt[0]=cnt[1]=0;
    dfs(i,0);
    A.push_back(cnt[0]);
    B.push_back(cnt[1]);
  }
  cout<<solve()<<endl;
  return 0;
}