//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const ll maxn=100050;
const ll mod=1e9+7;



int main(){
    fast;
	int n,m,i,j,k,u,v,mask;
	cin >> n >> m;	
	vector<set<int>> g(20);
	for(i=0;i<m;i++){
		cin >> u >> v;
		--u,--v;
		g[u].insert(v);
		g[v].insert(u);
	}
	vector<bool> can(1<<n,true);
	for(mask=0;mask<(1<<n);++mask){
		vector<int> str;
		for(j=0;j<n;j++){
			if(mask&(1<<j))
				str.pb(j);
		}
		for(i=0;i<str.size();++i){
			for(j=i+1;j<str.size();++j){
				if(g[str[i]].count(str[j])==false){
					can[mask]=false;
					break;
				}
			}
		}
	}
	vector<int> dp(1<<n,1e9);
	dp[0]=0;
	//dp[mask]-> minimum number of connected components formed from mask subset of nodes.
	for(i=0;i<(1<<n);i++){
		if(can[i])
			dp[i]=1;
		else{
			for(j=i;j;j=(j-1)&i){
				dp[i]=min(dp[i],dp[j]+dp[i^j]);
			}
		}
	}
	cout<<dp[(1<<n)-1];
}

 


#include<bits/stdc++.h>
using namespace std;

struct fastio{fastio(){cin.tie(nullptr);ios_base::sync_with_stdio(false);std::cout<<std::fixed<<setprecision(10);}}oitsaf;
#define rep(i,n) for(int i=0;i<int(n);++i)
constexpr int inf = 1<<28;
constexpr char newl = '\n';
template<class T>std::istream&operator>>(std::istream&is,std::vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T>std::ostream&operator<<(std::ostream&os,std::vector<T>const&v){for(auto const& vi:v)os<<vi<<" ";return os;}
#if _local
struct debug_structure{template<class T>debug_structure&operator<<(const T&elm){std::cerr<<elm<<std::flush;return*this;}}dout;
#else
struct debug_structure{template<class T>debug_structure&operator<<(const T&elm){return*this;}}dout;
#endif
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> adj(n);
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    adj[a] |= 1 << b;
    adj[b] |= 1 << a;
  }
  vector<int> dp(1 << n, inf);
  rep(S, 1 << n) {
    bool kn = true;
    rep(i, n) if ((S >> i) & 1) kn &= ((adj[i] | 1 << i) & S) == S;
    if (kn)
      dp[S] = 1;
  }
  rep(S, 1 << n) {
    for (int T = S;; T = (T - 1) & S) {
      if (T == 0)
        break;
      chmin(dp[S], dp[S ^ T] + dp[T]);
    }
  }
  cout << (dp.back()) << endl;
  rep(i, 1 << n) dout << i << ":" << bitset<10>(i) << ":" << dp[i] << newl;
}