#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#ifdef WIN_32
#define getchar_unlocked _getchar_nolock
#endif
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, M, A, B, cnt, mem[1 << 20], link[25], sz[25], tmpmap[25];
bool good[1 << 20];
bool C[25][25];

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[a] < sz[b]) swap(a, b);
	sz[a] += sz[b];
	link[b] = a;
}

bool is(int bm) {
	vector<int> tmp;
	for (int i = 0; i < N; i++)
		if (bm & (1 << i)) tmp.pb(i + 1);
	for (int i : tmp)
		for (int j : tmp)
			if (i != j && !C[i][j]) return 0;
	return 1;
}

int dp(int bm) {
	if (mem[bm] != -1) return mem[bm];
	if (bm == 0) return 0;
	int ans = 1e9;
	for (int s = bm; s; s = (s - 1) & bm)
		if (good[s]) ans = min(ans, 1 + dp(bm ^ s));
	return mem[bm] = ans;
}

main() {
	memset(mem, -1, sizeof mem);
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	for (int i = 1; i <= M; i++) {
		cin >> A >> B;
		C[A][B] = C[B][A] = 1;
	}
	for (int i = 1; i <= N; i++)
		for (int j = i + 1; j <= N; j++)
			if (!C[i][j]) {
				//cout << i << ' ' << j << '\n';
				unite(i, j);
			}
	for (int i = 0; i < (1 << N); i++) {
		good[i] = is(i);
		//if (good[i]) cout << i << '\n';
	}
	cout << dp((1 << N) - 1) << '\n';
}

#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define rep(i, n) for(int i=0;i<n;i++)
#define all(i, v) for(auto& i : v)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n, m, a, b;
    cin >> n >> m;
    bool ok[n][n];
    memset(ok, 0, sizeof(ok));
    rep(i, m){
        cin >> a >> b;
        a--; b--;
        ok[a][b] = ok[b][a] = true;
    }
    rep(i, n) ok[i][i] = true;
    m = 1 << n;
    bool connect[m];
    memset(connect, 0, sizeof(connect));
    connect[0] = 1;
    rep(bit, m){
        rep(i, n) if(bit >> i & 1){
            if(!connect[bit - (1 << i)]) continue;
            bool c = true;
            rep(j, n) if(bit >> j & 1){
                if(!ok[i][j]) c = false;
            }
            if(c){
                connect[bit] = true;
                break;
            }
        }
    }


    int cost[m];
    rep(i, m) cost[i] = 20;
    cost[0] = 0;
    rep(bit, m){
        if(connect[bit]) {
            cost[bit] = 1;
            continue;
        }
        int i = (bit - 1) & bit;
        for(;i>=1;i=(i-1)&bit){
            cost[bit] = min(cost[bit], cost[i] + cost[bit - i]);
        }
    }
    cout << cost[m - 1] << endl;
    return 0;
}


