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

using namespace std;

int b[30];
vector<vector<int> > G;

int dfs(int x,int u,int n){
  if(x<0)return n;
  int m=dfs(x-1,u|1<<x,n+1);
  bool f=false;
  for(auto e:G[x]){
    f|=!(b[e]&u)&&1<<x==(b[e]&-b[e]);
  }
  if(!f){
    m=min(m,dfs(x-1,u,n));
  }
  return m;
}

int main(){
  for(int x,y;cin>>x>>y,x|y;){
    G=vector<vector<int> >(x);
    for(int i=0;i<x;i++){
      b[i]=1<<i;
      G[i].push_back(i);
    }
    while(y--){
      int u,v;
      cin>>u>>v;
      b[u]|=1<<v;
      b[v]|=1<<u;
      G[v].push_back(u);
      G[u].push_back(v);
    }
    cout<<dfs(x-1,0,0)<<endl;
  }
}