#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;
const int MAX_V=10001;
int n,m;
vector<int> G[MAX_V];
bool used[MAX_V];
int mark[MAX_V];
int res;

void dfs(int s,int cnt){
  if(cnt>=res)return;
  if(s==n){
    bool ok=true;
    // 全てがmarkされているか
    for(int i=0;i<n;i++){
      if(!mark[i]){
	ok=false;
	break;
      }
    }
    if(ok)res=min(res,cnt);
  }
  else{
    dfs(s+1,cnt);
    // markする
    mark[s]++;
    for(int j=0;j<G[s].size();j++){
      int to=G[s][j];
      mark[to]++;
    }
    dfs(s+1,cnt+1);
    mark[s]--;
    for(int j=0;j<G[s].size();j++){
      int to=G[s][j];
      mark[to]--;
    }
  }
}

int main(){
  while(cin>>n>>m&&(n|m)){
    for(int i=0;i<n;i++)G[i].clear();
    for(int i=0;i<m;i++){
      int a,b;
      cin>>a>>b;
      G[a].push_back(b);
      G[b].push_back(a);
    }
    res=1000000000;
    memset(used,0,sizeof(used));
    memset(mark,0,sizeof(mark));
    dfs(0,0);
    cout<<res<<endl;
  }

  return 0;
}