#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template <class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);

	auto solve = [&]() {
		int n, m;
		cin >> n >> m;

		vector adj(n, vector<int>(n));
		while (m--) {
			int u, v;
			cin >> u >> v;
			u--, v--;
			adj[u][v] = adj[v][u] = true;
		}

		vector<int> col(n, -1);
		vector<int> dp(n + 1);
		dp[0] = true;

		for (int i = 0; i < n; i++) {
			if (col[i] != -1) {
				continue;
			}
			vector<int> q{i};
			col[i] = 0;
			for (int j = 0; j < int(q.size()); j++) {
				int u = q[j];
				for (int v = 0; v < n; v++) {
					if (u == v || adj[u][v]) {
						continue;
					}
					if (col[v] == -1) {
						q.push_back(v);
						col[v] = col[u] ^ 1;
					} else if (col[u] == col[v]) {
						cout << "-1\n";
						return;
					}
				}
			}
			int c0 = count_if(q.begin(), q.end(), [&](auto u) {
					return col[u] == 0; });
			int c1 = int(q.size()) - c0;
			for (int i = n; i >= 0; i--) {
				if (i >= c0) {
					dp[i] |= dp[i - c0];
				}
				if (i >= c1) {
					dp[i] |= dp[i - c1];
				}
			}
		}

		for (int i = n / 2; i >= 0; i--) {
			if (dp[i]) {
				cout << n - 2 * i << '\n';
				return;
			}
		}
	};

	solve();
}