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 100010
#define int long long
using namespace std;
typedef pair<int,int> P;
int n,m;
vector<int> G[N];
int flag;
int col[N];
 
P cnt;
void dfs(int pos,int c){
  if(col[pos]!=-1 && c!=col[pos]) flag = 1;
  if(col[pos]!=-1 && c==col[pos]) return; 
  if(flag) return;
  c? cnt.first++:cnt.second++;
  col[pos] = c;
  for(int nx:G[pos])dfs(nx,!c);
}
 
map<int,int> A;

int calc(int d){
  int a = (n-d)/2;
  int b = n - a;
  return a*b;
}

int dp[N] = {};
int DP(){
  int sum = 0;
  for(P a:A) sum+=a.first*a.second;

  for(P a:A){
    dp[0] = 1;
    for(int j=0;j<N;j++)if(dp[j]) dp[j] = a.second+1;
    for(int j=0;j<N;j++){
      if(j+a.first>=N)break;
      if(dp[j] == 0)continue;
      dp[j+a.first] = max(dp[j+a.first],dp[j] - 1);
    }
  }
  
  int res = 0;
  for(int i=0;i<N;i++)
    if(dp[i]>0) res = max(res,calc(abs(i-(sum-i))));
  return res;
}

signed main(){
  cin>>n>>m;
  for(int i=0,a,b;i<m;i++){
    cin>>a>>b;a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
 
  memset(col,-1,sizeof(col));
  for(int i=0;i<n;i++) {
    if(col[i]!=-1)continue;
    cnt = P(0,0); 
    dfs(i,0);
    A[abs(cnt.first-cnt.second)]++;
  }

  if(flag) cout<<"-1"<<endl,exit(0);
  cout<<DP()-m<<endl;
  return 0;
}