#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int head[N],tot,n,k,t,s[N],tt,cnt,sz[N],m,minn=1e9,step,a[N];
queue<int> q1,q2;
map<int,int> vis1,vis2;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
void bfs(int s,int t){
	q1.push(s);
	q2.push(t);
	vis1[s]=1;
	vis2[t]=1;
	while(!q1.empty()&&!q2.empty()){
		if(q1.size()<=q2.size()){
			int bq=q1.size();
			while(bq--){
				int h=q1.front();
				q1.pop();
				for(int i=0;i<30;i++){
					int v=h^a[i];
					if(vis2.find(v)!=vis2.end()){
						step++;
						return ;
					}
					if(vis1.find(v)==vis1.end()){
						vis1[v]=1;
						q1.push(v);
					}
				}	
			}
		}else {
			int bq=q2.size();
			while(bq--){
				int h=q2.front();
				q2.pop();
				for(int i=0;i<30;i++){
					int v=h^a[i];
					if(vis1.find(v)!=vis1.end()){
						step++;
						return ;
					}
					if(vis2.find(v)==vis2.end()){
						vis2[v]=1;
						q2.push(v);	
					}
				}
			}
		
		}
		step++;
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		a[i]=1LL<<i;
	}
	for(int i=1;i<=m;i++){
		int u,v;
		u=read(),v=read();
		u--,v--;
		a[u]|=1LL<<v;
		a[v]|=1LL<<u;
	}
	bfs(0,((1LL<<n)-1));
	cout<<step;
	return 0;
}
/*


*/