#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

int n,m,ans;
int vis[600];
vector<int> E[600];

void DFS(int u,int L){
	vector<int> G;
	if (L>=ans) return;
	if (u > 30||u > n){
		ans=min(ans,L);
		return;
	}
	int tag=1;
	for (int i=0;i<E[u].size();i++){
		int v=E[u][i];
		tag&=vis[v];
	}
	if (tag||vis[u]){
		DFS(u+1,L);
		return;
	}
	G.clear();
	tag=0;
	for (int i=0;i<E[u].size();i++){
		int v=E[u][i];
		if (!vis[v]){
			tag++;
			G.push_back(v);
			vis[v]=1;
		}
	}
	DFS(u+1,L+tag);
	for (int i=0;i<G.size();i++){
		int v=G[i];
		vis[v]=0;
	}
	vis[u]=1;
	DFS(u+1,L+1);
	vis[u]=0;
}

int main()
{
	int a,b;
	while(scanf("%d%d",&n,&m)!=EOF){
		for (int i=1;i<=n;i++){
			E[i].clear();
			vis[i]=0;
		}
		for (int i=0;i<m;i++){
			scanf("%d%d",&a,&b);
			E[a].push_back(b);
			E[b].push_back(a);
		}
		ans=n;
		DFS(1,0);
		printf("%d\n",ans);
	}
	return 0;
}