#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include <limits>
#include <iomanip>
#include <cassert>
#include <numeric>
#include <chrono>
#include <random>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define debug(x) cerr << #x << " = " << (x) << endl;
#define debug_pii(x) cerr << "(" << x.first << "," << x.second << ")";
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n-1;i >= 0;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second

const long double pi = 3.141592653589793;
const int mod = 1e9 + 7;

const int nmax = 18;
const int inf = 30;
int dp[1 << nmax];
int g[nmax][nmax];
int n, e, a, b;

bool fullc(int mask) {
  rep(i, n) {
    rep(j, n) {
      if(i == j) continue;
      int ii = mask & (1 << i);
      int jj = mask & (1 << j);
      if(ii > 0 && jj > 0) {
        if(g[i][j] == 0) {
          return false;
        }
      }
    }
  }
  return true;
}

void solve() {

  cin >> n >> e;
  rep(i, e) {
    cin >> a >> b;
    a--;
    b--;
    g[a][b] = g[b][a] = 1;
  }
  for(int mask = 1;mask < (1 << n);mask++) {
    if(fullc(mask)) {
      dp[mask] = 1;
      continue;
    }
    dp[mask] = inf;
    for(int j = mask;j > 0;j = (j-1) & mask) {
      dp[mask] = min(dp[j] + dp[mask ^ j], dp[mask]);
    }
  }
  cout << dp[(1 << n)-1] << endl;
}

int main() {

 // freopen("input.in","r",stdin);
 // freopen("output.out","w",stdout);
 // cout << fixed << setprecision(15);
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 int t = 1;
 // cin >> t;
 while (t--) {
   solve();
 }

 return 0;
}

#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll = long long; using ull = unsigned long long; using pll = pair<ll,ll>; const ll INF = 4e18;
void print0() {}
template<typename Head,typename... Tail> void print0(Head head,Tail... tail){cout<<fixed<<setprecision(15)<<head;print0(tail...);}
void print() { print0("\n"); }
template<typename Head,typename... Tail>void print(Head head,Tail... tail){print0(head);if(sizeof...(Tail)>0)print0(" ");print(tail...);}
// clang-format on

vector<ll> nodes(19);
vector<vector<ll>> nodesset((1ULL << 19) + 5);
ll n, m;

vector<ll> memo2(500000, -1);
// 確定済みを s とするbitDP
ll dfs2(ll s) {
    if (s == (1ULL << n) - 1) {
        return 0;
    }
    if (memo2[s] >= 0) {
        return memo2[s];
    }
    ll ans = INF;
    auto task = stack<ll>();
    for (ll u = 0; u < n; u++) {
        ll ub = (1ULL << u);
        if (ub & s) continue;
        task.push(ub);
    }

    set<ll> done;
    while (!task.empty()) {
        ll t = task.top();
        task.pop();
        if (done.count(t)) continue;
        done.insert(t);
        bool added = false;
        for (auto v : nodesset[t]) {
            ll vb = (1ULL << v);
            if (vb & s) continue;
            if (vb & t) continue;
            task.push(t | vb);
            added = true;
        }
        // 次の状態の探索は、拾える連結成分を全部拾ったときだけ
        if (!added) ans = min(ans, 1 + dfs2(t | s));
    }
    return memo2[s] = ans;
}

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

    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        nodes[a] |= (1ULL << b);
        nodes[b] |= (1ULL << a);
    }
    for (ll i = 0; i < (1ULL << n); i++) {
        for (ll j = 0; j < n; j++) {
            ll nd = nodes[j];
            if ((nd & i) == i) {
                nodesset[i].push_back(j);
            }
        }
    }
    print(dfs2(0));
}
