import std.stdio, std.algorithm, std.range, std.conv, std.string, std.math, std.container, std.typecons;
import core.stdc.stdio;
// foreach, foreach_reverse, writeln

void main() {
	int n, m;
	scanf("%d%d", &n, &m);
	bool[][] g = new bool[][](n,n);
	foreach (i; 0..n) foreach (j; 0..n) {
		if (i != j) g[i][j] = true;
	}
	foreach (i; 0..m) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		g[a][b] = g[b][a] = false;
	}
	//if (n*(n-1)/2 == m) {
	//	int s = n/2, t = n-s;
	//	m -= s*t;
	//	writeln(m);
	//	return;
	//}

	int[] color = new int[n];
	color[] = -1;

	int[] cnt;
	bool dfs(int v, int c) {
		if (color[v] != -1) {
			if (color[v] != c) return false;
			return true;
		}
		color[v] = c;
		cnt[c]++;
		foreach (u; 0..n) {
			if (g[v][u]) {
				if (!dfs(u,c^1)) return false;
			}
		}
		return true;
	}
	int l = 0;
	int[] a;
	foreach (i; 0..n) {
		if (color[i] != -1) continue;
		cnt = new int[2];
		if (!dfs(i,0)) {
			writeln(-1);
			return;
		}
		cnt.sort;
		l += cnt[0];
		if (cnt[0] < cnt[1]) a ~= cnt[1]-cnt[0];
	}
	bool[] dp = new bool[n+1];
	dp[0] = true;
	foreach (x; a) {
		foreach_reverse (i; 0..n-x+1) {
			dp[i+x] |= dp[i];
		}
	}
	int ans = m;
	int im = n*(n-1)/2-m;
	foreach (i; 0..n+1) {
		if (!dp[i]) continue;
		int s = l+i, t = n-s;
		ans = min(ans, m-(s*t-im));
	}
	writeln(ans);
}