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

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define fr(i,k,n) for (int i = k; i < n; ++i)
#define fri(i,k,n) for (int i = k; i >= n; --i)
#define pb push_back
#define mp make_pair
#define all(arr) arr.begin(),arr.end()
#define ff first
#define ss second

const double pi=3.1415926535897932384626433832795;
const int inf=1e9;
const ll inf2=1e18;
const int mod=1e9+7;

void boost(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

int adj[20][20],n;
vi dp(1<<20,inf);

void solve(){
	int m;
	cin>>n>>m;
	int u,v;
	fr(i,0,m){
		cin>>u>>v;
		u--;
		v--;
		adj[u][v]=adj[v][u]=1;
	}
	for(int i=1;i<(1<<n);i++){
		if(!(i&(i-1))){
			dp[i]=1;
			continue;
		}
		dp[i]=1;
		for(int j=0;j<n;j++){
			if((i>>j)&1){
				for(int k=j+1;k<n;k++){
					if((i>>k)&1){
						if(adj[j][k]==0)
							dp[i]=inf;
					}
				}
			}
		}
		for(int j=(i-1)&i;j;j=(j-1)&i){
			dp[i]=min(dp[i],dp[j]+dp[i^j]);
		}
	}
	cout<<dp[(1<<n)-1]<<endl;
	return;
}

int main()
{
	boost();
	
	int tc=1;
	//cin>>tc;
	while(tc--)
		solve();
	return 0;
}
#ifdef Prateek
  #include "Prateek.h"
#else
  #include <bits/stdc++.h>
  using namespace std;
  #define debug(...) 42
#endif
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
const int MOD = 1e9+7, N = 20; 

int g[N][N];
int n, m;
int dp[(1 << N)];

int dfs(int mask) {
   // debug(mask);
   int &ans = dp[mask];
   if (ans != -1) return ans;
   if (__builtin_popcount(mask) == 1) return ans = 1;
   if (__builtin_popcount(mask) == 2) {
      for (int i = 0; i < n; ++i) {
         for (int j = i + 1; j < n; ++j) {
            if ((mask >> i & 1) and (mask >> j & 1)) {
               if (g[i][j]) return ans = 1;
               return ans = 1e9;
            }
         }
      }
      assert(false);
   }
   int chk = 1;
   for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
         if ((mask >> i & 1) and (mask >> j & 1)) {
            if (!g[i][j]) {
               chk = 0;
               break;
            }
         }
      }
      if (!chk) break;
   }
   if (chk) {
      return ans = 1;
   }
   ans = 1e9;
   for (int s = mask; s; s = (s - 1) & mask) {
      if (s == mask) continue;
      // debug(s, mask ^ s);
      ans = min(ans, dfs(s) + dfs(mask ^ s));
   }
   return ans;
}

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   memset(dp, -1, sizeof dp);
   cin >> n >> m;
   for (int i = 0; i < m; ++i) {
      int x, y;
      cin >> x >> y;
      --x, --y;
      g[x][y] = g[y][x] = 1;
   }
   int mask = (1 << n) - 1;
   int ans = dfs(mask);
   if (ans > n) ans = n;
   cout << ans << '\n';
   return 0;
} 