#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

int n,m,ans;
bool y[41][41];
bool can[41];
bool ty[41][41];
int tn[41];

void init()
{
	scanf("%d%d",&n,&m);
	int a,b;
	for (;m;--m)
	{
		scanf("%d%d",&a,&b);
		y[a][b]=y[b][a]=true;
	}
	for (int i=1;i<=n;i++)
	{	
		y[i][i]=true;
		y[i][0]=true;
	}
}

void XO(int a,int b)
{
	for (int i=0;i<=n;i++)
		y[a][i]^=y[b][i];
}

void dfs(int u,int now)
{
	if (u>n)
	{
		int t=now;
		for (int i=1;i<=n;i++)
			if (y[i][0] && tn[i]==0) return;
		for (int i=1;i<=n;i++)
			if (y[i][0]) ++t;
		ans=min(ans,t);
			return ;
	}
	if (can[u]) dfs(u+1,now);
	else
	{
		for (int i=1;i<=n;i++)
			if (ty[i][u])
			{
				if (y[i][u])--tn[i];
				y[i][u]=false;
				y[i][0]=!y[i][0];
			}
		dfs(u+1,now+1);
		for (int i=1;i<=n;i++)
			if (ty[i][u])
			{
				if (y[i][u])--tn[i];
				y[i][u]=false;
				y[i][0]=!y[i][0];
			}
		dfs(u+1,now);
	}
}


void solve()
{
	int now;
	for (int i=1;i<=n;i++)
	{
		for (now=1;!y[i][now] && now<=n;now++);
		if (now>n) break;
		can[now]=true;
		for (int j=1;j<=n;j++)
		if (i!=j && y[j][now])
		XO(j,i);
	}
	ans=100;
	for (int T=1;T<=n;T++)
	{
		for (int i=1;i<=n;i++)
		{
			int num=0,k=0;
			for (int j=1;j<=n;j++)
			{
				if (y[i][j]) ++num,k=j;
			}
			if (num==1)
			{	
				can[k]=true;
				for (int j=1;j<=n;j++)
					if (i!=j && y[j][k])
					{
						y[j][k]=false;
						y[j][0]^=y[i][0];
					}
			}
		}
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
	if (y[i][j]) tn[i]++;
	memcpy(ty,y,sizeof(y));
	dfs(1,0);
	printf("%d\n",ans);
}

int main()
{
	freopen("lights.in","r",stdin);
	freopen("lights.out","w",stdout);
	init();
	solve();
	return 0;
}