#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 36
#define INF 200000000
int G[MAXN][MAXN], L[MAXN][MAXN];
int B[MAXN], S[MAXN];
int N, M, A;
void Print() {
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=N; j++)
			printf("%d ", G[i][j]);
		printf("\n");
	}
	printf("\n");
}
void Exchange(int i, int j) {
	for(int l=1; l<=N; l++)
		swap(L[i][l], L[j][l]);
	swap(B[i], B[j]);
}
void Xor(int i, int j) {
	for(int l=1; l<=N; l++)
		L[i][l] ^= L[j][l];
	B[i] ^= B[j];
}
void DFS(int k, int c) {
	if(c>=A)
		return;
	if(k == 0) {
		if(c < A)
			A = c;
		return;
	}
	if(L[k][k]) {
		bool t = B[k];
		for(int i=k+1; i<=N; i++)
			if(L[k][i])
				t ^= S[i];
		S[k] = t;
		if(S[k])
			DFS(k-1, c+1);
		else
			DFS(k-1, c);
	}
	else {
		S[k] = false;
		DFS(k-1, c);
		S[k] = true;
		DFS(k-1, c+1);
		S[k] = false;
	}
}
int main() {
	freopen("lights.in","r",stdin);
	freopen("lights.out","w",stdout);
	scanf("%d %d\n", &N, &M);
	int s, t;
	for(int i=1; i<=N; i++)
		G[i][i] = 1;
	//Print();
	for(int i=1; i<=M; i++) {
		scanf("%d %d\n", &s, &t);
		G[s][t] = G[t][s] = 1;
	}
	//Print();
	for(int i=1; i<=N; i++)
		B[i] = 1;
	for(int i=1; i<=N; i++)
		for(int j=1; j<=N; j++)
			L[i][j] = G[i][j];
	for(int k=1; k<=N; k++) {
		bool f = false;
		for(int i=k; i<=N; i++)
			if(L[i][k]) {
				f = true;
				Exchange(i,k);
				break;
			}
		if(!f)
			continue;
		for(int i=k+1; i<=N; i++)
			if(L[i][k])
				Xor(i,k);
	}
	A = INF;
	DFS(N, 0);
	printf("%d\n", A);
	return 0;
}