#include <bits/stdc++.h>

using namespace std;
#define int long long
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    int m;
    cin>>m;
    int a[n][n];
    for(int i=0;i<n;++i) for(int j=0;j<n;++j) {a[i][j]=0;if(i==j) a[i][j]=1;}
    for(int i=0;i<m;++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        a[x][y]=1;
        a[y][x]=1;
    }
    bool ok[1<<n];
    for(int mask=0;mask<(1<<n);++mask)
    {
        int sum=0;
        vector <int> v;
        for(int i=0;i<n;++i)
        {
            if(mask & (1<<i))
            {
                v.push_back(i);
            }
        }
        for(int i=0;i<v.size();++i) for(int j=0;j<v.size();++j) sum+=a[v[i]][v[j]];
        ok[mask]=(sum==(v.size()*v.size()));
    }
    int res[1<<n];
    res[0]=0;
    for(int mask=1;mask<(1<<n);++mask)
    {
        if(ok[mask])
        {
            res[mask]=1;
            continue;
        }
        res[mask]=1e18;
        for(int i=mask;;i=((i-1) & mask))
        {
            if(ok[i])
            {
                res[mask]=min(res[mask],res[mask^i]+1);
            }
            if(i==0)
            {
                break;
            }
        }
    }
    cout<<res[(1<<n)-1];
    return 0;
}

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <functional>
#include <bitset>
#include <limits>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <random>

#ifdef DEBUG
#include "library/Utility/debug.cpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i=0;i<(n);++i)
#define EL '\n'
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using lnt = long long;
struct FIO{FIO(){std::cin.tie(0);std::ios_base::sync_with_stdio(0);std::cout<<std::fixed<<std::setprecision(15);}}fIO;
template<typename T> using V = std::vector<T>;
template<typename T> void fill(V<T>&v) { for(T&e:v) std::cin >> e; }
/*-*/

int main() {
	int n,m;
	std::cin >> n >> m;
	V<V<int> > g(n,V<int>(n,0));
	rep(i,n) g[i][i]=1;
	rep(i,m) {
		int a,b;
		std::cin >> a >> b;
		a--;b--;
		g[a][b]=1;
		g[b][a]=1;
	}
	V<lnt> comp(1<<n,0);
	rep(i,1<<n) {
		int ok=true;
		rep(j,n) {
			rep(k,n) {
				if((i>>j&1)&&(i>>k&1)&&g[j][k]==0) ok=false;
			}
		}
		comp[i]=ok;
	}
	V<lnt> dp(1<<n,n);
	rep(S,1<<n) {
		if(comp[S]) {
			dp[S]=1;
			continue;
		}
		for(int T=(S-1)&S;T>0;T=(T-1)&S) {
			dp[S]=std::min(dp[S],dp[T]+dp[S^T]);
		}
	}
	print(dp[(1<<n)-1]);
}
