#ifdef _LOCAL
#	include <dbg_print.h>
#else
#	define NDEBUG
#	define dprint(...)
#endif

#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef long long ll;

bool connected[32][32] = {0};
int n, m;

int check_hist[1<<18] = {0};

bool check(int nodes)
{
	if(check_hist[nodes])
		return (check_hist[nodes] == 2);

	for(int i=0; i<n; ++i)
	{
		if(nodes & (1<<i))
		{
			for(int j=0; j<i; ++j)
			{
				if(nodes & (1<<j))
				{
					if(!connected[i][j])
					{
						check_hist[nodes] = 1;
						return false;
					}
				}
			}
		}
	}

	check_hist[nodes] = 2;
	return true;
}


int hist[1<<18] = {0};

int solve(int nodes)
{
	assert(nodes);

	if(hist[nodes])
		return hist[nodes];

	if(check(nodes))
		return 1;

	int n1 = __builtin_popcount(nodes);
	int res = 999;

	for(int submask=1; submask<(1<<n1); ++submask)
	{
		int mask = 0;
		for(int i=0,j=0; i<n; ++i) if(nodes & (1<<i))
		{
			if((submask>>j)&1)
				mask |= (1<<i);
			++j;
		}
		if(!check(mask))
			continue;

		int r = 1 + solve(nodes & (~mask));
		res = std::min(res, r);
	}

	return hist[nodes] = res;
}


int solve2(int fullMask, int i0, int currMask)
{
	if(!fullMask)
		return 0;

	if(currMask == 0)
	{
		if(hist[fullMask])
			return hist[fullMask];

		if(check(fullMask))
			return 1;
	}

	int res = 999;
	if(currMask)
		res = 1 + solve2(fullMask & (~currMask), 0, 0);

	for(int i=i0; i<n; ++i) if(fullMask & (1<<i))
	{
		currMask |= (1<<i);
		
		if(check(currMask))
		{
			int r = solve2(fullMask, i+1, currMask);
			res = std::min(res, r);
		}

		currMask &= ~(1<<i);
	}

	if(currMask == 0)
		hist[fullMask] = res;

	return res;
}


int main()
{
	ios::sync_with_stdio(false);
	
	cin >> n >> m;
	for(int i=0; i<m; ++i)
	{
		int u, v;
		cin >> u >> v;
		--u, --v;
		connected[u][v] = connected[v][u] = 1;
	}

	int ans = solve2((1<<n)-1, 0, 0);
	cout << ans << "\n";

	return 0;
}

#include <bits/stdc++.h>
using namespace std;
//using namespace atcoder;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define pb push_back
#define fi first
#define se second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void chOut(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using v_bool = vector<bool>;
using v_Pii = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;



signed main(){

    int N, M; cin >> N >> M;
    vec A(M), B(M);
    bool f[18][18] = {};
    REP(i, M){
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
        f[A[i]][B[i]] = true;
        f[B[i]][A[i]] = true;
    }

    v_bool ok(bit(N), false);
    FOR(b, 1, bit(N)){
        bool t = true;
        REP(i, N) REP(j, i) if((b >> i) & (b >> j) & 1){
            if(!f[i][j]) t = false;
        }
        ok[b] = t;
    }

    vec dp(bit(N), INF);
    dp[0] = 0;
    FOR(sup, 1, bit(N)){
        int sub = sup;
        do{
            if(ok[sub]){
                chmin(dp[sup], dp[sup ^ sub] + 1);
            }
            sub = (sub - 1) & sup;
        }while(sub != sup);
    }
    Out(dp[bit(N) - 1]);

    return 0;
}
