#pragma GCC optimize("O2")

#include <bits/stdc++.h>

#ifdef DEBUG
#include "debug.hpp"
#endif

using namespace std;

#define all(c)              (c).begin(), (c).end()
#define rall(c)             (c).rbegin(), (c).rend()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rrep(i, N)          for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d)    for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))

#ifdef DEBUG
#define debug(x...)         { \
                            ++dbg::depth; \
                            string dbg_vals = dbg::to_string(x); \
                            --dbg::depth; \
                            dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
                            }

#define light_debug(x)      { \
                            dbg::light = true; \
                            dbg::dout << __func__ << ":" << __LINE__; \
                            dbg::dout << "  " << #x << " = " << x << endl; \
                            dbg::light = false; \
                            }
#else
#define debug(x...)         42
#define light_debug(x)      42
#endif


using ll = long long;

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    #ifdef DEBUG
    freopen("debug", "w", stderr);
    #endif

    int N, M; cin >> N >> M;
    vector<vector<bool>> E(N, vector<bool>(N));
    rep(_, M) {
        int a, b; cin >> a >> b; --a, --b;
        E[a][b] = E[b][a] = true;
    }
    
    vector<bool> ch(1 << N, true);
    rep(m, 1 << N) {
        rep(i, N) rep2(j, i + 1, N - 1)
            if((m & (1 << i)) && (m & (1 << j)) && !E[i][j])
                ch[m] = false;
    }

    vector<int> dp(1 << N, N); dp[0] = 0;
    rep(m, 1 << N) {
        for(int i{m}; i; i = (i - 1) & m)
            if((i & m) == i && ch[i]) ckmin(dp[m], 1 + dp[m ^ i]);
    }

    cout << dp.back() << '\n';
    

    #ifdef DEBUG
    dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC  << "ms" << endl;
    #endif

    return 0;
}



#include <bits/stdc++.h> 
using namespace std; 

#define vec vector 
#define PB push_back 

#define MP make_pair 
#define MT make_tuple 
#define F first 
#define S second 

using ll = long long int; // watch out for overflows in your code
using pii = pair<int,int>;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void debug() { cout << "\n"; };
template <typename T, typename... Targs> 
void debug(T t, Targs... args) {
    cout << t << " ";
    debug(args...);
}

template <typename T1, typename T2> 
inline ostream& operator << (ostream& os, const pair<T1,T2>& p) {
    return os << "(" << p.F << ", " << p.S << ")";
}

template <typename T> 
inline ostream& operator << (ostream& os, const vec<T>& v) {
    for(auto& t : v) {
        os << t << " ";
    }
    return os;
}

template <typename T> 
inline ostream& operator << (ostream& os, const vec<vec<T>>& m) {
    for(auto& v : m) {
        for(auto& t : v) {
            os << t << " ";
        }
        os << "\n";
    }
    return os;
}

template <typename T> 
inline ostream& operator << (ostream& os, const set<T>& v) {
    for(auto& t : v) {
        os << t << " ";
    }
    return os;
}

template <typename K, typename V> 
inline ostream& operator << (ostream& os, const map<K,V>& m) {
    for(auto& p : m) {
        os << p.F << " -> " << p.S << "\n";
    }
    return os;
}

const int INF = 1e9;
int N, M;
vec<vec<int>> adj;

struct Solution {
    int lso(int x) {
        return x & (-x);
    }

    bool complete(int mask) {
        int m = mask;
        while(m) {
            int bit_u = lso(m);
            int u = __builtin_ctz(m) + 1;
            int new_mask = bit_u;
            for(int v : adj[u]) {
                new_mask |= (1 << (v-1));
            }
            if((new_mask & mask) != mask) {
                return false;
            }
            m -= bit_u;
            //debug(mask, new_mask);
        }
        return true;
    }

    int S;
    vec<int> dp;
    int ans;

    Solution() : S((1 << N) - 1), dp(S+1, -1) {
        compute();
        ans = dp[S];
    }

    void compute() {
        dfs(S);
    }

    int dfs(int mask) {
        //debug("dfs_in", mask);
        if(mask == 0) {
            return 0;
        }
        int& ans = dp[mask];
        if(ans != -1) {
            //debug("dfs_out_0", mask, ans);
            return ans;
        }
        if(complete(mask)) {
            //debug("dfs_out_1", mask, ans);
            ans = 1;
        }
        else {
            ans = INF;
            for(int m = mask; m > 0; m = ((m-1) & mask)) {
                //debug("dfs_mid", m, mask^m);
                if(m != 0 && (mask ^ m) != 0) {
                    ans = min(ans, dfs(m) + dfs(mask ^ m));
                }
            }
        }
        //debug("dfs_out_2", mask, ans);
        return ans;
    }

};

////////////////////////////////////////////////////////////////////////

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

    cin >> N >> M;
    adj.assign(N+1, vec<int>());
    for(int i = 1; i <= M; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].PB(b);
        adj[b].PB(a);
    }

    Solution sol;
    /*
    cout << sol.check_complete(0b111);
    cout << sol.check_complete(0b101);
    cout << sol.check_complete(0b100);
    cout << "\n";
    */
    cout << sol.ans << "\n";
}

