#include <bits/stdc++.h>
using namespace std;
//#define ll long long
#define int long long
//#define ull unsigned long long
#define PI pair<int,int>
//#define PI pair<ll,int>
const int maxm=2e5+5;
int d[1<<20];
int e[20];//e[i]为点i的边集
int n,m;
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)e[i]|=(1<<i);
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        a--,b--;
        e[a]|=(1<<b);
        e[b]|=(1<<a);
    }
    //init
    for(int i=0;i<(1<<n);i++){
        d[i]=1e9;
    }
    d[0]=0;
    //dp
    for(int i=1;i<(1<<n);i++){
        //判断集合是否本身是一个完全图
        int ok=1;
        for(int j=0;j<n;j++){
            if(i>>j&1){
                if((e[j]&i)!=i){
                    ok=0;
                }
            }
        }
        if(ok)d[i]=1;
        //枚举当前集合是从何组合的
        for(int j=i;j;j=((j-1)&i)){//枚举子集
            d[i]=min(d[i],d[i-j]+d[j]);//d[i]由(i-j)和j组成.
        }
    }
    cout<<d[(1<<n)-1]<<endl;
    return 0;
}
/*
n<=18,考虑状压dp:
令d[i]表示点集为i时,满足题目条件的最小连通块数量.



*/




#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <ios>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>

using namespace std;

using i64 = int64_t;
using u64 = uint64_t;
using i32 = int32_t;
using pi64 = pair<i64, i64>;

constexpr i64 MAXN = 3*100*1000LL+5LL;
constexpr i64 MOD = 1000000007LL;
constexpr i64 INF64 = MOD * MOD;
#define vec vector
#define let const
#define DRi64(x) i64 x; cin >> x;
#define DRS(x) string x; cin >> x;
#define DRVi64(v, n) vec<i64> v(n); { for (i64 i = 0; i < n; ++i) { cin >> v[i]; }}

#ifdef DEBUG
#define P(x) cerr << x << "\n"
#else
#define P(x)
#endif

int
main()
{
    ios_base::sync_with_stdio(false);
    const unsigned seed =
        chrono::system_clock::now().time_since_epoch().count();
    mt19937 gen(seed);

    DRi64(N); DRi64(M);
    vec<vec<i64>> adj(N);
    for (i64 i = 0; i < M; ++i)
    {
        DRi64(A); DRi64(B);
        A--, B--;
        adj[A].push_back(B);
        adj[B].push_back(A);
    }

    vec<bool> is_valid(1LL << N, false);
    // look at all possible cliques and see whether each one is valid
    for (i64 mask = 0; mask < (1LL << N); ++mask)
    {
        vec<i64> clique;
        for (i64 i = 0, mask2 = mask; mask2; ++i, mask2 >>= 1)
        {
            if (mask2 & 1)
            {
                clique.push_back(i);
            }
        }
        bool ok = true;
        for (let i64 v : clique)
        {
            for (let i64 v2 : clique)
            {
                if (v2 == v)
                {
                    continue;
                }
                ok &= find(adj[v].begin(), adj[v].end(), v2) != adj[v].end();
            }
        }
        is_valid[mask] = ok;
        P(mask << ": " << (is_valid[mask] ? "OK" : "bad"));
    }

    vec<i64> min_clique_counts(1LL << N, MOD);
    min_clique_counts[0] = 0;
    for (i64 mask = 1; mask < (1LL << N); ++mask)
    {
        for (i64 submask = mask; submask; submask = (submask - 1) & mask)
        {
            P("mask: " << mask << " sub: " << submask);
            if (is_valid[submask])
            {
                P("mask & ~submask: " << (mask & ~submask));
                min_clique_counts[mask] = min(min_clique_counts[mask], 1 + min_clique_counts[mask & ~submask]);
            }
            else
            {
                min_clique_counts[mask] = min(min_clique_counts[mask], min_clique_counts[submask] + min_clique_counts[mask & ~submask]);
            }
        }
        P(bitset<18>(mask) << ": " << min_clique_counts[mask]);
    }
    cout << min_clique_counts[(1LL << N) - 1] << "\n";

    return 0;
}
