# AtCoder Regular 099E: Independence

This problem is one that requires thoughts on complement graph. The official editorial has done a pretty good job in explanation.

Step: Convert into complement graph -> Find characteristic of this graph -> Bipartite graph -> Convert back -> Find minimum roads -> DP

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1005;
int N,M;
bool conn[maxn][maxn];
int col[maxn],cnt[maxn],f[maxn][maxn];
bool dfs(int u,int c){
cnt[c]++;
col[u] = c;
for(int i = 1; i <= N; i++){
if(!conn[u][i]){
if(!col[i]){
if(!dfs(i,3 - c)) return 0;
}
else if(col[i] == c) return 0;
}
}
return 1;
}
int main(){
FAST_IO
cin>>N>>M;
for(int i = 1; i <= M; i++){
int a,b;
cin>>a>>b;
conn[a][b] = conn[b][a] = 1;
}
for(int i = 1; i <= N; i++) conn[i][i] = 1;
f[0][0] = 1;
int now = 0;
for(int i = 1; i <= N; i++){
if(!col[i]){
now++;
cnt[1] = cnt[2] = 0;
if(!dfs(i,1)){
cout<<-1<<endl;
return 0;
}
for(int j = 0; j <= N; j++) if(f[now - 1][j]) f[now][j + cnt[1]] = f[now][j + cnt[2]] = 1;
}
}
int ans = INT_MAX;
for(int i = 0; i <= N; i++){
if(f[now][i]){
ans = min(ans, i * (i - 1) / 2 + (N - i) * (N - i - 1) / 2);
}
}
cout<<ans<<endl;
return 0;
}