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

using namespace std;

struct Node{
  vector<int> vcon;
  Node(){}
};

bool solve(const vector<Node> &G, int n, int k){
  int *p;
  bool loop = false;
  
  p = new int[k];
  for(int i = 0; i < k; i++) p[i] = i;
  
  do{ loop = false;

    bool bNG = false;
    bool vis[n];
    fill(vis,vis+n,false);

    for(int i = 0; i < k; ++i){
      vis[ p[i] ] = true;
      for(int j = 0; j < G[ p[i] ].vcon.size(); ++j){
	vis[ G[ p[i] ].vcon[j] ] = true;
      }
    }

    for(int i = 0; i < n; ++i){
      if( !vis[ i ] ){
	bNG=true;
      }
    }
    if( !bNG ) return true;
    
    for(int pk=k-1;pk>=0;pk--){p[pk]++;if(p[pk]<=n-(k-pk)){for(int j=pk+1;j<k;j++)p[j]=p[j-1]+1;pk++;loop=true;break;}}
  }while(loop);
  delete [] p; 
  return false;
}

int main(){
  while(true){
    int ans = -1;
    int N,V;
    cin >> N >> V;
    if( N == 0 && V == 0 ) break;
    vector<Node> G(N);
    for(int i = 0; i < V; ++i){
      int a,b;
      cin >> a >> b;
      G[a].vcon.push_back(b);
      G[b].vcon.push_back(a);
    }
    
    for(int k = 1; k <= (N%2==0?N/2:N/2+1); ++k){
      if( solve(G,N,k) ){
	ans = k;
	break;
      }
    }
    cout << ans << endl;
  }
  return 0;
}