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;
vector<vector<int>> edge;
vector<int> vertex;

void color(int v,bool c){
  if(vertex[v]!=-1){
    if(vertex[v]!=c) throw "nonbin";
    return;
  }
  vertex[v]=c;
  for(int i=0;i<edge[v].size();i++){
    color(edge[v][i],!c);
  }
  return;
}

void dfs(int v,vector<int> &used,vector<int>& con){
  if(used[v]) return;
  used[v]=true;
  con.push_back(v);
  for(int i=0;i<edge[v].size();i++){
    dfs(edge[v][i],used,con);
  }
  return;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,e;
  cin>>n>>e;
  edge.resize(n);
  for(int i=0;i<e;i++){
    int a,b;
    cin>>a>>b;
    a--,b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  vector<vector<int>> chunk;
  vector<int> used(n);
  for(int i=0;i<n;i++){
    if(!used[i]){
      vector<int> con;
      dfs(i,used,con);
      chunk.push_back(con);
    }
  }
  
  vertex.resize(n,-1);
  vector<int> dis;
  int smsum=0;
  for(int i=0;i<chunk.size();i++){
    try{
      color(chunk[i][0],0);
    }catch(const char* ex){
      cout<<-1<<endl;
      return 0;
    }
    int cnt1=0;
    for(int j=0;j<chunk[i].size();j++){
      cnt1+=vertex[chunk[i][j]];
    }
    smsum+=min(cnt1,int(chunk[i].size())-cnt1);
    dis.push_back(abs(cnt1-(int(chunk[i].size())-cnt1)));
  }
  map<int,int> m;
  for(int i=0;i<dis.size();i++){
    if(!m.count(dis[i])){
      m[dis[i]]=1;
    }
    else m[dis[i]]++;

  }
  
  vector<vector<int>> s;
  for(auto it=m.begin();it!=m.end();it++){
    vector<int> ss;
    int val=it->first;
    int time=it->second;

    for(int i=0;i<=time;i++){
      ss.push_back(val*i);
    }
    s.push_back(ss);
  }

  set<int> ob(s[0].begin(),s[0].end());

  for(int i=1;i<s.size();i++){

    set<int> nexob;
    for(auto v:s[i]){
      for(auto vv:ob){
	nexob.insert(v+vv);
      }
    }
    ob=nexob;
  }


  
  long long int res=0;
  for(auto v:ob){
    long long int b=(smsum+v);
    long long int a=(n-smsum-v);
    res=max(res,a*b-e);
  }
  cout<<res<<endl;  
  
  return 0;
}