#include<cstdio>
#include<vector>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

class DominatingSet{
	const int n;
	const ll Omega;
	vector<ll> mask,mask2;
	vector< vector<int> > adj;

	int dfs(int u,ll S,int tmp,int &ub){
		if(S==Omega){
			ub=tmp;
			return tmp;
		}
		if(u==n || tmp>=ub || (S|mask2[u])!=Omega) return n;

		return min(dfs(u+1,S,tmp,ub),dfs(u+1,S|mask[u],tmp+1,ub));
	}

public:
	DominatingSet(const vector< vector<int> > &A):n(A.size()),Omega((1LL<<A.size())-1),adj(A){
		mask.resize(n);
		rep(u,n){
			mask[u]=1LL<<u;
			rep(i,adj[u].size()) mask[u]|=1LL<<adj[u][i];
		}

		mask2.resize(n);
		mask2[n-1]=mask[n-1];
		for(int u=n-1;u>0;u--) mask2[u-1]=mask[u-1]|mask2[u];
	}

	int solve(){
		int ub=n;
		return dfs(0,0,0,ub);
	}
};

int main(){
	for(int n,m;scanf("%d%d",&n,&m),n||m;){
		vector< vector<int> > adj(n);
		rep(i,m){
			int u,v; scanf("%d%d",&u,&v);
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		printf("%d\n",DominatingSet(adj).solve());
	}

	return 0;
}