#include <bits/stdc++.h>
using namespace std;
set<int> s, g[100005];
set<int>::iterator it;
int ara[100005], sz[100005], vis[100005];
void initset(int n) {
  for (int i = 1; i <= n; i++) {
    ara[i] = i;
    sz[i] = 1;
    vis[i] = 0;
    g[i].clear();
  }
  s.clear();
}
int findset(int i) {
  if (ara[i] == i) return i;
  return ara[i] = findset(ara[i]);
}
bool issameset(int i, int j) { return (findset(i) == findset(j)); }
void unionset(int i, int j) {
  int a = findset(j);
  int b = findset(i);
  if (a == b) return;
  if (sz[a] >= sz[b]) {
    sz[a] += sz[b];
    ara[b] = a;
  } else {
    sz[b] += sz[a];
    ara[a] = b;
  }
}
vector<int> v;
priority_queue<pair<int, int>, vector<pair<int, int> >,
               greater<pair<int, int> > >
    pq;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int n, m;
  while (cin >> n >> m) {
    initset(n);
    for (int i = 1; i <= m; i++) {
      int a, b;
      cin >> a >> b;
      g[a].insert(b);
      g[b].insert(a);
    }
    for (int i = 1; i <= n; i++) {
      s.insert(i);
      int l = g[i].size();
      pq.push({l, i});
    }
    while (!pq.empty()) {
      pair<int, int> p = pq.top();
      pq.pop();
      if (vis[p.second]) continue;
      queue<int> q;
      q.push(p.second);
      while (!q.empty()) {
        int a = q.front();
        q.pop();
        if (vis[a]) continue;
        vis[a] = 1;
        for (it = s.begin(); it != s.end(); it++) {
          if (g[a].count(*it) == 0) {
            if (!issameset(a, *it)) {
              unionset(a, *it);
              v.push_back(*it);
              q.push(*it);
            }
          }
        }
        for (auto u : v) s.erase(u);
        v.clear();
      }
    }
    memset(vis, 0, sizeof vis);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
      int a = findset(i);
      if (!vis[a]) {
        ans++;
        vis[a] = 1;
      }
    }
    cout << ans - 1 << endl;
  }
  return 0;
}
