#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

long long power(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}
int chromatic_number(const vector<vector<int> > &G) {
    int n = (int)G.size();
    vector<int> neighbor(n, 0);
    for (int i = 0; i < n; ++i) {
        int S = (1<<i);
        for (int j = 0; j < n; ++j)
            if (G[i][j])
                S |= (1<<j);
        neighbor[i] = S;
    }
    
    // I[S] := #. of inndepndet subset of S
    vector<int> I(1<<n);
    I[0] = 1;
    for (int S = 1; S < (1<<n); ++S) {
        int v = __builtin_ctz(S);
        I[S] = I[S & ~(1<<v)] + I[S & ~neighbor[v]];
    }
    int low = 0, high = n;
    while (high - low > 1) {
        int mid = (low + high) >> 1;
        
        // g[S] := #. of "k independent sets" which cover S just
        // f[S] := #. of "k independent sets" which consist of subseta of S
        // then
        //   f[S] = sum_{T in S} g(T)
        //   g[S] = sum_{T in S} (-1)^(|S|-|T|)f[T]
        long long g = 0;
        for (int S = 0; S < (1<<n); ++S) {
            if ((n - __builtin_popcount(S)) & 1) g -= power(I[S], mid);
            else g += power(I[S], mid);
            g = (g % MOD + MOD) % MOD;
        }
        if (g != 0) high = mid;
        else low = mid;
    }
    return high;
}

int main(){
    ll N, M;
    cin >> N >> M;
    vector<vector<int>> G(N, vector<int>(N, 0));

    set<pair<int, int>> AB;
    REP(i,M){
        ll a, b;
        cin >> a >> b;
        a--, b--;
        AB.insert(make_pair(a, b));
        AB.insert(make_pair(b, a));
        //G[a][b] = 1;
        //G[b][a] = 1;
    }

    REP(i,N){
        REP(j,N){
            if(AB.find(make_pair(i, j)) == AB.end()){
                G[i][j] = 1;
                G[j][i] = 1;
            }
        }
    }

    ll ans = 0;
    //ans = N - chromatic_number(G);
    ans = chromatic_number(G);
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
constexpr auto ctz(int x) { return __builtin_ctz(x);      } constexpr auto ctz(ll x) { return __builtin_ctzll(x);      }
constexpr auto clz(int x) { return __builtin_clz(x);      } constexpr auto clz(ll x) { return __builtin_clzll(x);      }
constexpr auto pop(int x) { return __builtin_popcount(x); } constexpr auto pop(ll x) { return __builtin_popcountll(x); }
template <typename F> void for_each_subset(int mask, F&& f) {
    static_assert(is_convertible<decltype(f), function<void(int)>>::value, "can must be void(int)");
    for(int x = mask; x > 0; x = (x - 1) & mask) {
        f(x);
    }
}
const int N = 18;
int adj[N][N], mem[1 << N], is_clique[1 << N];
int opt(int mask) {
    int& ans = mem[mask];
    if(ans == -1) {
        if(is_clique[mask]) {
            ans = 1;
        } else {
            ans = lim<int>::max();
            for_each_subset(mask, [&](int submask) {
                if(submask != mask) {
                    if(is_clique[submask]) {
                        ans = min(ans, 1 + opt(mask ^ submask));
                    }
                }
            });
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u - 1][v - 1] = adj[v - 1][u - 1] = 1;
    }
    for(int i = 0; i < n; i++) {
        adj[i][i] = 1;
    }
    for(int mask = 0; mask < (1 << n); mask++) {
        is_clique[mask] = true;
        for(int ii = mask, i = ctz(ii); ii > 0; ii &= ~(ii & -ii), i = ctz(ii)) {
            for(int jj = mask, j = ctz(jj); jj > 0; jj &= ~(jj & -jj), j = ctz(jj)) {
                is_clique[mask] &= adj[i][j];
            }
        }
    }
    memset(mem, -1, sizeof mem);
    cout << opt((1 << n) - 1) << endl;
    return 0;
}
