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;

typedef pair<long long int, pair<long long int, long long int>>one;

#define mod 1000000007LL
int main() {
	long long int V, E;
	cin >> V >> E;
	vector<vector<long long int>>path( V );
	for( size_t i = 0; i < E; i++ ) {
		long long int a, b;
		cin >> a >> b;
		a--; b--;
		path[a].push_back( b );
		path[b].push_back( a );
	}
	vector<bool>flag( V );
	vector<pair<long long int, long long int>>two;
	vector<long long int>len( V, LLONG_MAX / 6 );
	for( size_t i = 0; i < V; i++ ) {
		if( !flag[i] ) {
			flag[i] = true;
			len[i] = 0;
			pair<long long int, long long int>memo( 1, 0 );
			queue<pair<long long int, long long int>>que;
			que.push( make_pair( 0, i ) );
			while( que.size() ) {
				auto now = que.front(); que.pop();
				for( auto x : path[now.second] ) {
					if( flag[x] ) {
						if( len[x] % 2 == now.first % 2 ) {
							cout << -1 << endl;
							return 0;
						}
					} else {
						flag[x] = true;
						len[x] = now.first + 1;
						if( len[x] % 2 ) {
							memo.second++;
						} else {
							memo.first++;
						}
						que.push( make_pair( len[x], x ) );
					}
				}
			}
			two.push_back( memo );
		}
	}
	vector<long long int>sub( two.size() );
	long long int xx = 0;

	long long int base = 0;
	map<long long int, long long int>MLL;
	for( size_t i = 0; i < two.size(); i++ ) {
		MLL[abs( two[i].first - two[i].second )]++;
		base += min( two[i].first , two[i].second );
	}
	vector<long long int>dp( V / 2 + 1, -1 );
	dp[base] = 0;
	for( auto now : MLL ) {
		//cout << now.first << " " << now.second << endl;
		for( size_t i = 0; i < V / 2 + 1; i++ ) {
			if( dp[i] >= 0 ) {
				dp[i] = now.second;
			} else if( i < now.first || dp[i - now.first] <= 0 ) {
				dp[i] = -1;
			} else {
				dp[i] = dp[i - now.first] - 1;
			}
		}
	}
	for( long long int i = 0; i < V / 2 + 1; i++ ) {
		if( dp[i] != -1 ) {
			xx = max( i, xx );
		}
	}
	cout << xx*( V - xx ) - E << endl;
}