x,y,a[32],r;
S(k,b,m){
	if(k==x){
		if(b==~(~0<<x))
			if(m<r)
				r=m;
	}else{
		S(k+1,b,m);
		if(m+1<r){
			S(k+1,b|a[k],m+1);
		}
	}
}
main(i,j){
	for(;scanf("%d%d",&x,&y)*x;){
		r=x;
		for(i=0;i<x;i++)
			a[i]=1<<i;
		for(;y--;){
			scanf("%d%d",&i,&j);
			a[i]|=1<<j;
			a[j]|=1<<i;
		}
		S(0,0,0);
		printf("%d \n",r);
	}
}