#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
priority_queue<pair<int, int>, vector<pair<int, int> >,
               greater<pair<int, int> > >
    sp;
template <typename T>
void read(T &x) {
  int p = 1;
  x = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') p = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - 48;
    c = getchar();
  }
  x *= p;
}
int fir[N], nxt[N], to[N], tot;
void add_edge(int x, int y) {
  nxt[++tot] = fir[x];
  fir[x] = tot;
  to[tot] = y;
}
bool vis[N];
int pt, rd[N];
int find() {
  while (vis[sp.top().second] || rd[sp.top().second] != sp.top().first)
    sp.pop();
  int x = sp.top().second;
  vis[x] = 1;
  return x;
}
int main() {
  long long n, m, x, y, s;
  long long sum = 0, now = 0, ans = 0;
  read(n);
  read(m);
  for (int i = 1; i <= m; i++) {
    read(x);
    read(y);
    add_edge(x, y);
    add_edge(y, x);
  }
  for (int i = 1; i <= n; i++) sp.push(make_pair(0, i));
  while (1) {
    if (now * (n - now) != sum || now == 0) {
      s = find();
      ++now;
      for (int j = fir[s]; j; j = nxt[j]) {
        if (!vis[to[j]]) {
          ++sum, ++rd[to[j]];
          sp.push(make_pair(rd[to[j]], to[j]));
        } else
          --sum;
      }
    } else {
      ++ans;
      s = find();
      ++now;
      for (int j = fir[s]; j; j = nxt[j]) {
        if (!vis[to[j]]) {
          ++sum, ++rd[to[j]];
          sp.push(make_pair(rd[to[j]], to[j]));
        } else
          --sum;
      }
    }
    if (now == n) break;
  }
  cout << ans << "\n";
  return 0;
}
