#include <bits/stdc++.h>
using namespace std;
int root[1000100];
unordered_map<int, int> mp[1000100];
pair<pair<int, int>, int> edge[1000100];
int cnt[1000100];
int find_root(int u) {
  if (root[u] == u) return u;
  return root[u] = find_root(root[u]);
}
bool cmp(pair<pair<int, int>, int> u, pair<pair<int, int>, int> v) {
  return u.second < v.second;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  while (m--) {
    int u, v;
    scanf("%d%d", &u, &v);
    cnt[u]++;
    cnt[v]++;
    mp[u][v] = 1;
    mp[v][u] = 1;
  }
  int mn = n, f = 0;
  for (int i = 1; i <= n; i++) {
    root[i] = i;
    if (mn > cnt[i]) {
      f = i;
      mn = cnt[i];
    }
  }
  vector<int> X, Y;
  X.push_back(f);
  for (int i = 1; i <= n; i++) {
    if (i == f) continue;
    if (!mp[f][i]) {
      X.push_back(i);
      root[i] = f;
    } else
      Y.push_back(i);
  }
  m = 0;
  for (int i = 0; i < Y.size(); i++) {
    for (int j = i + 1; j < Y.size(); j++) {
      int u = Y[i], v = Y[j];
      edge[++m] = pair<pair<int, int>, int>(pair<int, int>(u, v), mp[u][v]);
    }
  }
  for (int i = 0; i < Y.size(); i++) {
    for (int j = 0; j < X.size(); j++) {
      int u = Y[i], v = X[j];
      edge[++m] = pair<pair<int, int>, int>(pair<int, int>(u, v), mp[u][v]);
    }
  }
  sort(edge + 1, edge + m + 1, cmp);
  int ans = 0;
  for (int i = 1; i <= m; i++) {
    int u = edge[i].first.first, v = edge[i].first.second, w = edge[i].second;
    int fu = find_root(u), fv = find_root(v);
    if (fu == fv) continue;
    root[fu] = fv;
    ans += w;
  }
  printf("%d\n", ans);
  return 0;
}
