#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1012345678;

struct edge {
	int s, t;
};

pair<int, vector<edge> > reduce(int N, vector<edge> E) {
	int M = E.size();
	vector<int> deg(N);
	for (int i = 0; i < M; i++) {
		deg[E[i].s]++;
		deg[E[i].t]++;
	}
	vector<int> idx(N + 1, 0);
	for (int i = 0; i < N; i++) {
		idx[i + 1] = idx[i] + int(deg[i] >= 1);
	}
	for (int i = 0; i < M; i++) {
		E[i].s = idx[E[i].s];
		E[i].t = idx[E[i].t];
	}
	return make_pair(idx[N], E);
}

int solve(int N, const vector<edge>& E, int F) {
	int M = E.size();
	if (M == 0) {
		return 0;
	}
	if (F == 0) {
		return INF;
	}
	vector<int> deg(N);
	for (int i = 0; i < M; i++) {
		deg[E[i].s]++;
		deg[E[i].t]++;
	}
	int pos = max_element(deg.begin(), deg.end()) - deg.begin();
	if (deg[pos] * F < M) {
		return INF;
	}
	vector<edge> E1;
	vector<bool> adj(N, false);
	for (int i = 0; i < M; i++) {
		if (E[i].s != pos && E[i].t != pos) {
			E1.push_back(E[i]);
		} else {
			adj[E[i].s != pos ? E[i].s : E[i].t] = true;
		}
	}
	pair<int, vector<edge> > pack1 = reduce(N, E1);
	int ans = INF;
	int res1 = solve(pack1.first, pack1.second, F - 1);
	ans = min(ans, res1 + 1);
	if (deg[pos] <= F) {
		vector<edge> E2;
		for (int i = 0; i < M; i++) {
			if (!adj[E[i].s] && !adj[E[i].t]) {
				E2.push_back(E[i]);
			}
		}
		pair<int, vector<edge> > pack2 = reduce(N, E2);
		int res2 = solve(pack2.first, pack2.second, F - deg[pos]);
		ans = min(ans, res2 + deg[pos]);
	}
	return ans;
}

int main() {
	int N, M;
	cin >> N >> M;
	vector<edge> E(M);
	for (int i = 0; i < M; i++) {
		cin >> E[i].s >> E[i].t;
	}
	pair<int, vector<edge> > pack = reduce(N, E);
	N = pack.first;
	E = pack.second;
	int ans = solve(N, E, 28);
	cout << (ans != INF ? N - ans : -1) << endl;
	return 0;
}