#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN 40
using namespace std;
typedef long long LL;
int Mat[MAXN][MAXN];
int N,M,max;
class Kaaala {public:int id,num;}K[MAXN];
inline bool cmp(const Kaaala&a,const Kaaala&b) {return a.num>b.num;}
LL binary[MAXN];
LL Sta;
int Ans,res;

inline int Min(int a,int b) {return a<b?a:b;}

void dfs(int now)
{
	if(!Sta) 
	{
		Ans=Min(Ans,res); 
		return;
	}
	if(now>N || res+1>=Ans) return;	
	dfs(now+1);
	res++;
	Sta=Sta^(binary[K[now].id]);
	dfs(now+1); 
	Sta=Sta^(binary[K[now].id]);
	res--;
}

void init()
{
	scanf("%d %d\n",&N,&M); int x,y;
	memset(Mat,0,sizeof(Mat));  Sta=((1LL)<<N)-1;
	for(int i=1;i<=N;i++) {Mat[i][i]=1; K[i].id=i;}
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d\n",&x,&y);
		Mat[x][y]=1,Mat[y][x]=1;
		K[x].num++;  K[y].num++;
	}
	sort(K+1,K+N+1,cmp);
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			binary[i]=binary[i]<<1;
			if(Mat[i][j]) binary[i]++;
		}
	}
}

int main()
{
	freopen("lights.in","r",stdin);
	freopen("lights.out","w",stdout);
	init();
	Ans=Min(N+1,1<<4);
	dfs(1);
	printf("%d\n",Ans);
	return 0;
}