#include <fstream>
using namespace std;
ifstream fin("lights.in");
ofstream fout("lights.out");
long long V,E,Min=1,f,Map[10002];
void Initialize()
{
int i,St,En;
	fin>>V>>E;
	for(i=1;i<=17;i++)
		Min*=10;
	for(i=1;i<=V;i++)
	{
		Map[i]+=1<<(i-1);
		f+=1<<(i-1);
	}
	for(i=1;i<=E;i++)
	{
		fin>>St>>En;
		Map[St]+=1<<(En-1);
		Map[En]+=1<<(St-1);
	}
}

void DFS(int Pos,int Sum)
{
int i;
	if(Pos==V)
	{
		if(f)
			return;
		if(Min>Sum)
			Min=Sum;
		return ;
	}
	Pos++;
	for(i=0;i<=1;i++)
	{
		if(i==1)
			f=f^Map[Pos];
		DFS(Pos,Sum+i);
		if(i==1)
			f=f^Map[Pos];
	}
}

int main()
{
	Initialize();
	
	DFS(0,0);
	
	fout<<Min<<endl;
	
	fin.close();
	fout.close();
	return 0;
}