#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << '\n'; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

int popcount(int n) {
    int res = 0;
    while (n) {
        res += (n & 1);
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin, n, m;
    vector<int> edges(n, 0);
    rep(i, 0, m) {
        int a, b;
        cin, a, b;
        a--;
        b--;
        edges[a] |= (1 << b);
        edges[b] |= (1 << a);
    }
    int sz = 1 << n;
    vector<bool> clique(sz, false);
    rep(mask, 0, sz) {
        int msk = mask;
        rep(i, 0, n) {
            if ((mask >> i) & 1) {
                msk &= (edges[i] | (1 << i));
            }
        }
        clique[mask] = msk == mask;
    }

    const int inf = n + 1;
    vector<int> dp(sz, inf);
    rep(i, 0, sz) {
        if (clique[i]) {
            dp[i] = 1;
        }
    }
    rep(i, 0, sz) {
        for (int j = i;; j = (j - 1) & i) {
            int k = i ^ j;
            chmin(dp[i], dp[j] + dp[k]);
            if (j == 0) break;
        }
    }
    print(dp[sz - 1]);

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int g[N][N];
int dp[1<<N];
bool ok[1<<N];
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		x--,y--;
		g[x][y]=g[y][x]=1;
	}
	for(int i=0;i<(1<<n);i++)
	{
		vector<int> e;
		for(int j=0;j<n;j++)
		{
			if(i>>j&1) e.push_back(j);
		}
		 ok[i]=true;
		for(int j=0;j<e.size();j++)
		for(int k=j+1;k<e.size();k++)
		if(!g[e[j]][e[k]])
		{
			ok[i]=false;
		}
	}
	for(int i=0;i<(1<<n);i++) dp[i]=n+1;
	dp[0]=0;
	for(int i=1;i<(1<<n);i++)
	{
		if(ok[i]) dp[i]=1;//只有一块 
		for(int j=i;j;j=(j-1)&i)
		dp[i]=min(dp[i],dp[j]+dp[i^j]);
	}
	cout<<dp[(1<<n)-1];
	return 0;
}