#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int n, m, ans, cnt, d[N], minn = INT_MAX, head[N];
int siz[N], fa[N];
bool vis[N], is1[N];

struct Edge
{
	int to, nxt;
}edge[N];

void addEdge(int u, int v)
{
	edge[++cnt].to = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
	d[u]++;
	d[v]++;
	return;
}

int find(int x)
{
	if(x == fa[x]) return x;
	else return fa[x] = find(fa[x]);
}

void insert(int x, int y)
{
	x = find(x), y = find(y);
	if(x == y) return;
	if(siz[x]<siz[y])
		{
			swap(x, y);
		}
	fa[y] = x;
	siz[x] += siz[y];
	return;
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		{
			fa[i] = i;
		}//初始化并查集 
	int u, v;
	for(int i = 1; i <= m; i++)
		{
			cin >> u >> v;
			addEdge(u, v);
			addEdge(v, u);
		}//建双向边 
	for(int i = 1; i <= n; i++)
		{
			if(d[i] < minn)
				{
					minn = i;
				}
		}//找到1边数量最少的点 minn 
	for(int i = head[minn]; i; i = edge[i].nxt)
		{
			is1[edge[i].to] = 1;
		}//标记minn到某个点之间的边为1 
	for(int i = 1; i <= n; i++)
		{
			if(is1[i] == 0)
				{
					insert(minn, i);
				}
		}//如果minn到某个点为0，则加入同一个集合 
	for(int i = 1; i <= n; i++)
		{
			if(find(minn) == find(i))
				continue;
			for(int k = 1; k <= n; k++)
				{
					is1[k] = 0;
				}
			for(int k = head[i]; k; k = edge[k].nxt)
				{
					is1[edge[k].to] = 1;
				}
			for(int j = 1; j <= n; j++)
				{
					if(is1[j] == 0)
						{
							insert(i, j);
						}
				}
		}//开始暴力扫描散点，找到和minn不在同一个集合的点时，扫描这个点的所有1边并标记，如果某个点和这个点之间为0边，则加入同一个集合 
	queue<int> q;
	q.push(minn);//开始prim最小生成树 
	while(!q.empty())
		{
			int pos = q.front();
			q.pop();
			if(vis[pos]) continue;
			vis[pos] = 1;
			for(int i = head[pos]; i; i = edge[i].nxt)
				{
					int to = edge[i].to;
					if(find(minn) == find(to))
						{
							continue;
						}
					ans++;
					insert(minn, to);
//					q.push(to);
					if(!vis[to])
						{
							q.push(to);
						}
				}
		}//从minn开始更新，如果edge[i].to和minn不在同一个集合中，则需要连接一条1边，ans++，并记录当前点的所有边已经遍历，下次不再压入队列 
	cout << ans;
	return 0;
}