#include<bits/stdc++.h>
//#include<atcoder/all>
//using namespace atcoder;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair< ll, ll > Pi;
using vl = vector<ll>;
using vs = vector<string>;
using vvl = vector<vector<ll>>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
void printb(ll N,ll d){
    rep(i,d){
        cout<<(N/(1<<(d-i-1)))%2;
    }
    cout<<endl;
    
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};
ll N,M;
map<pair<ll,ll>,bool>m;
vl dp,dp2;
ll rec(ll s){
    //cout<<s<<endl;
    //cout<<dp[s]<<endl;
    if(dp[s]!=-1){
        return dp[s];
    }

    rep(i,N){
        if(((s>>i)&1)==1){
            if(rec(s-(1<<i))==0)continue;
            ll flag=0;
            rep(j,N){
                if(i==j)continue;
                if(((s>>j)&1)==0)continue;

                if(rec((1<<i)|(1<<j))==0){
                    flag=1;
                    break;
                }
            }
            if(flag==0){
                dp[s]=1;
                return 1;
            }
        }
    }
    dp[s]=0;
    return 0;
}

ll rec2(ll s){
    //cout<<s<<endl;
    if(dp2[s]!=-1){
        return dp2[s];
    }
    if(dp[s]==1){
        return dp2[s]=1;
    }
    ll ret=INF;
    for(ll t=(s-1)&s;t>=1;t=(t-1)&s){
        //cout<<s<<" "<<t<<endl;
        //cout<<(s&(~t))<<endl;
        chmin(ret,rec2(s&(~t))+rec2(t));
        

    }

    return dp2[s]=ret;
}
int main() {
    
    cin>>N>>M;
    vl A(N),B(N);
    dp=vl((1<<N),-1);
    dp2=vl((1<<N),-1);
    dp[0]=1;
    //dp2[0]=0;
    rep(i,N){
        dp[(1<<i)]=1;
        dp2[(1<<i)]=1;
    }
    rep(i,M){
        ll a,b;
        cin>>a>>b;
        a--,b--;
        m[{a,b}]=1;
        dp[(1<<a)|(1<<b)]=1;
    }

    rep(i,N){
        rep3(j,i+1,N){
            if(dp[(1<<i)|(1<<j)]==-1){
                dp[(1<<i)|(1<<j)]=0;
            }
        }
    }

    rep(i,(1<<N)){
        if(dp[i]!=-1)continue;
        rec(i);
    }

    
    //cout<<"ok"<<endl;
    /*rep(i,(1<<N)){
        printb(i,N);
        cout<<dp[i]<<endl;
    }*/

    /*rep(i,(1<<N)){

    }*/

    cout<<rec2((1<<N)-1)<<endl;



    return 0;
    

}
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define speed                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define ll long long
#define pb push_back
#define mem1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define setp(x) fixed << setprecision(x)
#define endl "\n"
#define mod 1000000007
#define mod1 998244353
#define ff first
#define ss second
#define MAX 500005
#define N 100005
#define INF 1000000009
#define all(v) v.begin(), v.end()
#define sbit(a) __builtin_popcount(a)
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> ppl;
typedef map<ll, ll> mpll;
typedef map<vector<ll>, ll> mpvl;
ll power(ll x, ll y, ll p)
{
    ll res = 1;

    x = x % p;

    if (x == 0)
        return 0;
    while (y > 0)
    {

        if (y & 1)
            res = (res * x) % p;

        y = y >> 1;
        x = (x * x) % p;
    }

    return res;
}
bool edge[18][18];
ll dp[(1ll << 18)];
void solve()
{
    ll n, m;
    cin >> n >> m;
    bool good[(1ll << n)];
    mem0(good);
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < n; j++)
        {
            edge[i][j] = false;
        }
    }
    for (ll i = 0; i < m; i++)
    {
        ll x, y;
        cin >> x >> y;
        x--, y--;
        edge[x][y] = true;
        edge[y][x] = true;
    }
    for (ll i = 0; i < (1ll << n); i++)
    {
        dp[i] = 1e18;
        vector<ll> v;
        for (ll j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                v.pb(j);
            }
        }

        good[i] = true;
        ll sz = v.size();
        for (ll j = 0; j < sz; j++)
        {
            for (ll k = j + 1; k < sz; k++)
            {
                if (!edge[v[j]][v[k]])
                {
                    good[i] = false;
                    break;
                }
            }
        }
    }
    for (ll i = 0; i < (1ll << n); i++)
    {
        if (good[i] == true)
        {
            dp[i] = 1;
        }
        for (ll j = i; j; j = (j - 1) & i)//iterating over all submasks in total 3^n
        {
            dp[i] = min(dp[i], dp[j] + dp[j ^ i]);
        }
    }
    cout << dp[(1ll << n) - 1] << endl;
    return;
}
int main()
{

    speed;
    ll kk;
    kk = 1;
    // cin >> kk;
    while (kk--)
    {
        solve();
    }
}