#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include <cassert>
#include <numeric>
typedef long long ll;
#define FOR(i, a, b) for(int i=(a); i<(b);i++)
#define REP(i, n) for(int i=0; i<(n);i++)
#define ROF(i, a, b) for(int i=(b-1); i>=(a);i--)
#define PER(i, n) for(int i=n-1; i>=0;i--)
using namespace std;


vector<ll> parent;
vector<vector<ll>> edges;
vector<ll> depth;

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

  vector<ll> a, b;
  //vector<vector<ll>> g;
  bool g[18][18] = { false };
  a.resize(m);
  b.resize(m);

  REP(i, m) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
    g[a[i]][b[i]] = true;
    g[b[i]][a[i]] = true;
  }

  vector<ll> ans;
  ll count = 1 << n;
  ans.resize(count);
  FOR(i, 1, count) {
    // ビット数1なら強制で完全グラフ
    int count = 0;
    REP(j, n) {
      if ((i & (1 << j)) != 0) {
        count++;
      }
    }
    if (count == 1) {
      ans[i] = 1;
      continue;
    }
    // 完全グラフか調べる
    bool pg = true;
    REP(j, n) {
      if ((i & (1 << j)) == 0) {
        continue;
      }
      FOR(k, j + 1, n) {
        if ((i & (1 << k)) == 0) {
          continue;
        }
        pg = pg && g[j][k];
        if (!pg) break;
      }
      if (!pg) break;
    }
    if (pg) {
      ans[i] = 1;
      continue;
    }

    // 分割する
    ll sub = i;
    ans[i] = n;
    sub = (sub - 1) & i;
    while (sub != i) {
      if (sub != 0) {
        ll tmp = ans[sub] + ans[i & (~sub)];
        ans[i] = tmp < ans[i] ? tmp : ans[i];
      }
      sub = (sub - 1) & i;
    }
  }
  cout << ans[count - 1];
  return 0;
}
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define maxn 200005 
typedef long long ll;
using namespace std;
const double pi = acos(-1);
const ll mod = 1e9 + 7;
inline ll read(){
    ll x = 0, f = 1;char ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch -'0';ch = getchar();}
    return x * f;
}
int n, q;
int dp[1 << 20], ok[1 << 20];
int mp[20][20], m, sum[1 << 20];;
int main(){
	int i, j, u, k, v;
	n = read(), m = read();
	for(i = 1;i <= m;i++) u = read(), v = read(), mp[u][v] = mp[v][u] = 1;
	for(i = 0;i < n;i++) ok[1 <<i] = 1;
	for(i = 1;i < (1 << n);i++) sum[i] = sum[i >> 1] + (i & 1);
	for(i = 1;i < (1 << n);i++){
		if(!ok[i]) continue;
		for(j = 1;j <= n;j++){
			if(i & (1 << (j - 1))) continue;
			bool flag = 0;
			for(k = 1;k <= n;k++){
				if((i & (1 << (k - 1))) && k != j) if(!mp[k][j]) {flag = 1;break;}
			}
			if(!flag) ok[i | (1 << j - 1)] = 1;
		}
	}
	memset(dp, 0x3f3f,sizeof(dp));
	for(i = 0;i < (1 << n);i++) if(ok[i]) dp[i] = 1;
	for(i = 1;i < (1 << n);i++){
		j = i;
		for(;j;j = (j - 1) & i) if(dp[i] > dp[j] + dp[i ^ j]) dp[i] = dp[j] + dp[i ^ j];
	}
	printf("%d\n", dp[(1 << n) - 1]);
	return 0;
}
/*
6 6
1 2
2 3
2 4
4 5
3 5
3 6
*/