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;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

bool flag = true;
bitset<100010> bit;
int black,white,col[100010];
vector<int> G[100010];
vector<P> vec;

void dfs(int v,int c){
	col[v] = c;
	(c ? black : white) += 1;
	for(int to : G[v]){
		if(col[to] == -1){
			dfs(to,(c + 1) % 2);
		}else if(col[to] != (c + 1) % 2){
			flag = false;
			return;
		}
	}
}

signed main(){
	int n,m,ma = 0;
	cin >> n >> m;
	for(int i = 0;i < m;i++){
		int a,b;
		cin >> a >> b; a--;b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	for(int i = 0;i < n;i++) col[i] = -1;
	for(int i = 0;i < n;i++){
		if(col[i] == -1){
			black = 0;
			white = 0;
			dfs(i,0);
			if(!flag){
				cout << -1 << endl;
				return 0;
			}
			vec.pb(P(black,white));
		}
	}
	bit.set(0);
	for(P p : vec){
		bit = (bit << p.first) | (bit << p.second);
	}
	for(int i = 0;i < 100005;i++){
		if(bit[i]) chmax(ma,i * (n - i));
	}
	cout << ma - m << endl;
}