You are given an undirected graph consisting of n vertices and $\frac{n(n - 1)}{2} - m$ edges. Instead of giving you the edges that exist in the graph, we give you m unordered pairs (x, y) such that there is no edge between x and y, and if some pair of vertices is not listed in the input, then there is an edge between these vertices.

You have to find the number of connected components in the graph and the size of each component. A connected component is a set of vertices X such that for every two vertices from this set there exists at least one path in the graph connecting these vertices, but adding any other vertex to X violates this rule.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 200000, $0 \leq m \leq \operatorname{min}(\frac{n(n - 1)}{2}, 200000)$).

Then m lines follow, each containing a pair of integers x and y (1 ≤ x, y ≤ n, x ≠ y) denoting that there is no edge between x and y. Each pair is listed at most once; (x, y) and (y, x) are considered the same (so they are never listed in the same test). If some pair of vertices is not listed in the input, then there exists an edge between those vertices. 


-----Output-----

Firstly print k — the number of connected components in this graph.

Then print k integers — the sizes of components. You should output these integers in non-descending order.


-----Example-----
Input
5 5
1 2
3 4
3 2
4 2
2 5

Output
2
1 4

Source: codeforces | Difficulty: HARD
Tags: Spanning trees

Graph algorithms

Data structures

Graph traversal


Solutions:
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))
notVisited = set(range(1, n + 1))
comps = []
for s in range(1, n + 1):
	if s in notVisited:
		notVisited.remove(s)
		ctr = 1
		stack = [s]
		while stack:
			v = stack.pop()
			visited = set()
			for to in notVisited:
				if (v, to) not in eins:
					visited.add(to)
					stack.append(to)
					ctr += 1
			notVisited -= visited
		comps.append(ctr)
comps.sort()
print(len(comps))
print(*comps)


(N, M) = map(int, input().split())
nE = [{i} for i in range(N)]
for _ in range(M):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	nE[u].add(v)
	nE[v].add(u)
unvisited = set(range(N))
res = []
while unvisited:
	s = next(iter(unvisited))
	unvisited.discard(s)
	stack = [s]
	cnt = 1
	while stack:
		v = stack.pop()
		s = unvisited - nE[v]
		cnt += len(s)
		stack.extend(s)
		unvisited &= nE[v]
	res.append(cnt)
res.sort()
print(len(res))
print(' '.join(map(str, res)))


def Solution(G):
	unvisited = {i for i in range(len(G))}
	sol = []
	while unvisited:
		l = len(unvisited)
		a = next(iter(unvisited))
		unvisited.discard(a)
		stack = [a]
		while stack:
			v = stack.pop()
			s = unvisited & G[v]
			stack.extend(unvisited - s)
			unvisited = s
		sol.append(l - len(unvisited))
	sol.sort()
	print(len(sol))
	print(' '.join(map('{0}'.format, sol)))
	pass

def main():
	s = input().split(' ')
	n = int(s[0])
	m = int(s[1])
	G = [{i} for i in range(n)]
	for _ in range(m):
		s = input().split(' ')
		n1 = int(s[0]) - 1
		n2 = int(s[1]) - 1
		G[n2].add(n1)
		G[n1].add(n2)
	Solution(G)
main()


import sys, math, os.path
FILE_INPUT = 'e.in'
DEBUG = os.path.isfile(FILE_INPUT)
if DEBUG:
	sys.stdin = open(FILE_INPUT)

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

def nia():
	return list(map(int, input().split()))

def log(x):
	if DEBUG:
		print(x)
(n, m) = ni()
a = [{i} for i in range(n)]
for i in range(m):
	(x, y) = ni()
	(x, y) = (x - 1, y - 1)
	a[x].add(y)
	a[y].add(x)
q = []
willVisit = set(range(n))
while willVisit:
	x = willVisit.pop()
	queue = [x]
	count = 1
	while queue:
		y = queue.pop()
		sibling = willVisit - a[y]
		count += len(sibling)
		queue.extend(sibling)
		willVisit -= sibling
	q.append(count)
q.sort()
print(len(q))
print(' '.join(map(str, q)))


(n, m) = map(int, input().split())
non = [{i} for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	non[u].add(v)
	non[v].add(u)
vertex = set(range(n))
ans = []
while vertex:
	a = next(iter(vertex))
	vertex.remove(a)
	stk = [a]
	cou = 1
	while stk:
		v = stk.pop()
		s = vertex - non[v]
		cou += len(s)
		stk.extend(s)
		vertex &= non[v]
	ans.append(cou)
ans.sort()
print(len(ans))
print(' '.join(map(str, ans)))


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy, copy
mod = 10 ** 9 + 7
INF = float('inf')

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

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

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()

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())
(n, m) = inpl()
un = [set() for _ in range(n)]
for _ in range(m):
	(a, b) = inpl_1()
	un[b].add(a)
	un[a].add(b)
uf = UnionFind(n)
seen = [0] * n
unknown = set(range(n))
for i in range(n):
	if seen[i]:
		continue
	seen[i] = 1
	unknown.discard(i)
	adj = deque()
	noadj = set()
	for j in list(unknown):
		if not j in un[i]:
			adj.append(j)
		else:
			noadj.add(j)
	while adj:
		j = adj.popleft()
		for k in list(noadj - un[j]):
			adj.append(k)
			noadj.discard(k)
		seen[j] = 1
		unknown.discard(j)
		uf.union(i, j)
res = []
for root in uf.roots():
	res.append(uf.size(root))
res.sort()
print(len(res))
print(*res)


import sys
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
adj = [set() for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().split())
	adj[x].add(y)
	adj[y].add(x)
unpaired = set([i for i in range(1, n + 1)])
comps = []
vis = [0] * (n + 1)
for i in range(1, n + 1):
	if not vis[i]:
		comps.append(0)
		s = [i]
		while s:
			c = s[-1]
			if not vis[c]:
				comps[-1] += 1
				vis[c] = 1
				remove = []
				for ne in unpaired:
					if ne not in adj[c]:
						remove.append(ne)
						s.append(ne)
				for ne in remove:
					unpaired.remove(ne)
			else:
				s.pop()
print(len(comps))
print(*sorted(comps))


(n, m) = map(int, input().split())
ae = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	ae[a - 1].append(b - 1)
	ae[b - 1].append(a - 1)
mn = -1
nbr = n
for i in range(n):
	if len(ae[i]) < nbr:
		mn = i
		nbr = len(ae[i])
keep = ae[mn]
ok = n - len(keep)
while True:
	toDel = -1
	for i in keep:
		aeo = len(ae[i])
		for j in ae[i]:
			if j in keep:
				aeo -= 1
				if aeo < ok:
					break
		if aeo < ok:
			toDel = i
			break
	if toDel == -1:
		break
	else:
		keep.remove(i)
		ok += 1
out = [ok]
d = {}
if len(keep) == 1:
	out.append(1)
elif len(keep) == 0:
	out = out
else:
	keep.sort()
	for i in range(len(keep)):
		d[keep[i]] = i
	edg = [[] for _ in range(len(keep))]
	for i in range(len(keep)):
		for j in range(len(keep)):
			if i == j:
				continue
			edg[i].append(j)
			edg[j].append(i)
	for i in keep:
		for j in ae[i]:
			if j in keep:
				if d[j] in edg[d[i]]:
					edg[d[i]].remove(d[j])
				if d[i] in edg[d[j]]:
					edg[d[j]].remove(d[i])
	used = [False] * len(keep)
	uss = 0
	while uss < len(keep):
		fi = -1
		for i in range(len(keep)):
			if not used[i]:
				fi = i
				break
		bfs = [fi]
		used[fi] = True
		usn = 1
		uss += 1
		while len(bfs) > 0:
			temp = bfs.pop()
			for i in edg[temp]:
				if not used[i]:
					used[i] = True
					bfs.append(i)
					uss += 1
					usn += 1
		out.append(usn)
out.sort()
print(len(out))
print(' '.join(map(str, out)))


import sys
from collections import deque
(n, m) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
adj = [set() for _ in range(n)]
for (u, v) in (map(int, line.decode('utf-8').split()) for line in sys.stdin.buffer):
	adj[u - 1].add(v - 1)
	adj[v - 1].add(u - 1)
dq = deque(range(n))
ans = []
while dq:
	stack = [dq.popleft()]
	size = 1
	while stack:
		v = stack.pop()
		for _ in range(len(dq)):
			if dq[0] not in adj[v]:
				size += 1
				stack.append(dq.popleft())
			dq.rotate()
	ans.append(size)
print(len(ans))
print(*sorted(ans))


(n, m) = map(int, input().split())
bar = [{i} for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	bar[u].add(v)
	bar[v].add(u)
nodes = set(range(n))
ans = []
while nodes:
	u = next(iter(nodes))
	nodes.remove(u)
	stk = [u]
	cnt = 1
	while stk:
		v = stk.pop()
		s = nodes - bar[v]
		cnt += len(s)
		stk.extend(s)
		nodes &= bar[v]
	ans.append(cnt)
ans.sort()
print(len(ans))
print(' '.join(map(str, ans)))


def read_int():
	return int(input())

def read_str():
	return input()

def read_list(type=int):
	return list(map(type, input().split()))

def print_list(x):
	print(len(x), ' '.join(map(str, x)))
N = 200123
nbs = [[] for i in range(N)]
up = [i for i in range(N)]
sz = [1] * N

def find(v):
	if v == up[v]:
		return v
	up[v] = find(up[v])
	return up[v]

def join(v, w):
	v = find(v)
	w = find(w)
	if v == w:
		return
	if sz[v] < sz[w]:
		(v, w) = (w, v)
	up[w] = v
	sz[v] += sz[w]

def main():
	(n, m) = read_list()
	for i in range(m):
		(a, b) = read_list()
		(a, b) = (a - 1, b - 1)
		if a < b:
			(a, b) = (b, a)
		nbs[a].append(b)
	components = set()
	for v in range(n):
		nonedges = dict()
		for w in nbs[v]:
			w = find(w)
			nonedges[w] = nonedges[w] + 1 if w in nonedges else 1
		tojoin = []
		for c in components:
			c = find(c)
			if nonedges.get(c, 0) < sz[c]:
				tojoin.append(c)
		for j in tojoin:
			join(j, v)
			components.remove(j)
		components.add(find(v))
	res = sorted([sz[find(c)] for c in components])
	print(len(res))
	for r in res:
		print(r, end=' ')
main()