rt，玄关

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N=45;
int n,m,p[N];
ll e[N],start;
queue<pair<ll,int>> q;
unordered_map<ll,bool> vis[2];
unordered_map<ll,int> step[2];
int bfs() {
	q.push({start,0});
	vis[0][start]=1;
	q.push({(1ll<<n)-1,1});
	vis[1][(1ll<<n)-1]=1;
	while(!q.empty()) {
		ll x=q.front().fi;
		int flag=q.front().se;
		q.pop();
		if(vis[flag^1][x]) return step[flag^1][x]+step[flag][x];
		for(int i=0;i<n;i++) {
			ll y=x^e[p[i]];
			if(!vis[flag][y]) {
				vis[flag][y]=1,step[flag][y]=step[flag][x]+1;
				q.push({y,flag});
			}
		}
	}
	return -1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++) p[i]=i;
	shuffle(p,p+n,rnd);
	for(int i=0;i<n;i++) {
		e[i]|=(1ll<<i);
	}
	for(int i=1,u,v;i<=m;i++) {
		cin>>u>>v;u--,v--;
		e[u]|=(1ll<<v),e[v]|=(1ll<<u);
	}
	cout<<bfs()<<"\n";
	return 0;
}