#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T1, class T2> inline bool chmax(T1 &a, const T2 &b) {if (a<b) { a=b; return 1;} return 0;}
template<class T1, class T2> inline bool chmin(T1 &a, const T2 &b) {if (b<a) { a=b; return 1;} return 0;}
struct init{init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}}init_;

#ifdef DEBUG
template <class T> void verr(const set<T> &st) { repa(a, st) cerr << a << " "; cerr << endl; }
template <class S, class T> void verr(const map<S, T> &mp) { repa(a, mp) cerr << "{" << a.first << ", " << a.second << "} "; cerr << endl; }
template <class S, class T, class N> void verr(const vector<pair<S,T>>& a, const N& n) { rep(i, n) cerr << "{" << a[i].first << ", " << a[i].second << "} "; cerr << endl; }
template <class T, class N> void verr(const vector<T>& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << endl; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << endl; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    ll N, M;
    cin >> N >> M;
    vvc<ll> G(N, vl(N));
    rep(i, M){
        ll a, b;
        cin >> a >> b;
        a--, b--;
        G[a][b] = G[b][a] = 1;
    }
    rep(i, N) G[i][i] = true;

    vl dp(1 << N, N), T(1 << N);
    rep(bit, 1 << N) dp[bit] = __builtin_popcount(bit);

    vl used(1 << N);
    rep(bit, 1 << N){
        bool isok = true;
        rep(i, N){
            if (!(bit >> i & 1)) continue;
            repe(j, i + 1, N){
                if (!(bit >> j & 1)) continue;
                if (!G[i][j]) isok = false;
            }
        }
        if (isok) T[bit] = true, dp[bit] = 1, used[bit] = true;
    }

    vc<pair<ll, ll>> A;
    repe(bit, 1, 1 << N) if (T[bit]) A.eb(__builtin_popcount(bit), bit);
    ll now = (1 << N) - 1;
    sort(all(A), greater<>());

    auto dfs = [&](auto&& dfs, ll now) ->void{
        if (used[now]) return;
        used[now] = true;
        for (ll t = now; t > 0; t = (t - 1) & now){
            dfs(dfs, t);
            dfs(dfs, now ^ t);
            chmin(dp[now], dp[t] + dp[now ^ t]);
        }
    };
    dfs(dfs, (1 << N) - 1);

    cout << dp[(1 << N) - 1] << endl;
}
#include <iostream>
using namespace std;

const int MAXN = 19;
int n, m, dp[(1 << MAXN)];
bool isol[(1 << MAXN)];
bool adj[MAXN][MAXN];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        adj[i][i] = 1;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a][b] = 1;
        adj[b][a] = 1;
    }
    for (int i = 1; i < (1 << n); i++)
        dp[i] = 1e9, isol[i] = true;
    for (int i = 1; i < (1 << n); i++)
        for (int j = 1; j <= n; j++)
            if ((i & (1 << (j - 1))) != 0)
                for (int k = j + 1; k <= n; k++)
                    if ((i & (1 << (k - 1))) != 0)
                        if (!adj[j][k])
                            isol[i] = false;
    for (int i = 1; i < (1 << n); i++)
        for(int j = i; j; j = (j - 1) & i)
            if (isol[j])
                dp[i] = min(dp[i], dp[i - j] + 1);
    cout << dp[(1 << n) - 1];
}