#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,a,b) for (ll i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (ll i = (b), _a = (a); i >= _a; i--)
#define rep(i,n) for (ll i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (ll i = (n) - 1; i >= 0; i--)
#define debug(x) cout<<"debug : "<<x<<endl
#define debug2(x,y) cout<<"debug : "<<x<<" | "<<y<<endl
#define debug3(x,y,z) cout<<"debug : "<<x<<" | "<<y<<" | "<<z<<endl
#define debug4(x,y,z,w) cout<<"debug : "<<x<<" | "<<y<<" | "<<z<<" | "<<w<<endl
#define all(ar) ar.begin(), ar.end()
#define rall(ar) ar.rbegin(), ar.rend()
#define sz(x) ((long long)x.size())
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define mp make_pair
#define ff first
#define ss second
#define M 1000000007          // 1e9+7
#define INF 1e9    // 1e9
 
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;
typedef vector<ii> vii;
typedef vector<ll> vi;
typedef vector<int> vint;
typedef vector<string> vs;
typedef vector<vi> vvi;
 
bool cus(pair<int,int> a, pair<int,int> b){
    if(a.ff<b.ff)
        return true;
    if(a.ff>b.ff)
        return false;
    return a.ss<b.ss;
}
 
ll gcd(ll a, ll b){
    if(b==0)
        return a;
    return gcd(b,a%b);
}

bool edg[19][19];
bool valid[1 << 18];
	
void solve(){
    ll n, m;
    cin >> n >> m;

    ll a, b;
    rep(i, m){
        cin >> a >> b;
        --a, --b;
        edg[a][b] = true;
        edg[b][a] = true;
    }

    for(ll i = 1; i < (1 << n); ++i){
    	vi tmp;
    	rep(j, 18){
    		if(i & (1 << j)) tmp.pb(j);
    	}

    	bool flg = true;
    	rep(j, tmp.size()){
    		rep(k, j){
    			if(!edg[tmp[j]][tmp[k]]) flg = false;
    		}
    	}
    	valid[i] = flg;
    }

    //debug("here");

    ll dp[1 << n];
    rep(i, 1 << n) dp[i] = INF;
    dp[0] = 0;
    fr(i, 1, (1<<n)-1){
    	if(valid[i]) dp[i] = 1;
    	else {
    		for(ll j = i;j;j = (j-1)&i){
    			dp[i] = min(dp[i], dp[j]+dp[i^j]);
    		}
    	}
    }

    cout << dp[(1 << n)-1] << endl;
}

int main () 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout<<setprecision(11);
 
    //ll t = 1;
    //cin>>t;
    //while(t--)
        solve();
 
    return 0;
}

#include <bits/stdc++.h>
 
#define INF 10000000000000000LL

constexpr long long MOD = 1000000007;

//Get-Content input | ./a.exe > output
 
using namespace std;
 
void redirect_io() {
    freopen("input", "r", stdin);
    // freopen("output", "w", stdout);
}
 
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
 
template <typename Head>
void print(Head&& h) {
    std::cout << h << std::endl;
}
 
template <typename Head, typename... Tail>
void print(Head&& h, Tail&&... t) {
    std::cout << h << " ";
    print(std::forward<Tail&&>(t)...);
}


int main() {
    // redirect_io();
    fast_io();
	int n, q, k, t, m, a, b;
    cin >> n >> m;
    vector<vector<int>> gr(n, vector<int>(n));
    for(int i = 0; i < m; i++) {
        cin >> a >> b;
        a--;b--;
        gr[a][b] = gr[b][a] = 1;
    }

    int mx = (1 << n);
    vector<int> f(mx, MOD);

    for(int i = 1; i < mx; i++) {
        vector<int> nodes;
        for(int j = 0; j < n; j++) {
            if((i >> j) & 1) {nodes.push_back(j);}
        }
        f[i] = 1;
        for(int j = 0; j < nodes.size(); j++) {
            for(int k = j + 1; k < nodes.size(); k++) {
                if(gr[nodes[j]][nodes[k]] == 0) {f[i] = MOD; break;}
            }
        }
    }
    f[0] = 0;

    for(int i  = 0; i < mx; i++) {
        for(int j = i; j > 0; j = (j - 1) & i) {
            f[i] = min(f[i],  f[j] +  f[i ^ j]);
        }
    }

    cout << f[mx - 1] << "\n";

    return 0;
}