#include <bits/stdc++.h>
using namespace std;
struct Node {
  Node() : vis(0) {}
  set<int> adj;
  int vis;
};
struct DSU {
  DSU(int parent = -1) : parent(parent), size(1) {}
  int parent;
  int size;
};
int find_set(vector<DSU>& a, int v) {
  if (v == a[v].parent) return v;
  return a[v].parent = find_set(a, a[v].parent);
}
void union_sets(vector<DSU>& a, int u, int v) {
  u = find_set(a, u);
  v = find_set(a, v);
  if (u != v) {
    if (a[u].size < a[v].size) swap(u, v);
    a[v].parent = u;
    a[u].size += a[v].size;
  }
}
void analyze(vector<Node>& a, vector<DSU>& b, int index) {
  queue<int> q;
  int n = a.size();
  int u = index;
  a[u].vis = true;
  set<int> possible;
  possible.insert(index);
  while (possible.size() > 0) {
    int u = *possible.begin();
    possible.erase(possible.begin());
    a[u].vis = true;
    for (int v = 0; v < n; v++) {
      if (v == u) continue;
      if (a[v].vis == 0) {
        if (a[u].adj.find(v) == a[u].adj.end()) {
          union_sets(b, u, v);
          if (possible.find(v) != possible.end()) {
            possible.erase(v);
          }
          q.push(v);
        } else {
          possible.insert(v);
        }
      }
    }
    while (q.size() > 0) {
      int u = q.front();
      q.pop();
      a[u].vis = true;
      for (set<int>::iterator it = possible.begin(); it != possible.end();) {
        if (a[u].adj.find(*it) == a[u].adj.end()) {
          union_sets(b, u, *it);
          q.push(*it);
          it = possible.erase(it);
        } else
          it++;
      }
    }
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<Node> a(n);
  vector<DSU> b;
  b.reserve(n);
  vector<int> d(n);
  for (int i = 0; i < n; i++) b.push_back(DSU(i));
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    a[u].adj.insert(v);
    a[v].adj.insert(u);
    d[u]++;
    d[v]++;
  }
  auto it = min_element(d.begin(), d.end());
  int index = it - d.begin();
  analyze(a, b, index);
  set<int> sets;
  for (int i = 0; i < n; i++) {
    sets.insert(find_set(b, i));
  }
  cout << sets.size() - 1 << endl;
  return 0;
}
