#include <iostream>
#include <vector>
#include <limits>
#include <cstring>
#include <time.h>
#include <math.h>
#include <algorithm>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii > vii;
typedef vector<vector<ll> > vvi;
typedef vector<vvi > vvvi;
typedef vector<vector<pair<ll, ll> > > vvii;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,s,e) for(ll i=(s);i<(e);++i)
#define repr(i,s,e) for(ll i=(e);i>(s);--i)
#define io ios::sync_with_stdio(false)
#define prv(v)                                                             \
	do                                                                      \
	{                                                                       \
		for(auto it = (v).begin(); it != (v).end(); ++it) cerr << *it << " "; \
		cerr << endl; \
	} while (0);
#define prm(m)                                           \
	do                                                     \
	{                                                      \
		for (auto it = (m).begin(); it != (m).end(); ++it)   \
			cerr << it->first << " -> " << it->second << endl; \
	} while (0);

const ll MOD = 1e9+7;
const ll INF = 100;
const ll TE3 = 1005;
const ll TE5 = 300005;
const string YN[2] = {"NO", "YES"};

using namespace std;

ll n, m;
ll f(vi &dp,vi &s,ll x,ll m) {
	if(binary_search(s.begin(), s.end(), x)) {
		return 1;
	}
	if(dp[x]!=-1) {
		return dp[x];
	}
	ll y = x;
	ll ans = INF;
	ll q = s.size();
	for (ll i = m-1; i >= 0;--i) {
		if((s[i]&y)==y) {
			ans = min(ans, 1 + f(dp, s, y-s[i], i-1));
		}
	}
	return dp[x] = ans;
}

int main()
{
	io;
	cin >> n >> m;
	vvi a(n, vi(n, 0));
	rep(i, 0, m)
	{
		ll x, y;
		cin >> x >> y;
		--x;
		--y;
		a[x][y] = 1;
		a[y][x] = 1;
	}
	ll z = 1ll << n;
	vi dp(z,n);
	rep(i, 0, z)
	{
		dp[i] = __builtin_popcount(i);
		ll j = i;
		vi o;
		ll c = 0;
		while (j)
		{
			if(j&1) {
				o.pb(c);
			}
			j = j >> 1;
			++c;
		}
		bool sc = true;
		for (ll t1 : o)
		{
			for(ll t2: o) {
				if(t1==t2||a[t1][t2]) {

				} else {
					sc = false;
					break;
				}
			}
			if(!sc) {
				break;
			}
		}
		if(sc && o.size()) {
			dp[i] = 1;
		}
	}
	rep(i,0,z) {
		for (ll t = i; t > 0;t=(t-1)&i) {
			dp[i] = min(dp[i], dp[t] + dp[i ^ t]);
		}
	}
	cout << dp[z-1] << endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,e[25][25],f[1<<19];
vector<int> v;
int main()
{
	int x,y;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		e[x][y]=e[y][x]=1;
	}
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<(1<<n);i++)
	{
		v.clear();
		for(int j=1;j<=n;j++)if(i&(1<<(j-1)))v.push_back(j);
		f[i]=1;
		for(int j=0;j<v.size();j++)
		{
			for(int k=j+1;k<v.size();k++)if(!e[v[j]][v[k]])f[i]=f[0];
		}
	}
	for(int i=1;i<(1<<n);i++)
	{
		for(int j=i;j;j=(j-1)&i)f[i]=min(f[i],f[j]+f[i^j]);
	}
	printf("%d\n",f[(1<<n)-1]);
	return 0;
}