/*
  In the name of ALLAH
  Author : Raashid Anwar
*/
 
#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
const int M1 =  998244353;
const int M2 =  1000000007;
mt19937 rng((uint64_t)chrono::steady_clock::now().time_since_epoch().count());
 
void solve() {
  int n, m;
  cin >> n >> m;
  vector <int> mask(n), dp(1 << n, n);
  while (m--) {
    int u, v;
    cin >> u >> v;
    mask[u - 1] |= 1 << (v - 1);
    mask[v - 1] |= 1 << (u - 1);
  }
  dp[0] = 1;
  for (int i = 0; i < n; i++) {
    for (int nmask = 0; nmask < (1 << n); nmask++) {
      if (dp[nmask] == 1 && (mask[i] & nmask) == nmask) {
        dp[nmask | (1 << i)] = 1;
      }
    }
  }
  for (int nmask = 1; nmask < (1 << n); nmask++) {
    for (int j = nmask; j; j = (j - 1) & nmask) {
      dp[nmask] = min(dp[nmask], dp[nmask ^ j] + dp[j]);
    }
  }
  cout << dp[(1 << n) - 1] << "\n";
}
 
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
}
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

/*-----for personal-----*/
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define repn(i,n)  rep(i,0,n)

/*-----for lib-----*/
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)

const double EPS = 1e-5;
const int MOD = 1e9+7;
const int INF = INT_MAX / 2;
const ll LLINF = LLONG_MAX / 2;
//for(auto &h : H){ cout << h << " ";} cout << endl;
//for(auto &h : H){for(auto &k:h){cout << k << " ";}cout << endl;}
//for(auto [k,v] : mp){cout << k << " " << v << endl;}
//for(auto [k,v] : mp){cout << k << " "; for(auto &u:v){cout << u << " ";}cout << endl;}

/*
dp[bit] : the minimal number of clique in the subset bit
dp[bit] = max_{subbit \in bit}(dp[sub_bit] + dp[bit&~sub_bit])
O(2^N(subbit \in bit) * 2^N (cases of bit)) = O(4^N) = 68719476736 -> O(3^N)
dp[(1<<N)-1] : answer
dp[0] = 0 : initial
*/

const int N = 18;
vector<ll> dp((1<<N)+1, -1);
vector<vector<bool>> am(N, vector<bool>(N,false));
vector<bool> ok((1<<N)+1, true);
vector<bool> visited((1<<N)+1, false);

ll f(ll bit){
  visited[bit] = true;
  if(dp[bit]!=-1) return dp[bit];
  if(bit==0) return dp[bit] = 0;
  if(ok[bit]) return dp[bit] = 1;
  //cout << (bitset<N>)bit << endl;

  ll min = LLINF;
  for(ll s_bit = bit; ; --s_bit&=bit){
    //cout << bit << " " << s_bit << endl;
    //if(visited[s_bit]) cout << "visited" << endl;
    if(s_bit==bit) continue;
    if(s_bit==0) break;
    ll res = f(s_bit) + f(bit & ~s_bit);
    if(res < min) min = res;
  }
  return dp[bit] = min;
}

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

  repn(i,m){
    int a, b; cin >> a >> b; a--; b--;
    am[a][b] = true;
    am[b][a] = true;
  }

  for(ll bit=0; bit<(1<<n); bit++){
    vector<int> vs;
    for(int i=0; i<n; i++){
      if(bit & (1 << i)) vs.emplace_back(i);
    }

    for(int i=0;i<vs.size()&&ok[bit];i++){
      for(int j=i+1;j<vs.size()&&ok[bit];j++){
        if(!am[vs[i]][vs[j]]) ok[bit] = false; //O(N^2)
      }
    }
  }

  ll res = f((1<<n)-1);
  cout << res << endl;

}
