#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll> pql;
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, k, n) for(ll i = ll(k); i <= ll(n); i++)
#define rep3(i, n, k) for(ll i = ll(n); i >= ll(k); i--)
#define all(v) (v).begin(), (v).end()
ll mod(ll a, ll b) {if(b == 0) return 0; return (a % b + b) % b;}
template <typename T, typename U> bool chmin(T &a, const U b) {if(a > b) {a = b; return 1;} return 0;}
template <typename T, typename U> bool chmax(T &a, const U b) {if(a < b) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 2e5;
const ld eps = 1e-9;
const char newl = '\n';

ll n;
vvl G;
vl memo;

ll f(ll s) {
  if(memo[s]) return memo[s];

  vl v;
  rep(i, n) if(s & (1LL << i)) v.push_back(i);
  ll vs = v.size();

  bool is_complete = 1;
  rep(i, vs-1) {
    if(!is_complete) break;
    rep2(j, i+1, vs-1) if(!count(all(G[v[i]]), v[j])) {
      is_complete = 0;
      break;
    }
  }
  if(is_complete) {
    memo[s] = 1;
    return 1;
  }
  
  ll res = vs;
  for(ll t=(s-1)&s; t>0; t=(t-1)&s) chmin(res, f(t) + f(s-t));
  memo[s] = res;
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll m, a, b;
  cin >> n >> m;
  G = vvl(n);
  memo = vl(1LL << n);
  rep(_, m) {
    cin >> a >> b;
    a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  cout << f((1LL << n) - 1) << newl;
  return 0;
}
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <functional>

#include <bitset>

#ifdef VS
#define __builtin_clz(v) __lzcnt(v)
#endif

constexpr int MAXN = 18;

int n, m;
int gr[MAXN];
char dp[1 << MAXN];
std::bitset<1 << MAXN> may;


int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;
	for (int i = 0; i < n; i++) {
		gr[i] |= (1 << i);
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		std::cin >> u >> v;
		u--; v--;
		gr[u] |= 1 << v;
		gr[v] |= 1 << u;
	}
	may[0] = true;
	for (int mask = 1; mask < (1 << n); mask++) {
		int i = 31 - __builtin_clz(mask);
		if ((may[mask ^ (1 << i)]) && ((gr[i] & mask) == mask)) {
			may[mask] = true;
		}
	}

	std::fill(dp, dp + (1 << n), n);
	dp[0] = 0;
	for (int mask = 1; mask < (1 << n); mask++) {
		if (may[mask]) {
			dp[mask] = 1;
			continue;
		}
		for (int s_mask = mask; s_mask > 0; s_mask = (s_mask - 1) & mask) {
			if (may[s_mask]) {
				dp[mask] = std::min<char>(dp[mask], dp[mask ^ s_mask] + 1);
			}
		}
	}

	std::cout << (int)dp[(1 << n) - 1] << std::endl;

	return 0;
}