#include <cstdio>
#include <set>

#define I_F "lights.in"
#define O_F "lights.out"

const short Maxn=35;

struct que
{
	long long x;
	short s;
	que *next;
};
long long T[Maxn];
struct edge
{
	short y;
	edge *next;
}*map[Maxn];
short n;
long long Com=1;
short ans;

void Input();
void Prework();
void Unc(const long long&, bool*);
void Enc(const bool*, long long&);
void Cpy(const bool*, bool*);
void Search();
void Output();

int main()
{
	Input();
	Prework();
	Search();
	Output();
	return 0;
}

void Input()
{
	int m,a,b;
	edge *t;
	freopen(I_F,"r",stdin);
	scanf("%hd%d",&n,&m);
	for (int i=0; i<m; i++)
	{
		scanf("%d%d",&a,&b);
		t=map[--a];
		map[a]=new edge;
		map[a]->y=--b;
		map[a]->next=t;
		t=map[b];
		map[b]=new edge;
		map[b]->y=a;
		map[b]->next=t;
	}
}

void Prework()
{
	T[0]=1;
	for (short i=1; i<n; i++)
	{
		T[i]=T[i-1]*2;
		Com+=T[i];
	}
}

void Unc(const long long &x, bool *y)
{
	long long t=x;
	for (short i=0; i<n; i++)
	{
		y[i]=(t%2==1);
		t/=2;
	}
}

void Enc(const bool *x, long long &y)
{
	y=0;
	for (short i=0; i<n; i++)
		if (x[i])
			y+=T[i];
}

void Cpy(const bool *a, bool *b)
{
	for (short i=0; i<n; i++)
		b[i]=a[i];
}

void Search()
{
	bool a[Maxn], b[Maxn];
	long long c;
	std::set<long long> f;
	f.insert(0);
	que *head, *tail, *t;
	head=new que;
	head->s=0;
	head->x=0;
	head->next=NULL;
	tail=head;
	bool flag=true;
	
	while (head!=NULL && flag)
	{
		Unc(head->x,a);
		for (short i=0; i<n && flag; i++)
		{
			Cpy(a,b);
			b[i]=!b[i];
			for (edge *j=map[i]; j!=NULL; j=j->next)
				b[j->y]=!b[j->y];
			Enc(b,c);
			if (f.find(c)==f.end())
			{
				tail->next=new que;
				tail=tail->next;
				tail->x=c;
				tail->s=head->s+1;
				tail->next=NULL;
				if (c==Com)
					ans=tail->s,
					flag=false;
			}
		}
		t=head;
		head=head->next;
		delete t;
	}
}

void Output()
{
	freopen(O_F,"w",stdout);
	printf("%hd\n",ans);
}