#include <iostream>
#include <vector>
#include <set>
#include <bitset>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	vector<set<int>> Graph(N);
	vector<int> A(M), B(M);
	for (int i = 0; i < M; i++) cin >> A[i] >> B[i], A[i]--, B[i]--;
	for (int i = 0; i < M; i++) {
		Graph[A[i]].insert(B[i]);
		Graph[B[i]].insert(A[i]);
	}

	vector<bool> comp(1 << N, false);
	for (int i = 0; i < N; i++) {
		comp[1 << i] = true;
	}
	for (int i = 1; i < (1 << N); i++) {
		if (!comp[i]) continue;
		for (int j = 0; j < N; j++) {
			if (i & (1 << j)) continue;
			bool judge = true;
			for (int k = 0; k < N; k++) {
				if ((i & (1 << k)) && !(Graph[j].count(k))) judge = false;
			}
			if (judge) comp[i | (1 << j)] = true;
		}
	}

	vector<int> dp(1 << N, 18);
	dp[0] = 0;
	for (int i = 0; i < (1 << N); i++) {
		int revi = (((1 << N) - 1) ^ i);
		for (int j = revi; j &= revi; j--) {
			if (comp[j]) {
				dp[i ^ j] = min(dp[i ^ j], dp[i] + 1);
			}
		}
	}

	cout << dp[(1 << N) - 1] << endl;
}
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define bit(n,k) ((n>>k)&1) //nのk　bit目
#define vec(T) vector<T>
#define vvec(T) vec(vec(T))
using ll = long long;
using P = pair<int,int>;


template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll llINF = 1LL << 60;
const int iINF = 1e9;

//------------------------------------------------
struct Solver{
    void solve(){
        int N,M;
        cin >> N >> M;

        vec(int) ed(N); //ある頂点から辺のつながってる先リスト

        rep(i,M){
            int a,b;
            cin >> a >> b;
            --a; --b;
            ed[a] |= 1<<b; // ビットで情報を保存
            ed[b] |= 1<<a;
        }

        vec(int) dp(1<<N, iINF);
        dp[0]=1;

        // 全結合の集合のとこを1に初期化
        rep(si,1<<N)rep(ni,N){
            // siが全結合かつsiの集合に頂点niを足しても全結合なら1
            if( dp[si]==1 && (ed[ni]&si)==si ) dp[si | 1<<ni] = 1;
        }

        // dp
        rep1(si,(1<<N)-1){
            for(int sj=si; (--sj)&=si  ; ){

                if( sj&si ) chmin(dp[si], dp[si^sj]+dp[sj]);
            }
        }
        cout << dp.back() << endl;

    }
};


int main(){
    int testcasenum=1;
    //cin >> testcasenum;
    rep1(ti,testcasenum){
        Solver solver;
        solver.solve();
    }
    return 0;
}