#include <cstdio>
#include <map>
using namespace std;
typedef long long ll;
int n;
bool edge[35][35];
int op[35], res[35];
map < ll, int > cnt[2];
int min(int a, int b) {
	return a < b ? a : b;
}
void dfs(int cur, int r, int k) {
	if (cur == r) {
		int num = 0;
		for (int i = 0; i < n; i++) {
			num += op[i];
			res[i] = 0;
			for (int j = 0; j < n; j++) {
				if (edge[i][j]) {
					res[i] ^= op[j];
				}
			}
		}
		ll s = 0;
		for (int i = 0; i < n; i++) {
			s += (1ll * res[i]) << i;
		}
		if (cnt[k].count(s) == 0) {
			cnt[k][s] = num;
		} else {
			cnt[k][s] = min(cnt[k][s], num);
		}
	} else {
		op[cur] = 0;
		dfs(cur + 1, r, k);
		op[cur] = 1;
		dfs(cur + 1, r, k);
	}
}
int main() {
	int m;
	scanf("%d %d", &n, &m);
	for (int u, v, i = 0; i < m; i++) {
		scanf("%d %d", &u, &v);
		u--;
		v--;
		edge[u][v] = edge[v][u] = true;
	}
	for (int i = 0; i < n; i++) {
		edge[i][i] = true;
	}
	dfs(0, n / 2, 0);
	for (int i = 0; i < n / 2; i++) {
		op[i] = 0;
	}
	dfs(n / 2, n, 1);
	ll ans = 40;
	for (pair < ll, int > i : cnt[0]) {
		if (cnt[1].count(((1 << n) - 1) ^ i.first) != 0) {
			ans = min(ans, i.second + cnt[1][((1 << n) - 1) ^ i.first]);
		}
	}
	printf("%lld", ans);
	return 0;
}