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: competition

Starter code:

Solutions:
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
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)

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)

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)


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)

#Do note that every other edge that isn't present in this list already connects nodes.
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)
            #intersection are things you need to process but can't yet
            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")



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 
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')

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)
    #print('bhai')
    #print(parent)
    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=list(map(int,input().split()))
graph=dict()
for i in range(1,n+1):
    graph[i]=[]
for i in range(m):
    a,b=list(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))
    #print(d)
    x=[j for j in member]
    member[i]=1
    #print(i)
    #print(d)
    #print(member)
    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(parent) 
print(len(member)-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)
    #print(com)
    #print(co,i)
    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)

n, edges_num = list(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 collections as cc
import sys
input=sys.stdin.readline
#sys.setrecursionlimit(10**9)
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):
	#print(x,parent[x])
	while x!=parent[x]:
		x=parent[x]
	return x
def union(x,y):
	#print(x,y)
	a=find(x)
	b=find(y)
	#print(a,b)
	if a!=b:
		parent[x]=parent[y]=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)

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)

import sys
input = sys.stdin.readline
#lev contains height from root,lower neighbour, higher neighbours
#lev[0] contains 0 (because it is the root), higher neighbours (=neighbours)
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)
            else:
                treated+=1
                todo.append(u)
        notinacomponent=newnotin
        for i in range(1,neig[v][0]+1):
            isconnected[neig[v][i]]=False
print(sol)

import sys
input = sys.stdin.readline
#lev contains height from root,lower neighbour, higher neighbours
#lev[0] contains 0 (because it is the root), higher neighbours (=neighbours)
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 collections as cc
import sys
input=sys.stdin.readline
#sys.setrecursionlimit(10**9)
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)

import collections as cc
import sys
input=sys.stdin.readline
#sys.setrecursionlimit(10**9)
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)