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

using namespace std;

const int MAXN=39;

int re[MAXN],i,j,k,m,n,ans,s;
bool map[MAXN][MAXN],flag;

void dfs(int dep)
{
	if (flag) return;
	if (dep>n)
	{
		int i,j;
		bool l;
		for (i=1;i<=n;i++)
		{
			l=false;
			for (j=1;j<=n;j++)
				if (map[i][j])
					if (re[j]==1) l=l xor false;
					else l=l xor true;
			if (!l) return;
		}
		flag=true;
		return;
	}
	if (s<ans)
	{
		++s;
		re[dep]=2;
		dfs(dep+1);
		--s;
	}
	if (ans-s<=n-dep)
	{
		re[dep]=1;
		dfs(dep+1);
	}
	if (flag) return;
}

int main()
{
	freopen("lights.in","r",stdin);
	freopen("lights.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(map,false,sizeof(map));
	for (i=1;i<=n;i++)
		map[i][i]=true;
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&j,&k);
		map[j][k]=true;
		map[k][j]=true;
	}
	for (ans=1;ans<n;ans++)
	{
		flag=false;
		s=0;
		dfs(1);
		if (flag)
		{
			printf("%d\n",ans);
			return 0;
		}
	}
	printf("%d\n",n);
	return 0;
}