#include <bits/stdc++.h>
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define int long long
#define ft first
#define sc second
#define pt(sth) cout << sth << "\n"
#define moca(a, s, b) a=((a)s(b)+MOD)%MOD
#define rep(i,n) for (int i=0;i<n;i++)
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
template<class T>bool chmax(T &a, const T &b) {if(a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if(b<a) {a=b; return 1;} return 0;}
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;



//for(i=0; i<N; i++) cin >> a[i];

signed main(void) {
  int n,m;
  cin>>n>>m;
  vector<vector<int>> root(n+1,vector<int>(n+1,0));
  rep(i,m){
    int a,b;
    cin>>a>>b;
    a-=1;
    b-=1;
    root[a][b]=1;
    root[b][a]=1;
  }
  vector<int> dp(1<<n,100000000);
  for (int s=1;s<(1<<n);s++){
    int bit[n];
    rep(i,n){
      bit[i]=(s>>i)&1;
    }
    

    bool flag=true;
    rep(l,n-1){
      for (int r=l+1;r<n;r++){
        
        if ((bit[l]==1 && bit[r]==1) && root[l][r]==0){
          
          flag=false;
        }
      }
    }
    if (flag==true){
      dp[s]=1;
      continue;
    }
    int t=(s-1)&s;
    while (t>0){
      dp[s]=min(dp[s],dp[s-t]+dp[t]);
      t=(t-1)&s;
    }
    
  }
  pt(dp[pow(2,n)-1]);
}

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

#define ll long long
#define ar array

const int mxN = 18;
int n, m, dp[1 << mxN];
bool e[mxN][mxN], trans[1 << mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >> b, --a, --b;
		e[a][b] = e[b][a] = 1;
	}
	for (int i = 1; i < (1 << n); ++i) {
		vector<int> v; v.reserve(n);
		for (int j = 0; j < n; ++j) if (i & (1 << j)) v.push_back(j);
		trans[i] = 1;
		for (int j = 0; j < v.size() && trans[i]; ++j) for (int k = j + 1; k < v.size() && trans[i]; ++k)
			trans[i] &= e[v[j]][v[k]];
	}
	fill(dp, dp + (1 << n), 1e9);
	dp[0] = 0;
	for (int i = 0; i < (1 << n); ++i) {
		int mask = i ^ ((1 << n) - 1);
		for (int s = mask; s; s = (s - 1) & mask)
			if (trans[s])
				dp[i | s] = min(dp[i | s], dp[i] + 1);
	}
	cout << dp[(1 << n) - 1];
	return 0;
}
