#include <bits/stdc++.h> 
 
using namespace std;  
 
typedef long long ll;  
typedef pair<int, int> ii;  
 
const int INF = 1e9;  
const ll LINF = 1e18;  
 
const int N = 1e5 + 5; 
 
int n, m;  
vector<int> adj[N]; 
 
int p[N], sz[N]; 
 
void initSet() {
	for (int u = 1; u <= n; u++) {
		p[u] = u;  
		sz[u] = 1; 
	}
}
 
int findSet(int u) {
	if (p[u] == u) return u;  
	return p[u] = findSet(p[u]); 
}
 
void unionSet(int u, int v) {
	u = findSet(u); 
	v = findSet(v); 
	if (u == v) return; 
	if (sz[u] < sz[v]) swap(u, v); 
	p[v] = u;  
	sz[u] += sz[v];
}
 
int cnt[N]; 
 
int main() {
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); 	
	cin >> n >> m; 
	for (int i = 0; i < m; i++) {
		int u, v; 
		cin >> u >> v; 
		if (u < v) swap(u, v); 
		adj[u].push_back(v); 
	}
 
	initSet();   
 
	int num_cc = n;  // Số thành phần liên thông tạo bởi những cạnh có trọng số = 0 
	set<int> comp; // Danh sách các đỉnh đại diện cho các thành phần liên thông hiện tại 
 
	for (int u = 1; u <= n; u++) {
		for (int v : comp) cnt[v] = 0;
 
		for (int v : adj[u]) cnt[findSet(v)]++;  
 
		vector<int> merged;  
		for (int v : comp) {
			// cnt[v] = Số đỉnh có trong thành phần liên thông do v đại diện có cạnh trọng số = 1 nối đến u 
			if (cnt[v] < sz[v]) { 
				unionSet(u, v);
				merged.push_back(v);
				num_cc--; 
			}
		}
 
		for (int v : merged) comp.erase(v); 
		comp.insert(findSet(u));  
 
	} // O(nlogn + m)
 
	cout << num_cc - 1 << '\n';
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+IAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsgIAoKdHlwZWRlZiBsb25nIGxvbmcgbGw7ICAKdHlwZWRlZiBwYWlyPGludCwgaW50PiBpaTsgIAoKY29uc3QgaW50IElORiA9IDFlOTsgIApjb25zdCBsbCBMSU5GID0gMWUxODsgIAoKY29uc3QgaW50IE4gPSAxZTUgKyA1OyAKCmludCBuLCBtOyAgCnZlY3RvcjxpbnQ+IGFkaltOXTsgCgppbnQgcFtOXSwgc3pbTl07IAoKdm9pZCBpbml0U2V0KCkgewoJZm9yIChpbnQgdSA9IDE7IHUgPD0gbjsgdSsrKSB7CgkJcFt1XSA9IHU7ICAKCQlzelt1XSA9IDE7IAoJfQp9CgppbnQgZmluZFNldChpbnQgdSkgewoJaWYgKHBbdV0gPT0gdSkgcmV0dXJuIHU7ICAKCXJldHVybiBwW3VdID0gZmluZFNldChwW3VdKTsgCn0KCnZvaWQgdW5pb25TZXQoaW50IHUsIGludCB2KSB7Cgl1ID0gZmluZFNldCh1KTsgCgl2ID0gZmluZFNldCh2KTsgCglpZiAodSA9PSB2KSByZXR1cm47IAoJaWYgKHN6W3VdIDwgc3pbdl0pIHN3YXAodSwgdik7IAoJcFt2XSA9IHU7ICAKCXN6W3VdICs9IHN6W3ZdOwp9CgppbnQgY250W05dOyAKCmludCBtYWluKCkgewoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyAKCWNpbi50aWUobnVsbHB0cik7IAkKCWNpbiA+PiBuID4+IG07IAoJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIHsKCQlpbnQgdSwgdjsgCgkJY2luID4+IHUgPj4gdjsgCgkJaWYgKHUgPCB2KSBzd2FwKHUsIHYpOyAKCQlhZGpbdV0ucHVzaF9iYWNrKHYpOyAKCX0KCglpbml0U2V0KCk7ICAgCgoJaW50IG51bV9jYyA9IG47ICAvLyBT4buRIHRow6BuaCBwaOG6p24gbGnDqm4gdGjDtG5nIHThuqFvIGLhu59pIG5o4buvbmcgY+G6oW5oIGPDsyB0cuG7jW5nIHPhu5EgPSAwIAoJc2V0PGludD4gY29tcDsgLy8gRGFuaCBzw6FjaCBjw6FjIMSR4buJbmggxJHhuqFpIGRp4buHbiBjaG8gY8OhYyB0aMOgbmggcGjhuqduIGxpw6puIHRow7RuZyBoaeG7h24gdOG6oWkgCgoJZm9yIChpbnQgdSA9IDE7IHUgPD0gbjsgdSsrKSB7CgkJZm9yIChpbnQgdiA6IGNvbXApIGNudFt2XSA9IDA7CgoJCWZvciAoaW50IHYgOiBhZGpbdV0pIGNudFtmaW5kU2V0KHYpXSsrOyAgCgoJCXZlY3RvcjxpbnQ+IG1lcmdlZDsgIAoJCWZvciAoaW50IHYgOiBjb21wKSB7CgkJCS8vIGNudFt2XSA9IFPhu5EgxJHhu4luaCBjw7MgdHJvbmcgdGjDoG5oIHBo4bqnbiBsacOqbiB0aMO0bmcgZG8gdiDEkeG6oWkgZGnhu4duIGPDsyBj4bqhbmggdHLhu41uZyBz4buRID0gMSBu4buRaSDEkeG6v24gdSAKCQkJaWYgKGNudFt2XSA8IHN6W3ZdKSB7IAoJCQkJdW5pb25TZXQodSwgdik7CgkJCQltZXJnZWQucHVzaF9iYWNrKHYpOwoJCQkJbnVtX2NjLS07IAoJCQl9CgkJfQoJCQoJCWZvciAoaW50IHYgOiBtZXJnZWQpIGNvbXAuZXJhc2Uodik7IAoJCWNvbXAuaW5zZXJ0KGZpbmRTZXQodSkpOyAgCgkKCX0gLy8gTyhubG9nbiArIG0pCgoJY291dCA8PCBudW1fY2MgLSAxIDw8ICdcbic7Cn0K

NiAxMQoxIDMKMSA0CjEgNQoxIDYKMiAzCjIgNAoyIDUKMiA2CjMgNAozIDUKMyA2Cg==

6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6