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<algorithm>
#include<iomanip>
#include<queue>
#include<map>
#include<bitset>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef pair<int,int> pint;
typedef long long ll;
const int inf   = 1<<30;
const ll  longinf = 1LL<<60;
const int mod=1e9+7;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

vector<int> v[100001];
int cnt,used[100001];
bool nibu;

void dfs(int x,int flag){
  if(flag==1)cnt++;
  else cnt--;
  rep(i,v[x].size()){
    if(used[v[x][i]]==flag){
      nibu=false;
      return;
      }
    if(used[v[x][i]]==-1){
      used[v[x][i]]=1-flag;
      dfs(v[x][i],1-flag);
      }
    }
  }


int main(){
  int n,m;
  cin>>n>>m;
  rep(i,m){
    int x,y;
    cin>>x>>y;
    x--;y--;
    v[x].push_back(y);
    v[y].push_back(x);
    }
  rep(i,n)used[i]=-1;
  int num=0;
  vector<int> e;
  rep(i,n){
    if(used[i]==-1){
      used[i]=1;
      cnt=0;
      nibu=true;
      dfs(i,1);
      if(!nibu){cout<<-1<<endl;return 0;}
      if(abs(cnt)>1)e.push_back(abs(cnt));
      if(abs(cnt)==1)num++;
      }
    }
  bitset<2000001> b;
  b=1;
  b=b<<100000;
  rep(i,e.size())b=(b<<e[i])|(b>>e[i]);
  rep(i,100001){
    if(b[100000+i]){
      ll ma,mi,d;
      if(i>num)d=ll(i-num);
      else d=(ll)(num-i)%2;
      ma=(ll)(d+n)/2;
      mi=(ll)(n-d)/2;
      cout<<ma*mi-m<<endl;
      return 0;
      }
    }
  return 0;    
  }