/*input
10 39
7 2
7 1
5 6
5 8
9 10
2 8
8 7
3 10
10 1
8 10
2 3
7 4
3 9
4 10
3 4
6 1
6 7
9 5
9 7
6 9
9 4
4 6
7 5
8 3
2 5
9 2
10 7
8 6
8 9
7 3
5 3
4 5
6 3
2 10
5 10
4 2
6 2
8 4
10 6
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 705
#define bit(x,y) ((x>>y)&1LL)
#define loop(x) for(int xv=1; xv<=x; xv++)

#define what_is(x) cerr << #x << " is " << x << endl;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) {
	return os << '(' << a.first << ", " << a.second << ')';
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) {
	os << '[';
	for (unsigned int i = 0; i < a.size(); i++)
		os << a[i] << (i < a.size() - 1 ? ", " : "");
	os << ']';
	return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &a) {
	os << '{';
	for (typename set<T>::iterator it = a.begin(); it != a.end(); it++) {
		typename set<T>::iterator jt = it;
		os << *it << (++jt != a.end() ? ", " : "");
	}
	os << '}';
	return os;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, map<T1, T2> &a) {
	os << "{\n";
	for (typename map<T1, T2>::iterator it = a.begin(); it != a.end(); it++) {
		typename map<T1, T2>::iterator jt = it;
		os << "  " << it->first << ": " << it->second << (++jt != a.end() ? ",\n" : "\n");
	}
	os << '}';
	return os;
}

int n, m;
bool con[N][N];
vector<vector<int> > a(N);
int color[N];
vector<int> num;

void bfs(int root) {
	queue<int> q;
	q.push(root);
	color[root] = 0;
	int cnt[2]; memset(cnt, 0, sizeof(cnt));
	while (!q.empty()) {
		int u = q.front(); q.pop();
		cnt[color[u]]++;
		for (auto v : a[u]) {
			if (color[v] == -1) {
				color[v] = color[u] ^ 1;
				q.push(v);
			}
			else {
				if (color[u] != (color[v] ^ 1)) {
					cout << "-1" << endl;
					exit(0);
				}
			}
		}
	}
	num.push_back(abs(cnt[0] - cnt[1]));
}

bool dp[2][1405];
void DP() {
	memset(dp, 0, sizeof(dp));
	int off = 700;
	dp[0][off] = 1; int c = 0;
	for (auto it : num) {
		for (int i = 0; i < 1405; i++) {
			if (i + it >= 1405) break;
			if (dp[c][i] == 0) continue;
			dp[c ^ 1][i + it] = true;
		}
		it = -it;
		for (int i = -it; i < 1405; i++) {
			if (i + it >= 1405) break;
			if (dp[c][i] == 0) continue;
			dp[c ^ 1][i + it] = true;
		}
		for (int i = 0; i < 1405; i++)
			dp[c][i] = false;
		c ^= 1;
	}
	int diff = 1e9;
	for (int i = 0; i < 1405; i++) {
		if (dp[c][i])
			diff = min(diff, abs(i - 700));
	}
	int big = (n + diff) / 2;
	int small = n - big;
	cout << small*(small - 1) / 2 + big*(big - 1) / 2 << endl;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		con[u][v] = con[v][u] = true;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (!con[i][j]) {
				a[i].push_back(j);
				a[j].push_back(i);
			}
		}
	}
	memset(color, -1, sizeof(color));
	for (int i = 1; i <= n; i++) {
		if (color[i] == -1) {
			bfs(i);
		}
	}
	DP();
}

Measured memory_bytes: 6016