#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=b;i>=a;i--)
const ll INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
const int inf=0x3f3f3f3f,maxn=1e5+500;
const double pi=3.1415926535;
bool cmp(ll x,ll y)
{
    return x<y;
}
ll n,m,t,ans,a[2*maxn],b[maxn*2]={0},cnt=0;
int main()
{
   scanf("%lld%lld",&n,&m);
   fo(i,0,m-1)scanf("%lld",&a[i]);
   a[m++]=n+1;
   a[m++]=0;
   sort(a,a+m,cmp);
   ll mi=n;
   fo(i,1,m-1){
       ll x=a[i]-a[i-1];
   if(x&&x!=1)b[cnt++]=x-1,mi=min(mi,x-1);
   }
   if(!mi)ans=0;
   else {
   ans=0;
   fo(i,0,cnt-1)
   {
   //    printf("%lld ",b[i]);
       ans+=b[i]/mi;
       if(b[i]%mi)ans++;
   }

   }
   printf("%lld\n",ans);
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <limits>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
using namespace std;
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(a > b){ a = b; return 1; } return 0; }
template<class T> inline int  sz(T &a) { return a.size(); }
using ll = long long; using ld = long double;
using pi = pair<int,int>; using pl = pair<ll,ll>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
const int inf = numeric_limits<int>::max();
const ll infll = numeric_limits<ll>::max();
int main()
{
  int n,m; cin >> n >> m;
  vvi edge(n, vi(n, 0));
  rep(i,m) {
    int a,b; cin >> a >> b;
    a--; b--;
    edge[a][b] = 1;
    edge[b][a] = 1;
  }

  vi tab((1<<n), 0);
  tab[0] = 1;
  rep(S, (1<<n)) {
    if(tab[S]) {
      rep(i,n) {
	bool f = true;
	rep(j,n) {
	  if((S>>j)&1) {
	    if(!edge[i][j]) f = false;
	  }
	}
	if(f) tab[S|(1<<i)] = 1;
      }
    }
  }

  //  rep(i,sz(tab)) cout << i << ":" << tab[i] << "\n";
  
  vl dp((1<<n), -1);
  auto rec = [&](auto self, int mask)->int {
    //    cout << bitset<8>(mask) << "\n";
    if(dp[mask] >= 0) return dp[mask];
    if(tab[mask]) return dp[mask] = 1;
    int res = 50;
    for(int i=mask;i>0;i=(i-1)&mask){
      if(i == mask) continue;
      int tmp =  self(self, i) + self(self, mask-i);
      chmin(res, tmp);
    }
    return dp[mask] = res;
  };

  int ans = rec(rec, (1<<n)-1);
  cout << ans << "\n";
  
  return 0;
}
