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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using LD = long double;

template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <typename T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <typename T> void coutall(T v) { if(v.empty()){cout << endl; return;} for(auto i = v.begin(); i != --v.end(); i++){cout << *i << " ";} cout << *--v.end() << endl; }
template <typename T> void DEBUGall(T v) { if(v.empty()){cerr << endl; return;} for(auto i = v.begin(); i != --v.end(); i++){cerr << *i << " ";} cerr << *--v.end() << endl; }
inline void IN(void){ return; }
template <typename First, typename... Rest> void IN(First& first, Rest&... rest){ cin >> first; IN(rest...); return; }
inline void OUT(void){ cout << "\n"; return; }
template <typename First, typename... Rest> void OUT(First first, Rest... rest){ cout << first << " "; OUT(rest...); return; }
inline void DEBUG(void){ cerr << "\n"; return; }
template <typename First, typename... Rest> void DEBUG(First first, Rest... rest){ cerr << first << " "; DEBUG(rest...); return; }

void yes(bool ok = true){ cout << (ok ? "yes" : "no") << endl; }
void Yes(bool ok = true){ cout << (ok ? "Yes" : "No") << endl; }
void YES(bool ok = true){ cout << (ok ? "YES" : "NO") << endl; }
ll myceil(ll a, ll b) { return a >= 0 ? (a+b-1)/b : -((-a)/b); }
ll myfloor(ll a, ll b) { return a >= 0 ? a/b : -myceil(-a, b); }

map<int, int> compress(vi a){
    int n = a.size();
    map<int, int> cnt;
    rep(i, n) cnt[a[i]] = 1;
    int now = 0;
    for(auto [k, v] : cnt){
        cnt[k] = now;
        now++;
    }
    return cnt;   
}

void Main(){
    int n, m; IN(n, m);
    vi x(m), y(m);
    rep(i, m) IN(x[i], y[i]);
    map<int, int> c = compress(x);    
    int sz = c.size();
    vvi black(sz);
    rep(i, m) {
        black[c[x[i]]].pb(y[i]);
    }
    
    set<int> st;
    st.insert(n);
    
    for(auto b : black){
        vi stadd, stdel;
        for(auto pos : b){
            if(st.find(pos-1) != st.end() || st.find(pos+1) != st.end()) stadd.pb(pos);
            if(st.find(pos-1) == st.end() && st.find(pos+1) == st.end()) stdel.pb(pos);
        }
        for(auto aa : stadd) st.insert(aa);
        for(auto bb : stdel) {
            auto it = st.find(bb);
            if(it != st.end()) st.erase(it);
        }
    }
    OUT(st.size());
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=20;

int main(){
	ll n,m;cin>>n>>m;
	vector<ll> g(n);
	while(m--){
		ll a,b;cin>>a>>b;a--;b--;
		g[a]|=(1<<b);
		g[b]|=(1<<a);
	}
	vector<ll> d(1<<n,INF);
	d[0]=1;
	for(ll i=0;i<n;i++)for(ll j=0;j<(1<<n);j++)if(d[j]==1 && (g[i]&j)==j)d[j|(1<<i)]=1;
	for(ll i=1;i<(1<<n);i++)for(ll j=i;j;j--,j&=i)d[i]=min(d[i],d[i^j]+d[j]);
	cout<<d[(1<<n)-1]<<endl;
}
