
// Problem: F - Close Group
// Contest: AtCoder - AtCoder Beginner Contest 187
// URL: https://atcoder.jp/contests/abc187/tasks/abc187_f
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define int long long
#define F(i, n) for (int i = 0; i < n; i++)
#define all(x)(x).begin(), (x).end()

using ld = long double;
using vi = vector <int>;
using mi = map <int, int>;
using pii = pair <int, int>;

const int N = 600005;
const int MOD = 1e9 + 7;

#define show(arr) { for (auto x: arr) cout << x << " "; cout << '\n'; }
#define show_(arr, n) F(i, n) show(arr[i])
int adj[20][20];
int dp[N];
int dist[N];
void solve() {
	int n,m, ans = 0; cin>>n>>m;
   	F(i, m){
   		int x,y;
   		cin>>x>>y; x--; y--;
   		adj[x][y]=1;
   		adj[y][x]=1;
   	}
	int a = 0;
	for(int i=0;i<n;i++) a += (1ll<<i);
	
	
	F(i,(1ll<<n)){
		dp[i]=0;
	}
	dp[0]=1;
	F(i,(1ll<<n)){
		dist[i] = 1e9;
		for(int j=0;j<n;j++){
			if(dp[i^(1ll<<j)]){
				bool ok=1;
				int x=(i^(1ll<<j));
				for(int k=0;k<n;k++){
					if(k==j) continue;
					if(((1ll<<k) & x )&&(adj[k][j]==0)){ ok=0; break;}
				}
				if(ok){
					dp[i]=1;
					break;
				}
			}
		}
	}
	dist[0]=0;
	for(int i=0;i+1<(1<<n);i++)
	{
		int j=0;
		while(i>>j&1)j++;
		int t=~i&(1<<n)-1;
		t^=1<<j;
		for(int k=t;;k=k-1&t)
		{
			if(dp[k|1<<j])
			{
				dist[i|k|1<<j]=min(dist[i|k|1<<j],dist[i]+1);
			}
			if(k==0)break;
		}
	}
	cout<<dist[(1<<n)-1]<<endl;
}
int32_t main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   int32_t t=1;
   // cin >> t;
   while (t--) solve();

   return 0;
}
//abc187_f.cpp
//Sat Jan  9 16:04:40 2021

#include <bits/stdc++.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007
#define rep(i,n) for (int i=0;i<(n);++i)

using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,m;
	cin >> n >> m;

	vector<int> e(n,0);
	rep(i,m){
		int a,b;
		cin >> a >> b;
		a--;b--;
		e[a] += 1<<b;
		e[b] += 1<<a;
	}

	vector<int> dp(1<<n,99999);
	dp[0] = 0;
	rep(i,1<<n){
		if (i==0)continue;
		rep(j,n){
			if(1<<j&i){
				int target = i-(1<<j);
				if (dp[target]<=1 && (e[j]&target)==target){
					dp[i] = 1;
				}
				break;
			}
		}
	}

	rep(i,1<<n){
		for (int j=i;j>0;j=((j-1)&i)){
			int k = i-j;
			dp[i] = min(dp[i],dp[j]+dp[k]);
		}
	}

	cout << dp[(1<<n)-1] << endl;
}