#include<bits/stdc++.h>
using namespace std;
const int L=40;
#define int long long
map<int,int> mp;
vector<int> e[L];
int n,m,mid,ans=LLONG_MAX;
inline void dfs1(int x,int step,int stat){
	if(x==mid+1){
		if(!mp[stat])mp[stat]=step;
		else mp[stat]=min(mp[stat],step);
		return ;
	}
	dfs1(x+1,step,stat);
	if(stat&(1<<x))stat-=1<<x;
	else stat+=1<<x;
	for(int i=0;i<e[x+1].size();i++){
		int v=e[x+1][i],b=stat&(1<<(v-1));
		if(b)stat-=1<<(v-1);
		else stat+=1<<(v-1);
	}
	dfs1(x+1,step+1,stat);
}
inline void dfs2(int x,int step,int stat){
	if(x==n+1){
		int t=(~stat)&((1<<n)-1);
		if(mp[t])ans=min(ans,step+mp[t]);
		return ;
	}
	dfs2(x+1,step,stat);
	if(stat&(1<<x))stat-=1<<x;
	else stat+=1<<x;
	for(int i=0;i<e[x+1].size();i++){
		int v=e[x+1][i],b=stat&(1<<(v-1));
		if(b)stat-=1<<(v-1);
		else stat+=1<<(v-1);
	}
	dfs2(x+1,step+1,stat);
}
signed main(){
	scanf("%lld%lld",&n,&m);
	while(m--){
		int u,v;
		scanf("%lld%lld",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	mid=1+n>>1;
	dfs1(0,0,0);
	dfs2(mid+1,0,0);
	printf("%lld",ans);
	return 0;
}