#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


enum Type{
	UNDEFINED,
	D,
	NOT_D,
};

int N,M,ans;
int min_dist[30];
vector<int> G[30];


bool check(Type array[30]){

	bool FLG;

	for(int i = 0; i < N; i++){

		if(array[i] != NOT_D)continue;

		FLG = false;
		for(int k = 0; k < G[i].size(); k++){
			if(array[G[i][k]] == UNDEFINED || array[G[i][k]] == D){
				FLG = true;
				break;
			}
		}
		if(!FLG)return false;
	}
	return true;
}


void recursive(Type array[30],int num,int count){

	if(count >= ans)return;

	if(num == N){
		ans = count;
		return;
	}

	Type next_arrayD[30];
	for(int i = 0; i < N; i++)next_arrayD[i] = array[i];
	next_arrayD[num] = D;
	recursive(next_arrayD,num+1,count+1);

	Type next_arrayNOT[30];
	for(int i = 0; i < N; i++)next_arrayNOT[i] = array[i];
	next_arrayNOT[num] = NOT_D;
	if(check(next_arrayNOT)){
		recursive(next_arrayNOT,num+1,count);
	}
}


void func(){

	for(int i = 0; i < N; i++){
		G[i].clear();
	}

	int from,to;
	for(int loop = 0; loop < M; loop++){
		scanf("%d %d",&from,&to);
		G[from].push_back(to);
		G[to].push_back(from);
	}

	ans = N;
	Type first[30];
	for(int i = 0; i < N; i++)first[i] = UNDEFINED;

	recursive(first,0,0);

	printf("%d\n",ans);
}

int main(){

	while(true){
		scanf("%d %d",&N,&M);
		if(N == 0 && M == 0)break;

		func();
	}

	return 0;
}

