/*
UID:cheepok
PID:lights
*/

#include<stdio.h>
#include<stdlib.h>
#define min(a,b) a<b?a:b

typedef long long Int;

struct orz
{int x,y;}a[50];

int n,m,ans,Min;

Int tmp,f[50];

bool flag[50][50];

void dfs(int k)
{
	if(!tmp){ans=min(ans,Min);return;}
	if(k>n)return;if(Min+1>=ans)return;
	dfs(k+1);tmp^=f[a[k].x];Min++;
	dfs(k+1);tmp^=f[a[k].x];Min--;
}

int cmp(const void *a,const void *b)
{return (*(orz *)b).y-(*(orz *)a).y;}

int main()
{
	freopen("lights.in","r",stdin);
	freopen("lights.out","w",stdout);
	int i,j,x,y;
	scanf("%d%d",&n,&m);tmp=(1LL<<n)-1;ans=n+1;
	for(i=1;i<=n;i++){flag[i][i]=1;a[i].x=i;}
	for(i=1;i<=m;i++){scanf("%d%d",&x,&y);
	flag[x][y]=flag[y][x]=1;a[x].y++;a[y].y++;}
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)
	{f[i]<<=1;if(flag[i][j])f[i]++;}
	qsort(a+1,n,sizeof(orz),cmp);dfs(1);
	printf("%d\n",ans);
	return 0;
}