#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define fs first
#define sc second
#define mod 100093
ll ans = 1e15, D, st, ed, N, M, ch[40], from, to;
vector<pair<ll, ll> > DS[2][100103];
vector<ll> vis[2][100103];
ll Hash1(ll x) {
	return x & (x - 1)^ (x + 1) %mod;
}
ll Hash2(ll x) {
	return x ^ ch[x%10] %mod;
}
ll Hash(ll x) {
	return (Hash1(x) + Hash2(x)) % mod;
}
void Insert(ll x, ll Dist, ll dir) {
	ll w = Hash(x);
	vis[dir][w].push_back(x);
	DS[dir][w].push_back(mp(x, Dist));
}
bool vs(ll x, ll dir) {
	ll w = Hash(x);
	for(int i = 0; i < vis[dir][w].size(); i++)if(vis[dir][w][i] == x)return 1;
	return 0;
}
ll ds(ll x, ll dir) {
	ll w = Hash(x);
	for(int i = 0; i < DS[dir][w].size(); i++)if(DS[dir][w][i].fs == x)return DS[dir][w][i].sc;
}
queue<pair<ll,ll> > Q;
void bfs() {
	Q.push(mp(st, 1));
	Q.push(mp(ed, 0));
	Insert(st, 0, 1);
	Insert(ed, 0, 0);
	while(Q.size()) {
		ll dir = Q.front().sc, ST = Q.front().fs, DIST = ds(ST, dir);
		while(Q.size() && Q.front().sc == dir && ds(Q.front().fs, dir) == DIST) {
			ll nw = Q.front().fs;
			Q.pop();
			if(vs(nw, 1) && vs(nw, 0)) {
				ans = ds(nw, 1) + ds(nw, 0);
				return;
			}
			for(int i = 1; i <= N; i++) {
				ll zd = (nw ^ ch[i]);
				if(vs(zd, dir))continue;
				Insert(zd, DIST + 1, dir);
				Q.push(mp(zd, dir));
				if(vs(zd, 1) && vs(zd, 0)) {
					ans = ds(zd, 1) + ds(zd, 0);
					return;
				}
			}
		}
		if(ans != 1e15)return;
	}
}
int main()
{
	cin >> N >> M;
	for(int i = 1; i <= M; i++)	{
		cin >> from >> to;
		ch[from] |= (1ll << (to - 1));
		ch[to] |= (1ll << (from - 1));
	}
	for(int i = 1; i <= N; i++)ch[i] |= (1ll << (i - 1));
	for(int i = 1; i <= N; i++) {
		ed |= (1ll << (i - 1));
	}
	bfs();
	cout << ans;
	
	
	
	
	return 0;
}