#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

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

    int N,M; cin >> N >> M;
    vector<int> g(N);
    rep(i,M){
        int a,b; cin >> a >> b; a--; b--;
        g[a] |= 1 << b;
        g[b] |= 1 << a;
    }

    vector<int> dp(1 << N, 1e9);
    dp[0] = 1;
    rep(i,N)rep(j,1<<N) if(dp[j] == 1 && (g[i] & j) == j) dp[j | 1 << i] = 1;
    rep(i,1<<N)for(int j = i; --j &= i;) dp[i] = min(dp[i], dp[i ^ j] + dp[j]);
    cout << dp.back() << endl;
}
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n, vector<int>(n, 0));
    for(int i = 0; i < n; i++)
        v[i][i] = 1;
    int a, b;
    for(int i = 0; i < m; i++)
    {
        cin >> a >> b;
        v[a - 1][b - 1] = 1;
        v[b - 1][a - 1] = 1;
    }

    vector<bool> dp((1 << n), false);
    
    for(int i = 0; i < (1 << n); i++)
    {
        bool good = true;
        
        for(int j = 0; j < n && good; j++)
        {
            if(!((i >> j) & 1))
                continue;
            for(int k = 0; k < n && good; k++)
            {
                if(!((i >> k) & 1))
                    continue;
                if(v[k][j] == 0)
                    good = false;
            }
        }
        if(good)
            dp[i] = true;
    }

    vector<int> ret(1 << n, 1e9);
    ret[0] = 0;
    
    for(int i = 1; i < (1 << n); i++)
    {
        if(dp[i])
        {
            ret[i] = 1;
            continue;
        }
        for(int mask = i; mask; mask = (mask - 1) & i)
        {
            ret[i] = min(ret[i], ret[mask] + ret[i ^ mask]);
        }
    }
    cout << ret[(1 << n) - 1] << endl;

    return 0;
}


