#include <bits/stdc++.h>

using namespace std;
#define int long long


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    int n, m;
    cin >> n >> m;

    vector<int> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u] |= 1 << v;
        g[v] |= 1 << u;
    }

    vector<int> dp(1 << n, LLONG_MAX);
    dp[0] = 1;
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i] == 1 && (g[j] & i) == i)
                dp[i | 1 << j] = 1;
        }
    }

    for (int i = 1; i < (1 << n); i++) {
        for (int j = i; --j &= i;) {
            dp[i] = min(dp[i], dp[i ^ j] + dp[j]);
        }
    }

    cout << dp.back();
}



#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<ll, ll>;
using Vec = vector<ll>;
using VecP = vector<P>;
template <class T>
using Vec2 = vector<vector<T>>;
#define REP(i, m, n) for(int i = (m); i < (n); ++i)
#define REPN(i, m, n) for(int i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(int i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(int i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
template <class T1, class T2>
bool chmax(T1 &a, const T2 b) { return a < b ? a = b, true : false; }
template <class T1, class T2>
bool chmin(T1 &a, const T2 b) { return a > b ? a = b, true : false; }
template <class T>
istream &operator>>(istream &is, vector<T> &v) { for (T &i : v) is >> i; return is; }
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &i : v) os << i << ' '; return os; }
void _co() { cout << '\n'; }
template <class Head, class... Tail>
void _co(Head&& head, Tail&&... tail) { cout << ' ' << head; _co(forward<Tail>(tail)...); }
template <class Head, class... Tail>
void co(Head&& head, Tail&&... tail) { cout << head; _co(forward<Tail>(tail)...); }
void ce() { cerr << '\n'; }
template <class Head, class... Tail>
void ce(Head&& head, Tail&&... tail) { cerr << head << ' '; ce(forward<Tail>(tail)...); }
void sonic() { ios::sync_with_stdio(false); cin.tie(nullptr); }
void setp(const int n) { cout << fixed << setprecision(n); }
constexpr int64_t INF = 1000000000000000001;
constexpr int64_t MOD = 1000000007;
constexpr int64_t MOD_N = 998244353;
constexpr long double EPS = 1e-11;
const double PI = acos(-1);

int main(void) {
    int n, m;
    cin >> n >> m;
    const int N = 1 << n;

    vector<bitset<18>> g(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a][b] = true;
        g[b][a] = true;
    }
    rep(i, n) g[i][i] = true;

    vector<int> dp(1 << n, 1e9);
    dp[0] = 0;

    rep(bit, N) {
        bool flg = true;
        rep(i, n) {
            rep(j, n) {
                if ((bit >> i) & (bit >> j) & 1)
                    flg &= g[i][j];
            }
        }
        if (flg)
            dp[bit] = 1;
    }

    rep(bit, N) {
        for (int i = bit; --i &= bit; ) {
            chmin(dp[bit], dp[i] + dp[bit ^ i]);
        }
    }
    co(dp.back());

    return 0;
}
