Ujan has a lot of useless stuff in his drawers, a considerable part of which are his math notebooks: it is time to sort them out. This time he found an old dusty graph theory notebook with a description of a graph.

It is an undirected weighted graph on $n$ vertices. It is a complete graph: each pair of vertices is connected by an edge. The weight of each edge is either $0$ or $1$; exactly $m$ edges have weight $1$, and all others have weight $0$.

Since Ujan doesn't really want to organize his notes, he decided to find the weight of the minimum spanning tree of the graph. (The weight of a spanning tree is the sum of all its edges.) Can you find the answer for Ujan so he stops procrastinating?


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 10^5$, $0 \leq m \leq \min(\frac{n(n-1)}{2},10^5)$), the number of vertices and the number of edges of weight $1$ in the graph. 

The $i$-th of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$), the endpoints of the $i$-th edge of weight $1$.

It is guaranteed that no edge appears twice in the input.


-----Output-----

Output a single integer, the weight of the minimum spanning tree of the graph.


-----Examples-----
Input
6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6

Output
2

Input
3 0

Output
0



-----Note-----

The graph from the first sample is shown below. Dashed edges have weight $0$, other edges have weight $1$. One of the minimum spanning trees is highlighted in orange and has total weight $2$. [Image] 

In the second sample, all edges have weight $0$ so any spanning tree has total weight $0$.

Difficulty: HARD
Tags: Spanning trees

Sorting

Graph algorithms

Graph traversal
Skill types: Sorting

Starter code:

Solutions:
from sys import stdin
from collections import defaultdict
input = stdin.readline

def put():
	return map(int, input().split())

def dfs(i):
	s = [i]
	points.remove(i)
	while s:
		i = s.pop()
		for j in tuple(points):
			if (min(i, j), max(i, j)) not in mp:
				s.append(j)
				points.remove(j)
(n, m) = put()
mp = defaultdict()
points = set(range(n))
for _ in range(m):
	(x, y) = put()
	(x, y) = (x - 1, y - 1)
	key = (min(x, y), max(x, y))
	mp[key] = 1
ans = -1
for i in range(n):
	if i in points:
		dfs(i)
		ans += 1
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
(N, M) = list(map(int, input().split()))
D = [{} for _ in range(N)]
for _ in range(M):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	D[a][b] = 1
	D[b][a] = 1
L = [i - 1 for i in range(N)]
R = [i + 1 for i in range(N)]
F = [0] * N
for i in range(N):
	if F[i]:
		continue
	f = 1
	while f:
		f = 0
		j = R[i]
		while j < N:
			if j in D[i]:
				j = R[j]
				continue
			F[j] = 1
			A = [a for a in D[i] if a not in D[j]]
			if A:
				f = 1
			for a in A:
				if a in D[i]:
					del D[i][a]
				if i in D[a]:
					del D[a][i]
			A = [a for a in D[j] if a not in D[i]]
			if A:
				f = 1
			for a in A:
				if a in D[j]:
					del D[j][a]
				if j in D[a]:
					del D[a][j]
			if R[j] < N:
				L[R[j]] = L[j]
			if L[j] >= 0:
				R[L[j]] = R[j]
			j = R[j]
print(N - sum(F) - 1)


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
(n, k) = map(int, input().split())
l = set()
for i in range(k):
	(a, b) = map(int, input().split())
	l.add((a, b))
	l.add((b, a))
p = set([i for i in range(1, n + 1)])
ans = 0
for i in range(1, n + 1):
	if i in p:
		p.remove(i)
		if i != 1:
			ans += 1
		q = collections.deque([i])
		while len(q) > 0:
			t = q.popleft()
			q1 = set()
			for j in p:
				if (t, j) not in l and (j, t) not in l:
					q.append(j)
					q1.add(j)
			for j in q1:
				p.remove(j)
print(ans)


from sys import stdin

def rl():
	return [int(w) for w in stdin.readline().split()]
(n, m) = rl()
he = [set() for _ in range(n + 1)]
for _ in range(m):
	(a, b) = rl()
	he[a].add(b)
	he[b].add(a)
unvisited = set(range(1, n + 1))
ccs = 0
while unvisited:
	fringe = {unvisited.pop()}
	while fringe:
		v = fringe.pop()
		nxt = [u for u in unvisited if u not in he[v]]
		unvisited.difference_update(nxt)
		fringe.update(nxt)
	ccs += 1
print(ccs - 1)


(n, edges_num) = map(int, input().split())
edges = set((tuple(map(int, input().split())) for _ in range(edges_num)))
nodes = set(range(1, n + 1))
comps = 0
comp_q = []
while nodes:
	if comp_q:
		u = comp_q.pop()
	else:
		u = nodes.pop()
		comps += 1
	zero_set = {v for v in nodes if (u, v) not in edges and (v, u) not in edges}
	nodes -= zero_set
	comp_q += zero_set
print(comps - 1)


import os, sys
from io import BytesIO, IOBase

def main():
	(n, m) = map(int, input().split())
	path = [set() for _ in range(n)]
	for _ in range(m):
		(a1, b1) = map(lambda xx: int(xx) - 1, input().split())
		path[a1].add(b1)
		path[b1].add(a1)
	(mini, ind, cost) = (10 ** 9, -1, 0)
	for i in range(n):
		if len(path[i]) < mini:
			(mini, ind) = (len(path[i]), i)
	le = path[ind]
	curr = [j for j in range(n) if j not in le]
	while 1:
		for i in curr:
			le1 = set()
			for r in le:
				if r in path[i]:
					le1.add(r)
				else:
					curr.append(r)
			le = le1
		if not len(le):
			break
		cost += 1
		curr = [le.pop()]
	print(cost)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def bfs(g, st, col, visited):
	visited[st] = col
	queue = deque([])
	queue.append(st)
	new = []
	while len(queue) != 0:
		s = queue.popleft()
		new.append(s)
		for i in g[s]:
			if visited[i] == 0:
				visited[i] = col
				queue.append(i)

def solve(case):
	(n, m) = sep()
	edges = {}
	for i in range(m):
		(a, b) = sep()
		a -= 1
		b -= 1
		edges[a, b] = True
		edges[b, a] = True
	notvis = {i for i in range(n)}
	vis = [0] * n
	col = 1
	for i in range(n):
		if vis[i] != 0:
			continue
		notvis.remove(i)
		vis[i] = col
		stack = [i]
		while len(stack) != 0:
			ii = stack.pop()
			done = set()
			for j in notvis:
				if (ii, j) not in edges:
					vis[j] = col
					stack.append(j)
					done.add(j)
			notvis -= done
		col += 1
	print(col - 2)
testcase(1)


import collections as cc
import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n, m) = I()
g = [set() for i in range(n + 1)]
xx = [0] * (n + 1)
for i in range(m):
	(x, y) = I()
	g[x].add(y)
	g[y].add(x)
parent = [i for i in range(n + 1)]

def find(x):
	while x != parent[x]:
		x = parent[x]
	return x

def union(x, y):
	a = find(x)
	b = find(y)
	if a != b:
		parent[a] = parent[b] = min(a, b)
ff = cc.defaultdict(int)
used = cc.defaultdict(int)
for i in range(1, n + 1):
	if find(i) == i:
		for j in range(1, n + 1):
			if j not in g[i]:
				g[i] &= g[j]
		for j in range(1, n + 1):
			if j not in g[i]:
				union(i, j)
print(len(set([find(i) for i in range(1, n + 1)])) - 1)


(n, m) = map(int, input().split())
e = set()
for _ in range(m):
	(x, y) = map(int, input().split())
	e.add((x - 1, y - 1))
	e.add((y - 1, x - 1))
points = set(range(n))
ans = -1
for i in range(n):
	if i in points:
		ans += 1
		st = [i]
		points.remove(i)
		while st:
			j = st.pop()
			for k in tuple(points):
				if (j, k) not in e:
					points.remove(k)
					st.append(k)
print(ans)


import sys
(n, m) = map(int, sys.stdin.readline().split(' '))
graph = set((tuple(map(int, sys.stdin.readline().split(' '))) for _ in range(m)))
to_visit = set(range(1, n + 1))
visited = []
cc = 0
while to_visit:
	if visited:
		v = visited.pop()
	else:
		v = to_visit.pop()
		cc += 1
	c = {u for u in to_visit if (u, v) not in graph and (v, u) not in graph}
	to_visit -= c
	visited += c
sys.stdout.write('{}\n'.format(cc - 1))


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
E = [[] for _ in range(N + 1)]
for _ in range(M):
	(v, u) = map(int, input().split())
	E[v].append(u)
	E[u].append(v)
Open = [True] * (N + 1)
Rem = set(range(1, N + 1))

def bfs(v):
	Open[v] = True
	global Rem
	Rem.remove(v)
	q = [v]
	while q:
		v = q.pop()
		set_E_v = set(E[v])
		for u in Rem - set_E_v:
			if Open[u]:
				Open[u] = False
				q.append(u)
		Rem &= set_E_v
ans = -1
for v in range(1, N + 1):
	if Open[v]:
		ans += 1
		bfs(v)
print(ans)


(n, m) = map(int, input().split())
e = set((tuple(map(int, input().split())) for _ in range(m)))
a = set(range(1, n + 1))
q = []
r = 0
while a:
	if q:
		u = q.pop()
	else:
		u = a.pop()
		r += 1
	c = {v for v in a if (u, v) not in e and (v, u) not in e}
	a -= c
	q += c
print(r - 1)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
(n, m) = map(int, input().split())
G = [set() for i in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].add(b)
	G[b].add(a)
ans = 0
unused = set(range(n))
while unused:
	cur = {unused.pop()}
	while cur:
		i = cur.pop()
		nxt = {j for j in unused if j not in G[i]}
		unused.difference_update(nxt)
		cur.update(nxt)
	ans += 1
print(ans - 1)


import sys
input = sys.stdin.readline

def find(parent, x):
	if parent[x] == x:
		return x
	else:
		parent[x] = find(parent, parent[x])
		return parent[x]

def union(x, y, parent):
	parent[x] = find(parent, x)
	parent[y] = find(parent, y)
	if parent[x] == parent[y]:
		return
	else:
		parent[parent[y]] = parent[x]
from collections import defaultdict as dd
(n, m) = map(int, input().split())
d = dd(list)
for i in range(m):
	(u, v) = map(int, input().split())
	if u > v:
		(u, v) = (v, u)
	d[v].append(u)
parent = dd(int)
com = dd(int)
com[1] = 1
for i in range(1, n + 1):
	parent[i] = i
com[1] = 1
for i in range(2, n + 1):
	co = dd(int)
	for j in com:
		co[j] = 0
	for j in d[i]:
		a = find(parent, j)
		co[a] += 1
	x = dd(int)
	for j in com:
		x[j] = com[j]
	lol = 0
	com[i] = 1
	for j in x:
		if co[j] < com[j]:
			a = find(parent, i)
			union(j, i, parent)
			com[j] += com[a]
			del com[a]
			lol = 1
print(len(com) - 1)


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
E = [set() for i in range(n + 1)]
for i in range(m):
	(x, y) = list(map(int, input().split()))
	E[x].add(y)
	E[y].add(x)
Group = [i for i in range(n + 1)]

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		Group[find(y)] = Group[find(x)] = min(find(y), find(x))
for i in range(1, n + 1):
	if find(i) == i:
		for j in range(1, n + 1):
			if not j in E[i]:
				E[i] &= E[j]
		for j in range(1, n + 1):
			if not j in E[i]:
				Union(i, j)
print(len(set([find(i) for i in range(1, n + 1)])) - 1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
e = set((tuple(map(int, input().split())) for _ in range(m)))
unknown = set(range(1, n + 1))
to_check = []
ans = 0
while unknown:
	if to_check:
		u = to_check.pop()
	else:
		u = unknown.pop()
		ans += 1
	cur = []
	for v in unknown:
		if (u, v) in e or (v, u) in e:
			continue
		cur.append(v)
	for v in cur:
		unknown.remove(v)
	to_check += cur
print(ans - 1)


import sys
from sys import stdin, stdout
(n, m) = stdin.readline().split()
n = int(n)
m = int(m)
e = set((tuple(map(int, stdin.readline().split())) for _ in range(m)))
a = set(range(1, n + 1))
q = []
r = 0
while a:
	if q:
		u = q.pop()
	else:
		u = a.pop()
		r += 1
	c = {v for v in a if (u, v) not in e and (v, u) not in e}
	a -= c
	q += c
stdout.write(str(r - 1) + '\n')


(n, m) = map(int, input().split())
Adj = []
for i in range(0, n):
	Adj.append([])
for i in range(0, m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	Adj[a].append(b)
	Adj[b].append(a)
To_Visit = []
for j in range(0, n):
	To_Visit.append(j)
C_Conexas = 0
for k in range(0, n):
	if k in To_Visit:
		C_Conexas += 1
		To_Visit.remove(k)
		Gray = []
		Gray.append(k)
		while len(Gray) != 0:
			Element = Gray.pop()
			NodosCost = []
			for v in Adj[Element]:
				if v in To_Visit:
					To_Visit.remove(v)
					NodosCost.append(v)
			for v in To_Visit:
				Gray.append(v)
			To_Visit.clear()
			for v in NodosCost:
				To_Visit.append(v)
print(C_Conexas - 1)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():

	def BFS(node):
		nonlocal unseen
		q = deque()
		q.append(node)
		v[node] = 1
		unseen.discard(node)
		future = set()
		res = 0
		while q:
			res += 1
			a = q.popleft()
			for i in graph[a]:
				if v[i]:
					continue
				if i in unseen:
					future.add(i)
					unseen.discard(i)
			for i in unseen:
				v[i] = 1
				q.append(i)
			unseen = set(future)
			future = set()
	(n, m) = mp()
	graph = defaultdict(list)
	for i in range(m):
		(a, b) = mp()
		graph[a].append(b)
		graph[b].append(a)
	v = defaultdict(int)
	ans = -1
	unseen = set(range(1, n + 1))
	for i in range(1, n + 1):
		if not v[i]:
			BFS(i)
			ans += 1
	print(ans)
for _ in range(1):
	solve()


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
(n, m) = inpl()
g = [set() for _ in range(n + 1)]
for _ in range(m):
	(a, b) = inpl()
	(a, b) = (a - 1, b - 1)
	g[a].add(b)
	g[b].add(a)
seen = [False] * n
nd = set((x for x in range(n)))
res = 0

def ch(i):
	q = deque([i])
	global nd
	nd.remove(i)
	while q:
		nv = q.popleft()
		now = g[nv]
		for v in nd - now:
			if seen[v]:
				continue
			seen[v] = True
			nd.remove(v)
			q.append(v)
for i in range(n):
	if seen[i]:
		continue
	seen[i] = True
	res += 1
	ch(i)
print(res - 1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
neig = [0] * n
for i in range(n):
	neig[i] = [0]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	neig[a][0] += 1
	neig[b][0] += 1
	neig[a].append(b)
	neig[b].append(a)
sol = -1
isconnected = [False] * n
notinacomponent = [0] * n
for i in range(n):
	notinacomponent[i] = i
treated = 0
while treated < n:
	todo = [notinacomponent.pop()]
	treated += 1
	sol += 1
	while len(todo) > 0:
		v = todo.pop()
		for i in range(1, neig[v][0] + 1):
			isconnected[neig[v][i]] = True
		newnotin = []
		for u in notinacomponent:
			if isconnected[u]:
				newnotin.append(u)
				isconnected[u] = False
			else:
				treated += 1
				todo.append(u)
		notinacomponent = newnotin
print(sol)


import sys
ip = lambda : sys.stdin.readline().rstrip()
from collections import defaultdict

def f(n):
	isv[n] = True
	if n in s:
		s.remove(n)
	a = []
	for i in s:
		if not isv[i] and i not in d[n]:
			a.append(i)
	for i in a:
		if i in s:
			s.remove(i)
	for i in a:
		f(i)
(n, m) = map(int, ip().split())
d = defaultdict(lambda : dict())
s = set()
isv = [False] * n
for i in range(n):
	s.add(i)
for _ in range(m):
	(u, v) = map(int, ip().split())
	u -= 1
	v -= 1
	d[u][v] = True
	d[v][u] = True
ans = 0
for i in range(n):
	if not isv[i]:
		f(i)
		ans += 1
print(ans - 1)


(n, m) = map(int, input().split())
inp = set()
for _ in range(m):
	(a, b) = map(int, input().split())
	inp.add((a - 1, b - 1))
	inp.add((b - 1, a - 1))
unc = set(range(n))
ans = -1
for i in range(n):
	if i in unc:
		ans += 1
		unc.remove(i)
		stack = [i]
		while stack:
			j = stack.pop()
			for k in tuple(unc):
				if (j, k) not in inp:
					unc.remove(k)
					stack.append(k)
print(ans)


from collections import Counter as CO
import sys
input = sys.stdin.readline

def find(parent, x):
	if parent[x] == x:
		return x
	else:
		parent[x] = find(parent, parent[x])
		return parent[x]

def union(parent, x, y, member):
	parent[x] = find(parent, x)
	parent[y] = find(parent, y)
	if parent[x] == parent[y]:
		return
	else:
		if x < y:
			(x, y) = (y, x)
		member[parent[y]] += member[parent[x]]
		del member[parent[x]]
		parent[parent[x]] = parent[y]
		return
(n, m) = map(int, input().split())
graph = dict()
for i in range(1, n + 1):
	graph[i] = []
for i in range(m):
	(a, b) = map(int, input().split())
	if b > a:
		(a, b) = (b, a)
	graph[a] += [b]
count = 0
parent = dict()
member = dict()
for i in range(1, n + 1):
	parent[i] = i
for i in range(1, n + 1):
	l = []
	for r in graph[i]:
		l += [find(parent, r)]
	d = dict(CO(l))
	x = [j for j in member]
	member[i] = 1
	for k in x:
		if k not in d:
			union(parent, i, k, member)
		elif d[k] < member[k]:
			union(parent, i, k, member)
print(len(member) - 1)


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		self.parent[self.find(b)] = self.find(a)

def main():
	(n, m) = readIntArr()
	oneEdges = [set() for _ in range(n)]
	for _ in range(m):
		(u, v) = readIntArr()
		u -= 1
		v -= 1
		oneEdges[u].add(v)
		oneEdges[v].add(u)
	uf = UnionFind(n)
	visited = [False for _ in range(n)]
	for i in range(n):
		if visited[i]:
			continue
		visited[i] = True
		toExplore = set()
		for j in range(i + 1, n):
			if visited[j] == False:
				toExplore.add(j)
		stack = [i]
		while stack and toExplore:
			node = stack.pop()
			toRemove = list()
			for nex in toExplore:
				if nex not in oneEdges[node]:
					uf.union(i, nex)
					stack.append(nex)
					visited[nex] = True
					toRemove.append(nex)
			for nex in toRemove:
				toExplore.remove(nex)
	parents = set()
	for i in range(n):
		parents.add(uf.find(i))
	ans = len(parents) - 1
	print(ans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


from collections import deque
(n, k) = map(int, input().split())
l = set()
for i in range(k):
	(a, b) = map(int, input().split())
	l.add((a, b))
	l.add((b, a))
p = set([i for i in range(1, n + 1)])
ans = 0
for i in range(1, n + 1):
	if i in p:
		p.remove(i)
		if i != 1:
			ans += 1
		q = deque([i])
		while len(q) > 0:
			t = q.popleft()
			q1 = set()
			for j in p:
				if (t, j) not in l and (j, t) not in l:
					q.append(j)
					q1.add(j)
			for j in q1:
				p.remove(j)
print(ans)


class UnionFind(object):
	__slots__ = ['nodes']

	def __init__(self, n: int):
		self.nodes = [-1] * n

	def size(self, x: int) -> int:
		return -self.nodes[self.find(x)]

	def find(self, x: int) -> int:
		if self.nodes[x] < 0:
			return x
		else:
			self.nodes[x] = self.find(self.nodes[x])
			return self.nodes[x]

	def unite(self, x: int, y: int) -> bool:
		(root_x, root_y, nodes) = (self.find(x), self.find(y), self.nodes)
		if root_x != root_y:
			if nodes[root_x] > nodes[root_y]:
				(root_x, root_y) = (root_y, root_x)
			nodes[root_x] += nodes[root_y]
			nodes[root_y] = root_x
		return root_x != root_y

def main():
	import sys
	from collections import Counter
	(n, m) = map(int, input().split())
	rev_edges = [[] for _ in range(n)]
	for (s, t) in (map(int, l.split()) for l in sys.stdin):
		if s < t:
			rev_edges[t - 1].append(s - 1)
		else:
			rev_edges[s - 1].append(t - 1)
	uf = UnionFind(n)
	(find, unite, size) = (uf.find, uf.unite, uf.size)
	zero_union = set()
	for v in range(n):
		cnt = Counter()
		for src in rev_edges[v]:
			cnt[find(src)] += 1
		for zero_v in zero_union:
			root = find(zero_v)
			if size(root) > cnt[root]:
				unite(root, v)
		zero_union = set((find(v_) for v_ in zero_union)) | {find(v)}
	print(len(zero_union) - 1)
main()


import sys
import queue

class UF(object):

	def __init__(self, n):
		self.arr = list(range(n + 1))
		self.rank = [1] * (n + 1)

	def root(self, x):
		if self.arr[x] != x:
			self.arr[x] = self.root(self.arr[x])
		return self.arr[x]

	def union(self, x, y):
		root_x = self.root(x)
		root_y = self.root(y)
		if root_x == root_y:
			return
		rank_x = self.rank[root_x]
		rank_y = self.rank[root_y]
		if rank_x >= rank_y:
			self.rank[root_x] += rank_y
			self.arr[root_y] = root_x
		else:
			self.rank[root_y] += rank_x
			self.arr[root_x] = root_y
(n, m) = sys.stdin.readline().split(' ')
n = int(n)
m = int(m)

def load_graph(m, n):
	graph = {}
	for i in range(1, n + 1):
		graph[i] = set()
	for _ in range(m):
		(i, j) = sys.stdin.readline().split(' ')
		i = int(i)
		j = int(j)
		graph[i].add(j)
		graph[j].add(i)
	return graph

def do(n, m):
	uf = UF(n)
	one_graph = load_graph(m, n)
	sorted_graph = sorted(one_graph, key=lambda x: len(one_graph[x]))
	if m < n - 1:
		return 0
	if m == n - 1 and n > 1:
		if len(one_graph[sorted_graph[-1]]) == n - 1:
			return 1
		else:
			return 0
	remaining = set(range(1, n + 1))
	for start in sorted_graph:
		if len(remaining) == 0:
			break
		if start not in remaining:
			continue
		Q = queue.Queue()
		Q.put(start)
		remaining.remove(start)
		while not Q.empty():
			u = Q.get()
			one_graph[u].intersection_update(remaining)
			remaining.difference_update(one_graph[u])
			for elt in remaining:
				Q.put(elt)
				uf.union(u, elt)
			remaining = one_graph[u]
			if len(remaining) == 0:
				break
	return len(set(uf.arr)) - 2
res = do(n, m)
sys.stdout.write(str(res) + '\n')


from collections import deque
from sys import stdin
global q, node, check
(node, node2) = ([[] for i in range(100001)], [[] for i in range(100001)])
(n, m) = map(int, input().split())
(small, big) = ([], [])
q = deque()
check = [0] * 100001

def bfs():
	while len(q) > 0:
		p = q[0]
		q.popleft()
		for i in node[p]:
			if check[i] == 0:
				check[i] = 1
				q.append(i)
for i in range(m):
	(a, b) = map(int, stdin.readline().split())
	node2[a].append(b)
	node2[b].append(a)
for i in range(1, n + 1):
	if len(node2[i]) < n // 2:
		big.append(i)
	else:
		small.append(i)
for i in small:
	inn = [0] * 100001
	for i2 in node2[i]:
		inn[i2] = 1
	for i2 in range(1, n + 1):
		if i2 != i and inn[i2] == 0:
			node[i].append(i2)
			node[i2].append(i)
for i in big:
	check[i] = 1
	q.append(i)
bfs()
ans = 0
for i in range(1, n + 1):
	if check[i] == 0:
		check[i] = 1
		q.append(i)
		bfs()
		ans += 1
if len(big) == 0:
	ans -= 1
print(ans)


from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import sys
sys.setrecursionlimit(10 ** 9)
(n, m) = map(int, input().split())
hash = defaultdict(set)
for i in range(m):
	(a, b) = map(int, input().split())
	hash[a].add(b)
	hash[b].add(a)
count = 0
un = {i + 1 for i in range(n)}
while un:
	queue = {un.pop()}
	while queue:
		z = queue.pop()
		nxt = [u for u in un if u not in hash[z]]
		un.difference_update(nxt)
		queue.update(nxt)
	count += 1
print(count - 1)


from sys import stdin, stdout
from collections import Counter, deque
from bisect import bisect_left
from itertools import product
input = stdin.buffer.readline
(n, m) = map(int, input().split())
e = [set() for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	e[a].add(b)
	e[b].add(a)
(res, cc) = (0, set(range(1, n + 1)))
for u in range(1, n + 1):
	for v in cc:
		if v not in e[u] and u != v:
			e[v].intersection_update(e[u])
			cc.remove(u)
			break
	else:
		cc.remove(u)
		res += 1
print(res - 1)


(n, m) = map(int, input().split())
g = [list() for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
vertex_to_cnt = [0] * n
cnt_to_vertices = {0: {v for v in range(0, n)}}
r = 0
weight = 0
size = 0

def add_to_tree(v):
	global size
	size += 1
	cnt = vertex_to_cnt[v]
	cnt_to_vertices[cnt].remove(v)
	if len(cnt_to_vertices[cnt]) == 0:
		cnt_to_vertices.pop(cnt)
	vertex_to_cnt[v] = None
	for c in g[v]:
		assert isinstance(c, int)
		if vertex_to_cnt[c] is not None:
			cnt_to_vertices[vertex_to_cnt[c]].remove(c)
			if len(cnt_to_vertices[vertex_to_cnt[c]]) == 0:
				cnt_to_vertices.pop(vertex_to_cnt[c])
			vertex_to_cnt[c] += 1
			if vertex_to_cnt[c] not in cnt_to_vertices:
				cnt_to_vertices[vertex_to_cnt[c]] = set()
			cnt_to_vertices[vertex_to_cnt[c]].add(c)
add_to_tree(r)
for i in range(1, n):
	v = None
	for (cnt, vertices) in cnt_to_vertices.items():
		if cnt < size:
			for v in vertices:
				break
			break
	if v is None:
		cnt = size
		vertices = cnt_to_vertices[cnt]
		for v in vertices:
			break
		weight += 1
	add_to_tree(v)
print(weight)


import sys
input = sys.stdin.readline

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members
(n, m) = map(int, input().split())
g = [set() for i in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	g[u - 1].add(v - 1)
	g[v - 1].add(u - 1)
min_idx = -1
MIN = 10 ** 9
for i in range(n):
	if len(g[i]) < MIN:
		MIN = len(g[i])
		min_idx = i
uf = UnionFind(n)
weight1 = g[min_idx]
weight0 = set([i for i in range(n)]) - weight1
for x in weight0:
	uf.union(x, min_idx)
for v in weight1:
	for i in range(n):
		if not v in g[i]:
			uf.union(i, v)
print(uf.group_count() - 1)


(n, m) = map(int, input().split())
arr = set()
for i in range(m):
	(a, b) = map(int, input().split())
	arr.add((a, b))
	arr.add((b, a))
if m < n - 1:
	print(0)
else:
	nodes = set(range(1, n + 1))
	ans = 0
	for i in range(1, n + 1):
		if i in nodes:
			nodes.remove(i)
			stack = [i]
			ans += 1
			while stack:
				j = stack.pop()
				visited = set()
				for k in nodes:
					if (j, k) not in arr:
						visited.add(k)
						stack.append(k)
				nodes -= visited
	print(ans - 1)


def find(u):
	if parent[u] == u:
		return u
	parent[u] = find(parent[u])
	return parent[u]

def union(a, b):
	if find(a) != find(b):
		u = parent[a]
		v = parent[b]
		if size[u] > size[v]:
			parent[v] = u
			size[u] += size[v]
			del size[v]
		else:
			parent[u] = v
			size[v] += size[u]
			del size[u]
	return
(n, m) = map(int, input().split())
adj = [[] for i in range(n + 1)]
for j in range(m):
	(u, v) = map(int, input().split())
	if u < v:
		adj[v].append(u)
	else:
		adj[u].append(v)
size = dict()
parent = [i for i in range(n + 1)]
for v in range(1, n + 1):
	req = []
	d1 = dict()
	for j in adj[v]:
		f = find(j)
		req.append(f)
		if f in d1:
			d1[f] += 1
		else:
			d1[f] = 1
	res = [j for j in size]
	size[v] = 1
	for i in res:
		if i not in d1:
			union(i, v)
		elif d1[i] < size[i]:
			union(i, v)
print(len(size) - 1)


I = input
(Vertix, edge) = list(map(int, I().split()))
edges = set((tuple(map(int, I().split())) for _ in range(edge)))
Universal_set = set(range(1, Vertix + 1))
queu = []
cost = 0
while Universal_set:
	if queu:
		pop = queu.pop()
	else:
		pop = Universal_set.pop()
		cost += 1
	next = {v for v in Universal_set if (pop, v) not in edges and (v, pop) not in edges}
	Universal_set -= next
	queu += next
print(cost - 1)


from collections import deque
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
(n, m) = [int(item) for item in input().split()]
ans = 0
edge = set()
for i in range(m):
	(a, b) = [int(item) - 1 for item in input().split()]
	edge.add((a, b))
	edge.add((b, a))
ans = 0
visited = [0] * n
for i in range(n):
	if visited[i]:
		continue
	ans += 1
	dq = deque()
	unseen = set((item for item in range(n)))
	dq.append(i)
	unseen.remove(i)
	while dq:
		v = dq.popleft()
		visited[v] = 1
		to_remove = []
		for item in unseen:
			if (v, item) not in edge:
				dq.append(item)
				to_remove.append(item)
		for item in to_remove:
			unseen.remove(item)
print(ans - 1)


import sys
import collections
import heapq
import math
input = sys.stdin.readline

def rints():
	return map(int, input().strip().split())

def rstr():
	return input().strip()

def rint():
	return int(input().strip())

def rintas():
	return [int(i) for i in input().strip().split()]

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
(n, m) = rints()
edges = collections.defaultdict(set)
for _ in range(m):
	(u, v) = rints()
	edges[u].add(v)
	edges[v].add(u)
cost = 0
set = collections.OrderedDict()
for i in range(1, n + 1):
	set[i] = i
for i in range(1, n + 1):
	if i in set:
		queue = collections.deque()
		queue.append(i)
		del set[i]
		cost += 1
		while queue:
			cur = queue.popleft()
			d = list()
			for (k, v) in set.items():
				if k not in edges[cur]:
					queue.appendleft(k)
					d.append(k)
			for k in d:
				del set[k]
print(cost - 1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
eins = set()
for _ in range(m):
	(v, to) = map(int, input().split())
	eins.add((v, to))
	eins.add((to, v))
if m < n - 1:
	print(0)
	sys.exit()
notVisited = set(range(1, n + 1))
compCtr = 0
for s in range(1, n + 1):
	if s in notVisited:
		notVisited.remove(s)
		stack = [s]
		compCtr += 1
		while stack:
			v = stack.pop()
			visited = set()
			for to in notVisited:
				if (v, to) not in eins:
					visited.add(to)
					stack.append(to)
			notVisited -= visited
print(compCtr - 1)


(n, m) = map(int, input().split())
adj = [[] for i in range(n)]
used = [0 for i in range(n)]
mark = [0 for i in range(n)]
S = [i for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	adj[u].append(v)
	adj[v].append(u)

def dfs(v):
	global S
	used[v] = 1
	(S2, S3) = ([], [])
	for to in adj[v]:
		mark[to] = 1
	for to in S:
		if mark[to] == 0:
			S3.append(to)
		else:
			S2.append(to)
	for to in adj[v]:
		mark[to] = 0
	S = S2.copy()
	for to in S3:
		dfs(to)
ans = -1
for i in range(n):
	if not used[i]:
		S.remove(i)
		ans += 1
		dfs(i)
print(ans)


from collections import defaultdict, deque
from sys import stdin, stdout
(n, m) = [int(x) for x in stdin.readline().split()]
graph = [set() for x in range(n)]
for e in range(m):
	(a, b) = [int(x) for x in stdin.readline().split()]
	a -= 1
	b -= 1
	graph[a].add(b)
	graph[b].add(a)
need = set([x for x in range(n)])
groups = 0
while need:
	groups += 1
	nxt = need.pop()
	group = [nxt]
	q = deque()
	q.append(nxt)
	while q:
		n = q.popleft()
		tempGroup = []
		for x in need:
			if not x in graph[n]:
				tempGroup.append(x)
				q.append(x)
		for x in tempGroup:
			need.remove(x)
print(groups - 1)


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
sys.setrecursionlimit(10 ** 5)
(n, m) = I()
g = [set() for i in range(n)]
for i in range(m):
	(u, v) = I()
	g[u - 1].add(v - 1)
	g[v - 1].add(u - 1)
p = [i for i in range(n)]

def find(x):
	while x != p[x]:
		x = p[x]
	return x

def union(a, b):
	x = find(a)
	y = find(b)
	p[y] = x
for i in range(n):
	if p[i] == i:
		for j in range(n):
			if j not in g[i]:
				g[i] &= g[j]
		for j in range(n):
			if j not in g[i]:
				union(i, j)
print(len(set([find(i) for i in range(n)])) - 1)


(n, m, *t) = map(int, open(0).read().split())
from collections import defaultdict
mp = defaultdict(int)
s1 = []
s2 = []
s1.append(1)
for i in range(2, n + 1):
	s2.append(i)
for (a, b) in zip(*[iter(t)] * 2):
	mp[a, b] = 1
	mp[b, a] = 1
ans = 0
while len(s2):
	ns1 = []
	ss1 = set()
	for i in s1:
		for j in s2:
			if mp[i, j]:
				continue
			ns1.append(j)
			ss1.add(j)
		s2 = list(set(s2) - ss1)
	if len(ss1) == 0:
		ans += 1
		s1 = [s2.pop()]
	else:
		s1 = ns1
	if len(s2) == 0 and len(s1) and (ans > 0):
		ans += 1
print(max(0, ans - 1))