AtCoder Library Practice Contest - SCC

You are given a directed graph with N vertices and M edges, not necessarily simple. The i-th edge is oriented from the vertex a_i to the vertex b_i. Divide this graph into strongly connected components and print them in their topological order.

Constraints

* 1 \leq N \leq 500,000
* 1 \leq M \leq 500,000
* 0 \leq a_i, b_i < N

Input

Input is given from Standard Input in the following format:


N M
a_0 b_0
a_1 b_1
:
a_{M - 1} b_{M - 1}


Output

Print 1+K lines, where K is the number of strongly connected components. Print K on the first line. Print the information of each strongly connected component in next K lines in the following format, where l is the number of vertices in the strongly connected component and v_i is the index of the vertex in it.


l v_0 v_1 ... v_{l-1}


Here, for each edge (a_i, b_i), b_i should not appear in earlier line than a_i.

If there are multiple correct output, print any of them.

Example

Input

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2


Output

4
1 5
2 4 1
1 2
2 3 0

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
class csr:

	def __init__(self, N, edges):
		self.start = [0] * (N + 1)
		self.elist = [0] * len(edges)
		for e in edges:
			self.start[e[0] + 1] += 1
		for i in range(1, N + 1):
			self.start[i] += self.start[i - 1]
		counter = self.start[:]
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class scc_graph:
	__slots__ = ['N', 'edges']

	def __init__(self, N):
		self.N = N
		self.edges = []

	def add_edge(self, v, w):
		self.edges.append((v, w))

	def scc_ids(self):
		N = self.N
		g = csr(N, self.edges)
		now_ord = group_num = 0
		visited = []
		low = [0] * N
		order = [-1] * N
		ids = [0] * N
		parent = [-1] * N
		stack = []
		for i in range(N):
			if order[i] == -1:
				stack.append(i)
				stack.append(i)
				while stack:
					v = stack.pop()
					if order[v] == -1:
						low[v] = order[v] = now_ord
						now_ord += 1
						visited.append(v)
						for j in range(g.start[v], g.start[v + 1]):
							to = g.elist[j]
							if order[to] == -1:
								stack.append(to)
								stack.append(to)
								parent[to] = v
							else:
								low[v] = min(low[v], order[to])
					else:
						if low[v] == order[v]:
							while True:
								u = visited.pop()
								order[u] = N
								ids[u] = group_num
								if u == v:
									break
							group_num += 1
						if parent[v] != -1:
							low[parent[v]] = min(low[parent[v]], low[v])
		for (i, x) in enumerate(ids):
			ids[i] = group_num - 1 - x
		return (group_num, ids)

	def scc(self):
		(group_num, ids) = self.scc_ids()
		groups = [[] for _ in range(group_num)]
		for (i, x) in enumerate(ids):
			groups[x].append(i)
		return groups
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
(N, M) = map(int, readline().split())
ab = list(map(int, read().split()))
sg = scc_graph(N)
it = iter(ab)
for (a, b) in zip(it, it):
	sg.add_edge(a, b)
scc = sg.scc()
print(len(scc))
for group in scc:
	print(str(len(group)) + ' ' + ' '.join(map(str, group)))


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	from collections import deque

	def SCC(adj, adj_rev):
		N = len(adj) - 1
		seen = [0] * (N + 1)
		compressed = [0] * (N + 1)
		order = []
		for v0 in range(1, N + 1):
			if seen[v0]:
				continue
			st = deque()
			st.append(v0)
			while st:
				v = st.pop()
				if v < 0:
					order.append(-v)
				else:
					if seen[v]:
						continue
					seen[v] = 1
					st.append(-v)
					for u in adj[v]:
						st.append(u)
		seen = [0] * (N + 1)
		num = 0
		for v0 in reversed(order):
			if seen[v0]:
				continue
			num += 1
			st = deque()
			st.append(v0)
			seen[v0] = 1
			compressed[v0] = num
			while st:
				v = st.pop()
				for u in adj_rev[v]:
					if seen[u]:
						continue
					seen[u] = 1
					compressed[u] = num
					st.append(u)
		return (num, compressed)

	def construct(adj, num, compressed):
		N = len(adj) - 1
		adj_compressed = [set() for _ in range(num + 1)]
		for v in range(1, N + 1):
			v_cmp = compressed[v]
			for u in adj[v]:
				u_cmp = compressed[u]
				if v_cmp != u_cmp:
					adj_compressed[v_cmp].add(u_cmp)
		return adj_compressed
	(N, M) = map(int, input().split())
	adj = [set() for _ in range(N + 1)]
	adj_rev = [set() for _ in range(N + 1)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		adj[a + 1].add(b + 1)
		adj_rev[b + 1].add(a + 1)
	(num, compressed) = SCC(adj, adj_rev)
	ans = [[] for _ in range(num + 1)]
	for v in range(1, N + 1):
		ans[compressed[v]].append(v - 1)
	print(num)
	for i in range(1, num + 1):
		line = [len(ans[i])] + ans[i]
		print(*line)
main()


import copy
import sys
sys.setrecursionlimit(1000000)

class csr:

	def __init__(s, n, edges):
		s.start = [0] * (n + 1)
		s.elist = [[] for _ in range(len(edges))]
		for e in edges:
			s.start[e.frm + 1] += 1
		for i in range(1, n + 1):
			s.start[i] += s.start[i - 1]
		counter = copy.deepcopy(s.start)
		for e in edges:
			s.elist[counter[e.frm]] = e.to
			counter[e.frm] += 1

class scc_graph:

	def __init__(s, n):
		s._n = n
		s.edges = []

	def num_vertices(s):
		return s._n

	def add_edge(s, frm, to):
		s.edges.append(s.edge(frm, to))

	def scc_ids(s):
		g = csr(s._n, s.edges)
		now_ord = group_num = 0
		visited = []
		low = [0] * s._n
		ord = [-1] * s._n
		ids = [0] * s._n

		def dfs(self, v, now_ord, group_num):
			low[v] = ord[v] = now_ord
			now_ord += 1
			visited.append(v)
			for i in range(g.start[v], g.start[v + 1]):
				to = g.elist[i]
				if ord[to] == -1:
					(now_ord, group_num) = self(self, to, now_ord, group_num)
					low[v] = min(low[v], low[to])
				else:
					low[v] = min(low[v], ord[to])
			if low[v] == ord[v]:
				while True:
					u = visited.pop()
					ord[u] = s._n
					ids[u] = group_num
					if u == v:
						break
				group_num += 1
			return (now_ord, group_num)
		for i in range(s._n):
			if ord[i] == -1:
				(now_ord, group_num) = dfs(dfs, i, now_ord, group_num)
		for i in range(s._n):
			ids[i] = group_num - 1 - ids[i]
		return [group_num, ids]

	def scc(s):
		ids = s.scc_ids()
		group_num = ids[0]
		counts = [0] * group_num
		for x in ids[1]:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for i in range(s._n):
			groups[ids[1][i]].append(i)
		return groups

	class edge:

		def __init__(s, frm, to):
			s.frm = frm
			s.to = to

def main():
	input = sys.stdin.readline
	(n, m) = list(map(int, input().split()))
	ab = [list(map(int, input().split())) for _ in range(m)]
	g = scc_graph(n)
	for i in range(m):
		(u, v) = ab[i]
		g.add_edge(u, v)
	scc = g.scc()
	print(len(scc))
	for v in scc:
		print(len(v), end=' ')
		for x in v:
			print(x, end=' ')
		print('')
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

class SCC:

	def __init__(self, n):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.graph_rev = [[] for i in range(n)]
		self.used = [False] * n

	def add_edge(self, fr, to):
		if fr == to:
			return
		self.graph[fr].append(to)
		self.graph_rev[to].append(fr)

	def dfs(self, node, graph):
		self.used[node] = True
		for nex in graph[node]:
			if self.used[nex]:
				continue
			self.dfs(nex, graph)
		self.order.append(node)

	def first_dfs(self):
		self.used = [False] * self.n
		self.order = []
		for i in range(self.n):
			if self.used[i]:
				continue
			self.dfs(i, self.graph)

	def second_dfs(self):
		self.used = [False] * self.n
		self.ans = []
		for node in reversed(self.order):
			if self.used[node]:
				continue
			self.used[node] = True
			self.order = []
			self.dfs(node, self.graph_rev)
			self.order.reverse()
			self.ans.append(self.order)

	def scc(self):
		self.first_dfs()
		self.second_dfs()
		return self.ans
(n, m) = map(int, input().split())
scc = SCC(n)
for _ in range(m):
	(a, b) = map(int, input().split())
	scc.add_edge(a, b)
ans = scc.scc()
print(len(ans))
for i in ans:
	print(len(i), *i)


import sys
sys.setrecursionlimit(10 ** 7)

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

class SCC:

	def __init__(self, N):
		self.N = N
		self.graph = [[] for _ in range(N)]
		self.graph_rev = [[] for _ in range(N)]
		self.flag = [False] * N

	def add_edge(self, start, end):
		if start == end:
			return
		self.graph[start].append(end)
		self.graph_rev[end].append(start)

	def dfs(self, node, graph):
		self.flag[node] = True
		for n in graph[node]:
			if self.flag[n]:
				continue
			self.dfs(n, graph)
		self.order.append(node)

	def first_dfs(self):
		self.flag = [False] * self.N
		self.order = []
		for i in range(self.N):
			if self.flag[i] == False:
				self.dfs(i, self.graph)

	def second_dfs(self):
		self.flag = [False] * self.N
		self.ans = []
		for n in reversed(self.order):
			if self.flag[n]:
				continue
			self.flag[n] = True
			self.order = []
			self.dfs(n, self.graph_rev)
			self.order.reverse()
			self.ans.append(self.order)

	def scc(self):
		self.first_dfs()
		self.second_dfs()
		return self.ans
(N, M) = MI()
SCC = SCC(N)
for _ in range(M):
	(a, b) = MI()
	SCC.add_edge(a, b)
ANS = SCC.scc()
print(len(ANS))
for s in ANS:
	print(*[len(s)] + s)


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M) = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]
from collections import defaultdict
graph = defaultdict(list)
for (u, v) in edges:
	graph[u].append(v)
	graph[v]

def scc(G):
	preorder = {}
	lowlink = {}
	seen = [False] * N
	scc_queue = []
	i = 0
	ans = []
	for source in range(N):
		if seen[source]:
			continue
		queue = [source]
		while queue:
			v = queue[-1]
			if v not in preorder:
				i = i + 1
				preorder[v] = i
			done = True
			for w in G[v]:
				if w not in preorder:
					queue.append(w)
					done = False
					break
			if done:
				lowlink[v] = preorder[v]
				for w in G[v]:
					if seen[w]:
						continue
					if preorder[w] > preorder[v]:
						lowlink[v] = min([lowlink[v], lowlink[w]])
					else:
						lowlink[v] = min([lowlink[v], preorder[w]])
				queue.pop()
				if lowlink[v] == preorder[v]:
					scc = {v}
					seen[v] = True
					while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
						k = scc_queue.pop()
						scc.add(k)
						seen[k] = True
					ans.append(scc)
				else:
					scc_queue.append(v)
	return ans
SCC = list(scc(graph))
DEBUG = False
print(len(SCC))
if DEBUG:
	seen = set()
for comp in reversed(SCC):
	print(len(comp), *comp)
	if DEBUG:
		for u in comp:
			for v in graph[u]:
				assert v not in seen
		seen.update(comp)


import sys
input = lambda : sys.stdin.readline().rstrip()

def scc(E):
	n = len(E)
	iE = [[] for _ in range(n)]
	for (i, e) in enumerate(E):
		for v in e:
			iE[v].append(i)
	T = []
	done = [0] * n
	ct = 0
	for i0 in range(n):
		if done[i0]:
			continue
		Q = [~i0, i0]
		while Q:
			i = Q.pop()
			if i < 0:
				if done[~i] == 2:
					continue
				done[~i] = 2
				T.append(~i)
				ct += 1
				continue
			if i >= 0:
				if done[i]:
					continue
				done[i] = 1
			for j in E[i]:
				if done[j]:
					continue
				Q.append(~j)
				Q.append(j)
	done = [0] * n
	SCC = []
	for i0 in T[::-1]:
		if done[i0]:
			continue
		L = []
		Q = [~i0, i0]
		while Q:
			i = Q.pop()
			if i < 0:
				if done[~i] == 2:
					continue
				done[~i] = 2
				L.append(~i)
				continue
			if i >= 0:
				if done[i]:
					continue
				done[i] = 1
			for j in iE[i]:
				if done[j]:
					continue
				Q.append(~j)
				Q.append(j)
		SCC.append(L)
	return SCC
(N, M) = map(int, input().split())
X = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	X[x].append(y)
S = scc(X)
print(len(S))
for s in S:
	print(*[len(s)] + s)


class DiGraph:

	def __init__(self, n):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.rev = [[] for _ in range(n)]
		self.deg = [0 for _ in range(n)]

	def add_edge(self, fr, to):
		self.graph[fr].append(to)
		self.rev[to].append(fr)
		self.deg[to] += 1

	def scc_ids(self):
		group = [None for _ in range(self.n)]
		used = [0 for _ in range(self.n)]
		order = []
		for s in range(self.n):
			if not used[s]:
				stack = [s]
				used[s] = 1
				while stack:
					node = stack.pop()
					movable = False
					for adj in self.graph[node]:
						if not used[adj]:
							movable = True
							used[adj] = 1
							stack.append(node)
							stack.append(adj)
							break
					if not movable:
						order.append(node)
		used = [0 for _ in range(self.n)]
		count = 0
		for s in order[::-1]:
			if not used[s]:
				stack = [s]
				group[s] = count
				while stack:
					node = stack.pop()
					used[node] = 1
					for adj in self.rev[node]:
						if not used[adj]:
							group[adj] = count
							stack.append(adj)
				count += 1
		return (group, count)

	def scc(self):
		(group, count) = self.scc_ids()
		scc = [[] for _ in range(count)]
		for (i, k) in enumerate(group):
			scc[k].append(i)
		return scc
(N, M) = map(int, input().split())
dg = DiGraph(N)
for i in range(M):
	dg.add_edge(*list(map(int, input().split())))
scc = dg.scc()
print(len(scc))
for c in scc:
	print(len(c), ' '.join(map(str, c)))


def argsort(arr, reverse=False, shift=20):
	N = len(arr)
	tmp = [0] * N
	for i in range(N):
		tmp[i] = arr[i] << shift | i
	tmp = sorted(tmp, reverse=reverse)
	out = [0] * N
	mask = (1 << shift) - 1
	for j in range(N):
		i = tmp[j] & mask
		out[j] = i
	return out

def dfs(G1, a0, seen, postorder, order):
	todo = [~a0, a0]
	while todo:
		a = todo.pop()
		if a >= 0:
			seen[a] = 1
			for b in G1[a]:
				if seen[b]:
					continue
				todo.append(~b)
				todo.append(b)
		elif postorder[~a] == -1:
			postorder[~a] = order
			order += 1
	return (seen, postorder, order)

def dfs2(G2, v, seen):
	todo = [v]
	seen[v] = 1
	cc = [v]
	while todo:
		v = todo.pop()
		for next_v in G2[v]:
			if seen[next_v]:
				continue
			seen[next_v] = 1
			todo.append(next_v)
			cc.append(next_v)
	return (cc, seen)

def scc(G1, G2):
	N = len(G1)
	seen = [0] * N
	postorder = [-1] * N
	order = 0
	for i in range(N):
		if seen[i]:
			continue
		(seen, postorder, order) = dfs(G1, i, seen, postorder, order)
	seen = [0] * N
	scclist = []
	for i in argsort(postorder, reverse=True):
		if seen[i]:
			continue
		(cc, seen) = dfs2(G2, i, seen)
		scclist.append(cc)
	return scclist

def main():
	(N, M) = map(int, input().split())
	G1 = [[] for _ in range(N)]
	G2 = [[] for _ in range(N)]
	for i in range(M):
		(a, b) = map(int, input().split())
		G1[a].append(b)
		G2[b].append(a)
	scclist = scc(G1, G2)
	print(len(scclist))
	for cc in scclist:
		print(len(cc), *cc)
main()


class Digraph:

	def __init__(self, vertex=[]):
		self.vertex = set(vertex)
		self.edge_number = 0
		self.vertex_number = len(vertex)
		self.adjacent_out = {v: set() for v in vertex}
		self.adjacent_in = {v: set() for v in vertex}

	def add_vertex(self, *adder):
		for v in adder:
			if v not in self.vertex:
				self.adjacent_in[v] = set()
				self.adjacent_out[v] = set()
				self.vertex_number += 1
				self.vertex.add(v)

	def add_edge(self, From, To):
		for v in [From, To]:
			if v not in self.vertex:
				self.add_vertex(v)
		if To not in self.adjacent_in[From]:
			self.edge_number += 1
		self.adjacent_out[From].add(To)
		self.adjacent_in[To].add(From)

	def remove_edge(self, From, To):
		for v in [From, To]:
			if v not in self.vertex:
				self.add_vertex(v)
		if To in self.adjacent_out[From]:
			self.adjacent_out[From].remove(To)
			self.adjacent_in[To].remove(From)
			self.edge_number -= 1

	def remove_vertex(self, *vertexes):
		for v in vertexes:
			if v in self.vertex:
				self.vertex_number -= 1
				for u in self.adjacent_out[v]:
					self.adjacent_in[u].remove(v)
					self.edge_number -= 1
				del self.adjacent_out[v]
				for u in self.adjacent_in[v]:
					self.adjacent_out[u].remove(v)
					self.edge_number -= 1
				del self.adjacent_in[v]

	def add_walk(self, *walk):
		N = len(walk)
		for k in range(N - 1):
			self.add_edge(walk[k], walk[k + 1])

	def add_cycle(self, *cycle):
		self.add_walk(*cycle)
		self.add_edge(cycle[-1], cycle[0])

	def __vertex_swap(self, p, q):
		self.vertex.sort()

	def vertex_exist(self, v):
		return v in self.vertex

	def edge_exist(self, From, To):
		if not (self.vertex_exist(From) and self.vertex_exist(To)):
			return False
		return To in self.adjacent_out[From]

	def neighbohood(self, v):
		if not self.vertex_exist(v):
			return []
		return list(self.adjacent[v])

	def out_degree(self, v):
		if not self.vertex_exist(v):
			return 0
		return len(self.adjacent_out[v])

	def in_degree(self, v):
		if not self.vertex_exist(v):
			return 0
		return len(self.adjacent_in[v])

	def degree(self, v):
		if not self.vertex_exist(v):
			return 0
		return self.out_degree(v) - self.in_degree(v)

	def vertex_count(self):
		return len(self.vertex)

	def edge_count(self):
		return self.edge_number

	def connected_component(self, v):
		pass

def Topological_Sort(D):
	from collections import deque
	X = {v: D.in_degree(v) for v in D.vertex}
	Q = deque([v for v in D.vertex if X[v] == 0])
	S = []
	while Q:
		u = Q.pop()
		S.append(u)
		for v in D.adjacent_out[u]:
			X[v] -= 1
			if X[v] == 0:
				Q.append(v)
	return S

def Strongly_Connected_Component_Decomposition(D, Mode=0):
	import sys
	from collections import deque
	T = {x: -1 for x in D.vertex}
	Q = deque([])

	def f(v):
		T[v] = 0
		for w in D.adjacent_out[v]:
			if T[w] == -1:
				f(w)
		Q.appendleft(v)
		T[v] = len(Q)
	x = D.vertex.pop()
	D.vertex.add(x)
	RT = sys.getrecursionlimit()
	sys.setrecursionlimit(3 * 10 ** 5)
	for v in D.vertex:
		if T[v] == -1:
			f(v)
	sys.setrecursionlimit(RT)
	T = {x: -1 for x in D.vertex}
	C = []
	p = 0
	for v in Q:
		if T[v] == -1:
			T[v] = p
			P = [v]
			R = deque([v])
			while R:
				u = R.popleft()
				for w in D.adjacent_in[u]:
					if T[w] == -1:
						T[w] = p
						R.append(w)
						P.append(w)
			C.append(P)
			p += 1
	if Mode == 1:
		return T
	elif Mode == 2:
		return (C, T)
	else:
		return C
(N, M) = map(int, input().split())
D = Digraph(list(range(N)))
for _ in range(M):
	(a, b) = map(int, input().split())
	D.add_edge(a, b)
C = Strongly_Connected_Component_Decomposition(D)
X = [''] * len(C)
for i in range(len(C)):
	X[i] = '{} {}'.format(len(C[i]), ' '.join(map(str, C[i])))
print(len(C))
print('\n'.join(X))


def StrongConnectedComponent(g, S):
	from collections import deque
	S = deque()
	q = deque()
	n = len(g)
	gp = [1] * n
	for i in range(n):
		if gp[i] == 1:
			q.append(i)
			while q:
				v = q.pop()
				if v < 0:
					if gp[~v] == 0:
						gp[~v] = -1
						S.append(~v)
				elif gp[v] == 1:
					q.append(~v)
					gp[v] = 0
					for c in rg[v]:
						if gp[c] == 1:
							q.append(c)
	q = deque()
	gp = [-1] * n
	g_scc = []
	cnt = 0
	while S:
		v = S.pop()
		if gp[v] == -1:
			q.append(v)
			gp[v] = cnt
			sv = set()
			while q:
				w = q.pop()
				for c in g[w]:
					if gp[c] == -1:
						q.append(c)
						gp[c] = gp[w]
					elif gp[c] != cnt:
						sv.add(gp[c])
			cnt += 1
			g_scc.append(sv)
	return (gp, g_scc)
import sys
readline = sys.stdin.readline
read = sys.stdin.read
(n, m) = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, readline().split())
	g[a].append(b)
	rg[b].append(a)
(gp, scc) = StrongConnectedComponent(g, rg)
v = max(gp) + 1
ans = [[] for _ in range(v)]
for (i, gpi) in enumerate(gp):
	ans[gpi].append(i)
print(v)
for lst in ans[::-1]:
	print(len(lst), end=' ')
	print(*lst)


def SCC_Tarjan(g):

	def dfs(v):
		nonlocal idx
		used[v] = 1
		pre[v] = low[v] = idx
		idx += 1
		S.append(v)
		onS[v] = 1
		for c in g[v]:
			if not used[c]:
				dfs(c)
				low[v] = min(low[v], low[c])
			elif onS[c]:
				low[v] = min(low[v], pre[c])
		used[v] = 2
		if low[v] == pre[v]:
			cc = []
			while True:
				w = S.pop()
				onS[w] = 0
				cc.append(w)
				if w == v:
					break
			scc.append(cc)
	n = len(g)
	used = [0] * n
	pre = [0] * n
	low = [0] * n
	onS = [0] * n
	idx = 0
	S = []
	scc = []
	for i in range(n):
		if not used[i]:
			dfs(i)
	return scc
import sys
readline = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 6)
(n, m) = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, readline().split())
	g[a].append(b)
gp = SCC_Tarjan(g)
print(len(gp))
for lst in gp[::-1]:
	print(*[len(lst)] + lst)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def scc(g):
	n = len(g)
	cmp = [0] * n
	ord = [-1] * n
	fin = [False] * n
	low = [0] * n
	visited = []
	num = 0
	k = 0
	for x in range(n):
		if ord[x] != -1:
			continue
		st = [~x, x]
		while st:
			v = st.pop()
			if v >= 0:
				if ord[v] != -1:
					continue
				ord[v] = num
				low[v] = num
				num += 1
				visited.append(v)
				for w in g[v]:
					if ord[w] == -1:
						st.append(~w)
						st.append(w)
			else:
				v = ~v
				if fin[v]:
					continue
				fin[v] = True
				for w in g[v]:
					if ord[w] < ord[v]:
						if ord[w] < low[v]:
							low[v] = ord[w]
					elif ord[w] < n:
						if low[w] < low[v]:
							low[v] = low[w]
				if ord[v] == low[v]:
					while True:
						w = visited.pop()
						cmp[w] = k
						ord[w] = n
						if w == v:
							break
					k += 1
	cmp = [k - 1 - x for x in cmp]
	return (k, cmp)
(n, m) = map(int, readline().split())
g = [[] for _ in range(n)]
ab = map(int, read().split())
for (a, b) in zip(ab, ab):
	g[a].append(b)
(k, cmp) = scc(g)
print(k)
vs = [[] for _ in range(k)]
ans = []
for (i, x) in enumerate(cmp):
	vs[x].append(i)
for v in vs:
	ans.append(f'{len(v)} ' + ' '.join(map(str, v)))
print('\n'.join(ans))


import sys
sys.setrecursionlimit(1000000)
(n, m) = map(int, input().split())
e = [[] for _ in range(n)]
e_rev = [[] for _ in range(n)]
for i in range(m):
	(ai, bi) = map(int, input().split())
	e[ai].append(bi)
	e_rev[bi].append(ai)
p_ord = []
used = [0] * n

def dfs(v):
	used[v] = 1
	for u in e[v]:
		if not used[u]:
			dfs(u)
	p_ord.append(v)
for i in range(n):
	if not used[i]:
		dfs(i)
compo = [0] * n
used = [0] * n

def dfs_rev(v, c):
	compo[v] = c
	used[v] = 1
	for u in e_rev[v]:
		if not used[u]:
			dfs_rev(u, c)
cnt = 0
for i in reversed(p_ord):
	if not used[i]:
		dfs_rev(i, cnt)
		cnt += 1
cc = [[] for _ in range(cnt + 1)]
for i in range(n):
	cc[compo[i]].append(i)
print(len([cci for cci in cc if cci]))
for cci in cc:
	if cci:
		print(len(cci), *cci)


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(6 * 10 ** 5)

class StronglyConnectedComponets:

	def __init__(self, n: int) -> None:
		self.n = n
		self.edges = [[] for _ in range(n)]
		self.rev_edeges = [[] for _ in range(n)]
		self.vs = []
		self.order = [0] * n
		self.used = [False] * n

	def add_edge(self, from_v: int, to_v: int) -> None:
		self.edges[from_v].append(to_v)
		self.rev_edeges[to_v].append(from_v)

	def dfs(self, v: int) -> None:
		self.used[v] = True
		for child in self.edges[v]:
			if not self.used[child]:
				self.dfs(child)
		self.vs.append(v)

	def rdfs(self, v: int, k: int) -> None:
		self.used[v] = True
		self.order[v] = k
		for child in self.rev_edeges[v]:
			if not self.used[child]:
				self.rdfs(child, k)

	def run(self) -> int:
		self.used = [False] * self.n
		self.vs.clear()
		for v in range(self.n):
			if not self.used[v]:
				self.dfs(v)
		self.used = [False] * self.n
		k = 0
		for v in reversed(self.vs):
			if not self.used[v]:
				self.rdfs(v, k)
				k += 1
		return k

def main() -> None:
	(N, M) = map(int, input().split())
	scc = StronglyConnectedComponets(N)
	for _ in range(M):
		(u, v) = map(int, input().split())
		scc.add_edge(u, v)
	scc.run()
	ans_size = max(scc.order) + 1
	ans = [[] for _ in range(ans_size)]
	for (i, c) in enumerate(scc.order):
		ans[c].append(i)
	print(ans_size)
	for row in ans:
		print(len(row), *row)
main()


import sys
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 9 + 1
MOD = 10 ** 9 + 7

def get_strongly_connected_components(edges, num_vertex):
	from collections import defaultdict
	reverse_edges = defaultdict(list)
	for v1 in edges:
		for v2 in edges[v1]:
			reverse_edges[v2].append(v1)
	terminate_order = []
	done = [0] * num_vertex
	count = 0
	for i0 in range(num_vertex):
		if done[i0]:
			continue
		queue = [~i0, i0]
		while queue:
			i = queue.pop()
			if i < 0:
				if done[~i] == 2:
					continue
				done[~i] = 2
				terminate_order.append(~i)
				count += 1
				continue
			if i >= 0:
				if done[i]:
					continue
				done[i] = 1
			for j in edges[i]:
				if done[j]:
					continue
				queue.append(~j)
				queue.append(j)
	done = [0] * num_vertex
	result = []
	for i0 in terminate_order[::-1]:
		if done[i0]:
			continue
		component = []
		queue = [~i0, i0]
		while queue:
			i = queue.pop()
			if i < 0:
				if done[~i] == 2:
					continue
				done[~i] = 2
				component.append(~i)
				continue
			if i >= 0:
				if done[i]:
					continue
				done[i] = 1
			for j in reverse_edges[i]:
				if done[j]:
					continue
				queue.append(~j)
				queue.append(j)
		result.append(component)
	return result

def debug(*x):
	print(*x, file=sys.stderr)

def solve(N, M, edges):
	scc = get_strongly_connected_components(edges, N)
	print(len(scc))
	for s in scc:
		print(*[len(s)] + s)

def main():
	(N, M) = map(int, input().split())
	from collections import defaultdict
	edges = defaultdict(list)
	for i in range(M):
		(a, b) = map(int, input().split())
		edges[a].append(b)
	solve(N, M, edges)
T1 = '\n6 7\n1 4\n5 2\n3 0\n5 5\n4 1\n0 3\n4 2\n'
TEST_T1 = '\n>>> as_input(T1)\n>>> main()\n4\n1 5\n2 4 1\n1 2\n2 3 0\n'

def _test():
	import doctest
	doctest.testmod()
	g = globals()
	for k in sorted(g):
		if k.startswith('TEST_'):
			doctest.run_docstring_examples(g[k], g, name=k)

def as_input(s):
	import io
	f = io.StringIO(s.strip())
	g = globals()
	g['input'] = lambda : bytes(f.readline(), 'ascii')
	g['read'] = lambda : bytes(f.read(), 'ascii')
input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
if sys.argv[-1] == '-t':
	print('testing')
	_test()
	sys.exit()
main()


from collections import defaultdict
import sys
input = sys.stdin.buffer.readline

def scc(V, E):
	g = [[] for _ in range(len(V))]
	rg = [[] for _ in range(len(V))]
	for (u, v) in E:
		g[u].append(v)
		rg[v].append(u)
	o = []
	done = set()
	for u in V:
		if u in done:
			continue
		s = [(u, True)]
		while s:
			(u, f) = s.pop()
			if f:
				if u in done:
					continue
				done.add(u)
				s.append((u, False))
				for v in g[u]:
					if v in done:
						continue
					s.append((v, True))
			else:
				o.append(u)
	done = set()
	ans = []
	while o:
		u = o.pop()
		if u in done:
			continue
		s = [u]
		vv = [u]
		done.add(u)
		while s:
			u = s.pop()
			for v in rg[u]:
				if v in done:
					continue
				vv.append(v)
				s.append(v)
				done.add(v)
		ans.append(vv)
	return ans

def atcoder_practice2_g():
	(N, M) = map(int, input().split())
	E = []
	for _ in range(M):
		(a, b) = map(int, input().split())
		E.append((a, b))
	V = list(range(N))
	vv = scc(V, E)
	print(len(vv))
	for r in vv:
		print(len(r), *r)

def test():
	g = {1: [2], 5: [2], 2: [4, 3], 3: [4, 7, 6], 4: [5, 8], 6: [9], 7: [8], 8: [9], 9: [7, 10], 10: []}
	V = list(range(1, 11))
	E = []
	for (u, e) in g.items():
		for v in e:
			E.append((u, v))
	vv = scc(V, E)
	for r in vv:
		print(r)
atcoder_practice2_g()


class CSR:

	def __init__(self, n: int, edges: list):
		self.start = [0] * (n + 1)
		self.elist = [0] * len(edges)
		for e in edges:
			self.start[e[0] + 1] += 1
		for i in range(1, n + 1):
			self.start[i] += self.start[i - 1]
		counter = self.start[:]
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class SccGraph:

	def __init__(self, n: int=0):
		self.__n = n
		self.__edges = []

	def __len__(self):
		return self.__n

	def add_edge(self, s: int, t: int):
		assert 0 <= s < self.__n and 0 <= t < self.__n
		self.__edges.append([s, t])

	def __scc_ids(self):
		g = CSR(self.__n, self.__edges)
		now_ord = group_num = 0
		visited = []
		low = [0] * self.__n
		order = [-1] * self.__n
		ids = [0] * self.__n
		parent = [-1] * self.__n
		for root in range(self.__n):
			if order[root] == -1:
				stack = [root, root]
				while stack:
					v = stack.pop()
					if order[v] == -1:
						visited.append(v)
						low[v] = order[v] = now_ord
						now_ord += 1
						for i in range(g.start[v], g.start[v + 1]):
							t = g.elist[i]
							if order[t] == -1:
								stack += [t, t]
								parent[t] = v
							else:
								low[v] = min(low[v], order[t])
					else:
						if low[v] == order[v]:
							while True:
								u = visited.pop()
								order[u] = self.__n
								ids[u] = group_num
								if u == v:
									break
							group_num += 1
						if parent[v] != -1:
							low[parent[v]] = min(low[parent[v]], low[v])
		for (i, x) in enumerate(ids):
			ids[i] = group_num - 1 - x
		return (group_num, ids)

	def scc(self):
		(group_num, ids) = self.__scc_ids()
		counts = [0] * group_num
		for x in ids:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for (i, x) in enumerate(ids):
			groups[x].append(i)
		return groups
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(N, M) = map(int, readline().split())
data = list(map(int, read().split()))
sg = SccGraph(N)
it = iter(data)
for (a, b) in zip(it, it):
	sg.add_edge(a, b)
scc = sg.scc()
print(len(scc))
for group in scc:
	print(*[len(group)] + group)


import sys
input = sys.stdin.readline

def dfs_numbering(st, M, V, ANS, cnt, v):
	ST = [st]
	while len(ST) > 0:
		i = ST[-1]
		if ANS[i] == -1:
			V[i] = v
			end = 1
			for x in M[i]:
				if V[x] == -1:
					ST.append(x)
					end = 0
			if end == 1:
				ST.pop()
				ANS[i] = cnt
				cnt += 1
		else:
			ST.pop()
	return cnt

class scc:

	def __init__(self, n):
		self.n = n
		self.M = [[] for i in range(n)]
		self.IM = [[] for i in range(n)]

	def add_edge(self, frm, to):
		self.M[frm].append(to)
		self.IM[to].append(frm)

	def scc_list(self):
		n = self.n
		V = [-1] * n
		ANS = [-1] * n
		cnt = 0
		for i in range(n):
			if V[i] == -1:
				cnt = dfs_numbering(i, self.M, V, ANS, cnt, 0)
		ANS1 = [[ANS[i], i] for i in range(n)]
		ANS1.sort(reverse=True)
		V = [-1] * n
		ANS = [-1] * n
		v = 0
		for i in range(n):
			if V[ANS1[i][1]] == -1:
				dfs_numbering(ANS1[i][1], self.IM, V, ANS, 0, v)
				v += 1
		FANS = [[] for i in range(v)]
		for i in range(n):
			FANS[V[i]].append(i)
		return FANS
(n, m) = map(int, input().split())
S = scc(n)
for i in range(m):
	(frm, to) = map(int, input().split())
	S.add_edge(frm, to)
ANS = S.scc_list()
print(len(ANS))
for i in range(len(ANS)):
	print(len(ANS[i]), end=' ')
	print(*ANS[i])


import sys
readline = sys.stdin.readline
import sys

def scc(Edge):
	N = len(Edge)
	Edgeinv = [[] for _ in range(N)]
	for vn in range(N):
		for vf in Edge[vn]:
			Edgeinv[vf].append(vn)
	used = [False] * N
	dim = [len(Edge[i]) for i in range(N)]
	order = []
	for st in range(N):
		if not used[st]:
			stack = [st, 0]
			while stack:
				(vn, i) = (stack[-2], stack[-1])
				if not i and used[vn]:
					stack.pop()
					stack.pop()
				else:
					used[vn] = True
					if i < dim[vn]:
						stack[-1] += 1
						stack.append(Edge[vn][i])
						stack.append(0)
					else:
						stack.pop()
						order.append(stack.pop())
	res = [None] * N
	used = [False] * N
	cnt = -1
	for st in order[::-1]:
		if not used[st]:
			cnt += 1
			stack = [st]
			res[st] = cnt
			used[st] = True
			while stack:
				vn = stack.pop()
				for vf in Edgeinv[vn]:
					if not used[vf]:
						used[vf] = True
						res[vf] = cnt
						stack.append(vf)
	M = cnt + 1
	components = [[] for _ in range(M)]
	for i in range(N):
		components[res[i]].append(i)
	tEdge = [[] for _ in range(M)]
	teset = set()
	for vn in range(N):
		tn = res[vn]
		for vf in Edge[vn]:
			tf = res[vf]
			if tn != tf and tn * M + tf not in teset:
				teset.add(tn * M + tf)
				tEdge[tn].append(tf)
	return (res, components, tEdge)
(N, M) = map(int, readline().split())
Edge = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, readline().split())
	Edge[a].append(b)
(R, comp, tE) = scc(Edge)
Ans = [str(len(comp))]
for c in comp:
	Ans.append(f'{len(c)} ' + ' '.join(map(str, c)))
print('\n'.join(Ans))


from collections import deque

class StronglyConnectedComponents:

	def __init__(self, n):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.rev = [[] for _ in range(n)]

	def add_edge(self, fr, to):
		self.graph[fr].append(to)
		self.rev[to].append(fr)

	def scc_id(self):
		group = [0] * self.n
		order = []
		for s in range(self.n):
			if group[s]:
				continue
			stack = deque([s])
			group[s] = -1
			while stack:
				node = stack.pop()
				for adj in self.graph[node]:
					if group[adj]:
						continue
					group[adj] = -1
					stack.append(node)
					stack.append(adj)
					break
				else:
					order.append(node)
		cnt = 0
		for s in order[::-1]:
			if group[s] != -1:
				continue
			stack = deque([s])
			group[s] = cnt
			while stack:
				node = stack.pop()
				for adj in self.rev[node]:
					if group[adj] != -1:
						continue
					group[adj] = cnt
					stack.append(adj)
			cnt += 1
		return (group, cnt)

	def scc(self):
		(group, cnt) = self.scc_id()
		res = [[] for _ in range(cnt)]
		for (i, g) in enumerate(group):
			res[g].append(i)
		return res
import sys
input = sys.stdin.buffer.readline
(N, M) = map(int, input().split())
scc = StronglyConnectedComponents(N)
for _ in range(M):
	(a, b) = map(int, input().split())
	scc.add_edge(a, b)
res = scc.scc()
print(len(res))
for r in res:
	print(len(r), *r)


class convolution:

	def __init__(self, a: list, b: list, mod: int):
		(self.a, self.b) = (a, b)
		(self.n, self.m) = (len(a), len(b))
		self.MOD = mod
		self.g = primitive_root_constexpr(self.MOD)

	def convolution(self) -> list:
		(n, m) = (self.n, self.m)
		(a, b) = (self.a, self.b)
		if not n or not m:
			return []
		if min(n, m) <= 60:
			if n < m:
				(n, m) = (m, n)
				(a, b) = (b, a)
			ans = [0] * (n + m - 1)
			for i in range(n):
				for j in range(m):
					ans[i + j] += a[i] * b[j] % self.MOD
					ans[i + j] %= self.MOD
			return ans
		z = 1 << ceil_pow2(n + m - 1)
		a = self.resize(a, z)
		a = self.butterfly(a)
		b = self.resize(b, z)
		b = self.butterfly(b)
		for i in range(z):
			a[i] = a[i] * b[i] % self.MOD
		a = self.butterfly_inv(a)
		a = a[:n + m - 1]
		iz = self.inv(z)
		a = [x * iz % self.MOD for x in a]
		return a

	def butterfly(self, a: list) -> list:
		n = len(a)
		h = ceil_pow2(n)
		first = True
		sum_e = [0] * 30
		m = self.MOD
		if first:
			first = False
			(es, ies) = ([0] * 30, [0] * 30)
			cnt2 = bsf(m - 1)
			e = self.mypow(self.g, m - 1 >> cnt2)
			ie = self.inv(e)
			for i in range(cnt2, 1, -1):
				es[i - 2] = e
				ies[i - 2] = ie
				e = e * e % m
				ie = ie * ie % m
			now = 1
			for i in range(cnt2 - 2):
				sum_e[i] = es[i] * now % m
				now = now * ies[i] % m
		for ph in range(1, h + 1):
			w = 1 << ph - 1
			p = 1 << h - ph
			now = 1
			for s in range(w):
				offset = s << h - ph + 1
				for i in range(p):
					l = a[i + offset] % m
					r = a[i + offset + p] * now % m
					a[i + offset] = (l + r) % m
					a[i + offset + p] = (l - r) % m
				now = now * sum_e[bsf(~s)] % m
		return a

	def butterfly_inv(self, a: list) -> list:
		n = len(a)
		h = ceil_pow2(n)
		first = True
		sum_ie = [0] * 30
		m = self.MOD
		if first:
			first = False
			(es, ies) = ([0] * 30, [0] * 30)
			cnt2 = bsf(m - 1)
			e = self.mypow(self.g, m - 1 >> cnt2)
			ie = self.inv(e)
			for i in range(cnt2, 1, -1):
				es[i - 2] = e
				ies[i - 2] = ie
				e = e * e % m
				ie = ie * ie % m
			now = 1
			for i in range(cnt2 - 2):
				sum_ie[i] = ies[i] * now % m
				now = es[i] * now % m
		for ph in range(h, 0, -1):
			w = 1 << ph - 1
			p = 1 << h - ph
			inow = 1
			for s in range(w):
				offset = s << h - ph + 1
				for i in range(p):
					l = a[i + offset] % m
					r = a[i + offset + p] % m
					a[i + offset] = (l + r) % m
					a[i + offset + p] = (m + l - r) * inow % m
				inow = sum_ie[bsf(~s)] * inow % m
		return a

	@staticmethod
	def resize(array: list, sz: int) -> list:
		new_array = array + [0] * (sz - len(array))
		return new_array

	def inv(self, x: int):
		if is_prime_constexpr(self.MOD):
			assert x
			return self.mypow(x, self.MOD - 2)
		else:
			eg = inv_gcd(x)
			assert eg[0] == 1
			return eg[1]

	def mypow(self, x: int, n: int) -> int:
		assert 0 <= n
		r = 1
		m = self.MOD
		while n:
			if n & 1:
				r = r * x % m
			x = x * x % m
			n >>= 1
		return r

class dsu:

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

	def merge(self, a: int, b: int) -> int:
		assert 0 <= a and a < self._n
		assert 0 <= b and a < self._n
		x = self.leader(a)
		y = self.leader(b)
		if x == y:
			return x
		if -self.parent_or_size[x] < -self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a: int, b: int) -> bool:
		assert 0 <= a and a < self._n
		assert 0 <= b and a < self._n
		return self.leader(a) == self.leader(b)

	def leader(self, a: int) -> int:
		assert 0 <= a and a < self._n
		if self.parent_or_size[a] < 0:
			return a
		self.parent_or_size[a] = self.leader(self.parent_or_size[a])
		return self.parent_or_size[a]

	def size(self, a: int) -> int:
		assert 0 <= a and a < self._n
		return -self.parent_or_size[self.leader(a)]

	def groups(self):
		leader_buf = [0] * self._n
		group_size = [0] * self._n
		for i in range(self._n):
			leader_buf[i] = self.leader(i)
			group_size[leader_buf[i]] += 1
		result = [[] for _ in range(self._n)]
		for i in range(self._n):
			result[leader_buf[i]].append(i)
		result = [v for v in result if v]
		return result

class fenwick_tree:

	def __init__(self, n):
		self._n = n
		self.data = [0] * n

	def add(self, p: int, x: int):
		assert 0 <= p and p <= self._n
		p += 1
		while p <= self._n:
			self.data[p - 1] += x
			p += p & -p

	def sum(self, l: int, r: int) -> int:
		assert 0 <= l and l <= r and (r <= self._n)
		return self.__sum(r) - self.__sum(l)

	def __sum(self, r: int) -> int:
		s = 0
		while r > 0:
			s += self.data[r - 1]
			r -= r & -r
		return s

def ceil_pow2(n: int) -> int:
	x = 0
	while 1 << x < n:
		x += 1
	return x

def bsf(n: int) -> int:
	return (n & -n).bit_length() - 1

def safe_mod(x: int, m: int) -> int:
	x %= m
	if x < 0:
		x += m
	return x

class barrett:

	def __init__(self, m: int):
		self._m = m
		self.im = -1 // (m + 1)

	def umod(self):
		return self._m

	def mul(self, a: int, b: int) -> int:
		z = a
		z *= b
		x = z * im >> 64
		v = z - x * self._m
		if self._m <= v:
			v += self._m
		return v

def pow_mod_constexpr(x: int, n: int, m: int) -> int:
	if m == 1:
		return 0
	_m = m
	r = 1
	y = safe_mod(x, m)
	while n:
		if n & 1:
			r = r * y % _m
		y = y * y % _m
		n >>= 1
	return r

def is_prime_constexpr(n: int) -> bool:
	if n <= 1:
		return False
	if n == 2 or n == 7 or n == 61:
		return True
	if n % 2 == 0:
		return False
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for a in [2, 7, 61]:
		t = d
		y = pow_mod_constexpr(a, t, n)
		while t != n - 1 and y != 1 and (y != n - 1):
			y = y * y % n
			t <<= 1
		if y != n - 1 and t % 2 == 0:
			return False
	return True

def inv_gcd(self, a: int, b: int) -> tuple:
	a = safe_mod(a, b)
	if a == 0:
		return (b, 0)
	s = b
	t = a
	m0 = 0
	m1 = 1
	while t:
		u = s // t
		s -= t * u
		m0 -= m1 * u
		tmp = s
		s = t
		t = tmp
		tmp = m0
		m0 = m1
		m1 = tmp
	if m0 < 0:
		m0 += b // s
	return (s, m0)

def primitive_root_constexpr(m: int) -> int:
	if m == 2:
		return 1
	if m == 167772161:
		return 3
	if m == 469762049:
		return 3
	if m == 754974721:
		return 11
	if m == 998244353:
		return 3
	divs = [0] * 20
	divs[0] = 2
	cnt = 1
	x = (m - 1) // 2
	while x % 2 == 0:
		x //= 2
	i = 3
	while i * i <= x:
		if x % i == 0:
			divs[cnt] = i
			cnt += 1
			while x % i == 0:
				x //= i
		i += 2
	if x > 1:
		divs[cnt] = x
		cnt += 1
	g = 2
	while True:
		ok = True
		for i in range(cnt):
			if pow_mod_constexpr(g, (m - 1) // div[i], m) == 1:
				ok = False
				break
		if ok:
			return g
		g += 1

class simple_queue:

	def __init__(self):
		self.payload = []
		self.pos = 0

	def size(self):
		return len(self.payload) - self.pos

	def empty(self):
		return self.pos == len(self.payload)

	def push(self, t: int):
		self.payload.append(t)

	def front(self):
		return self.payload[self.pos]

	def clear(self):
		self.payload.clear()
		pos = 0

	def pop(self):
		self.pos += 1

	def pop_front(self):
		self.pos += 1
		return self.payload[~-self.pos]

class csr:

	def __init__(self, n: int, edges: list):
		from copy import deepcopy
		self.start = [0] * (n + 1)
		self.elist = [[] for _ in range(len(edges))]
		for e in edges:
			self.start[e[0] + 1] += 1
		for i in range(1, n + 1):
			self.start[i] += self.start[i - 1]
		counter = deepcopy(self.start)
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class scc_graph:
	edges = []

	def __init__(self, n: int):
		self._n = n
		self.now_ord = 0
		self.group_num = 0

	def num_vertices(self):
		return self._n

	def add_edge(self, _from: int, _to: int):
		self.edges.append((_from, [_to]))

	def scc_ids(self):
		g = csr(self._n, self.edges)
		visited = []
		low = [0] * self._n
		ord = [-1] * self._n
		ids = [0] * self._n

		def dfs(s, v: int):
			low[v] = ord[v] = self.now_ord
			self.now_ord += 1
			visited.append(v)
			for i in range(g.start[v], g.start[v + 1]):
				to = g.elist[i][0]
				if ord[to] == -1:
					s(s, to)
					low[v] = min(low[v], low[to])
				else:
					low[v] = min(low[v], ord[to])
			if low[v] == ord[v]:
				while True:
					u = visited.pop()
					ord[u] = self._n
					ids[u] = self.group_num
					if u == v:
						break
				self.group_num += 1
		for i in range(self._n):
			if ord[i] == -1:
				dfs(dfs, i)
		for i in range(self._n):
			ids[i] = self.group_num - 1 - ids[i]
		return (self.group_num, ids)

	def scc(self):
		ids = self.scc_ids()
		group_num = ids[0]
		counts = [0] * group_num
		for x in ids[1]:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for i in range(self._n):
			groups[ids[1][i]].append(i)
		return groups

class lazy_segtree:

	def __init__(self, op, e, mapping, composition, id, v: list):
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.id = id
		self._n = len(v)
		self.log = ceil_pow2(self._n)
		self.size = 1 << self.log
		self.lz = [self.id()] * self.size
		self.d = [self.e()] * (2 * self.size)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		return self.d[p]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (r <= self._n)
		if l == r:
			return self.e()
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r >> i)
		(sml, smr) = (self.e(), self.e())
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p: int, f):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def apply(self, l: int, r: int, f):
		assert 0 <= l and l <= r and (r <= self._n)
		if l == r:
			return
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r - 1 >> i)
		(l2, r2) = (l, r)
		while l < r:
			if l & 1:
				self.__all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				self.__all_apply(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l2, r2)
		for i in range(1, self.log + 1):
			if l >> i << i != l:
				self.__update(l >> i)
			if r >> i << i != r:
				self.__update(r >> i)

	def max_right(self, l: int, g):
		assert 0 <= l and l <= self._n
		if l == self._n:
			return self._n
		l += self.size
		for i in range(self.log, 0, -1):
			self.__push(l >> i)
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.__push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, g):
		assert 0 <= r and r <= self._n
		if r == 0:
			return 0
		r += self.size
		for i in range(self.log, 0, -1):
			self.__push(r >> i)
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.__push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

	def __all_apply(self, k: int, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def __push(self, k: int):
		self.__all_apply(2 * k, self.lz[k])
		self.__all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.id()

def pow_mod(x: int, n: int, m: int) -> int:
	assert 0 <= n and 1 <= m
	if m == 1:
		return 0
	bt = barrett(m)
	r = 1
	y = safe_mod(x, m)
	while n:
		if n & 1:
			r = bt.mul(r, y)
		y = bt.mul(y, y)
		n >>= 1
	return n

def inv_mod(x: int, m: int) -> int:
	assert 1 <= m
	z = inv_gcd(x, m)
	assert z[0] == 1
	return z[1]

def crt(r: list, m: list) -> tuple:
	assert len(r) == len(m)
	n = len(r)
	r0 = 0
	m0 = 1
	for i in range(n):
		assert 1 <= m[i]
		r1 = safe_mod(r[i], m[i])
		m1 = m[i]
		if m0 < m1:
			(r0, r1) = (r1, r0)
			(m0, m1) = (m1, m0)
		if m0 % m1 == 0:
			if r0 % m1 != r1:
				return (0, 0)
			continue
		(g, im) = inv_gcd(m0, m1)
		u1 = m1 // g
		if (r1 - r0) % g:
			return (0, 0)
		x = (r1 - r0) // g % u1 * im % u1
		r0 += x * m0
		m0 *= u1
		if r0 < 0:
			r0 += m0
	return (r0, m0)

def floor_sum(n: int, m: int, a: int, b: int) -> int:
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += n * (b // m)
		bb %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

class mf_graph:
	numeric_limits_max = 10 ** 18

	def __init__(self, n: int):
		self._n = n
		self.g = [[] for _ in range(self._n)]
		self.pos = []

	def add_edge(self, _from: int, _to: int, cap: int) -> int:
		assert 0 <= _from and _from < self._n
		assert 0 <= _to and _to < self._n
		assert 0 <= cap
		m = len(self.pos)
		self.pos.append((_from, len(self.g[_from])))
		self.g[_from].append(self._edge(_to, len(self.g[_to]), cap))
		self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0))
		return m

	class edge:

		def __init__(s, _from: int, _to: int, cap: int, flow: int):
			s._from = _from
			s._to = _to
			s.cap = cap
			s.flow = flow

	def get_edge(self, i: int) -> edge:
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)

	def edges(self) -> list:
		m = len(self.pos)
		result = [self.get_edge(i) for i in range(m)]
		return result

	def change_edge(self, i: int, new_cap: int, new_flow: int):
		m = len(self.pos)
		assert 0 <= i and i < m
		assert 0 <= new_flow and new_flow <= new_cap
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		_e.cap = new_cap - new_flow
		_re.cap = new_flow

	def flow(self, s: int, t: int):
		return self.flow_(s, t, self.numeric_limits_max)

	def flow_(self, s: int, t: int, flow_limit: int) -> int:
		assert 0 <= s and s < self._n
		assert 0 <= t and t < self._n
		level = [0] * self._n
		it = [0] * self._n

		def bfs():
			for i in range(self._n):
				level[i] = -1
			level[s] = 0
			que = deque([s])
			while que:
				v = que.popleft()
				for e in self.g[v]:
					if e.cap == 0 or level[e.to] >= 0:
						continue
					level[e.to] = level[v] + 1
					if e.to == t:
						return
					que.append(e.to)

		def dfs(self_, v: int, up: int) -> int:
			if v == s:
				return up
			res = 0
			level_v = level[v]
			for i in range(it[v], len(self.g[v])):
				it[v] = i
				e = self.g[v][i]
				if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0:
					continue
				d = self_(self_, e.to, min(up - res, self.g[e.to][e.rev].cap))
				if d <= 0:
					continue
				self.g[v][i].cap += d
				self.g[e.to][e.rev].cap -= d
				res += d
				if res == up:
					break
			return res
		flow = 0
		while flow < flow_limit:
			bfs()
			if level[t] == -1:
				break
			for i in range(self._n):
				it[i] = 0
			while flow < flow_limit:
				f = dfs(dfs, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s: int) -> list:
		visited = [False] * self._n
		que = deque([s])
		while que:
			p = que.popleft()
			visited[p] = True
			for e in self.g[p]:
				if e.cap and (not visited[e.to]):
					visited[e.to] = True
					que.append(e.to)
		return visited

	class _edge:

		def __init__(s, to: int, rev: int, cap: int):
			s.to = to
			s.rev = rev
			s.cap = cap

class mcf_graph:
	numeric_limits_max = 10 ** 18

	def __init__(self, n: int):
		self._n = n
		self.g = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, _from: int, _to: int, cap: int, cost: int) -> int:
		assert 0 <= _from and _from < self._n
		assert 0 <= _to and _to < self._n
		m = len(self.pos)
		self.pos.append((_from, len(self.g[_from])))
		self.g[_from].append(self._edge(_to, len(self.g[_to]), cap, cost))
		self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0, -cost))
		return m

	class edge:

		def __init__(s, _from: int, _to: int, cap: int, flow: int, cost: int):
			s._from = _from
			s._to = _to
			s.cap = cap
			s.flow = flow
			s.cost = cost

	def get_edge(self, i: int) -> edge:
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)

	def edges(self) -> list:
		m = len(self.pos)
		result = [self.get_edge(i) for i in range(m)]
		return result

	def flow(self, s: int, t: int) -> edge:
		return self.flow_(s, t, self.numeric_limits_max)

	def flow_(self, s: int, t: int, flow_limit: int) -> edge:
		return self.__slope(s, t, flow_limit)[-1]

	def slope(self, s: int, t: int) -> list:
		return self.slope_(s, t, self.numeric_limits_max)

	def slope_(self, s: int, t: int, flow_limit: int) -> list:
		return self.__slope(s, t, flow_limit)

	def __slope(self, s: int, t: int, flow_limit: int) -> list:
		assert 0 <= s and s < self._n
		assert 0 <= t and t < self._n
		assert s != t
		dual = [0] * self._n
		dist = [0] * self._n
		(pv, pe) = ([-1] * self._n, [-1] * self._n)
		vis = [False] * self._n

		def dual_ref():
			for i in range(self._n):
				dist[i] = self.numeric_limits_max
				pv[i] = -1
				pe[i] = -1
				vis[i] = False

			class Q:

				def __init__(s, key: int, to: int):
					s.key = key
					s.to = to

				def __lt__(s, r):
					return s.key < r.key
			que = []
			dist[s] = 0
			heappush(que, Q(0, s))
			while que:
				v = heappop(que).to
				if vis[v]:
					continue
				vis[v] = True
				if v == t:
					break
				for i in range(len(self.g[v])):
					e = self.g[v][i]
					if vis[e.to] or not e.cap:
						continue
					cost = e.cost - dual[e.to] + dual[v]
					if dist[e.to] - dist[v] > cost:
						dist[e.to] = dist[v] + cost
						pv[e.to] = v
						pe[e.to] = i
						heappush(que, Q(dist[e.to], e.to))
			if not vis[t]:
				return False
			for v in range(self._n):
				if not vis[v]:
					continue
				dual[v] -= dist[t] - dist[v]
			return True
		flow = 0
		cost = 0
		prev_cost = -1
		result = []
		result.append((flow, cost))
		while flow < flow_limit:
			if not dual_ref():
				break
			c = flow_limit - flow
			v = t
			while v != s:
				c = min(c, self.g[pv[v]][pe[v]].cap)
				v = pv[v]
			v = t
			while v != s:
				e = self.g[pv[v]][pe[v]]
				e.cap -= c
				self.g[v][e.rev].cap += c
				v = pv[v]
			d = -dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				result.pop()
			result.append((flow, cost))
			prev_cost = cost
		return result

	class _edge:

		def __init__(s, to: int, rev: int, cap: int, cost: int):
			s.to = to
			s.rev = rev
			s.cap = cap
			s.cost = cost

class Mint:
	modint1000000007 = 1000000007
	modint998244353 = 998244353

	def __init__(self, v: int=0):
		self.m = self.modint1000000007
		self.x = v % self.__umod()

	def inv(self):
		if is_prime_constexpr(self.__umod()):
			assert self.x
			return self.pow_(self.__umod() - 2)
		else:
			eg = inv_gcd(self.x, self.m)
			assert eg[0] == 1
			return eg[2]

	def __str__(self):
		return str(self.x)

	def __le__(self, other):
		return self.x <= Mint.__get_val(other)

	def __lt__(self, other):
		return self.x < Mint.__get_val(other)

	def __ge__(self, other):
		return self.x >= Mint.__get_val(other)

	def __gt(self, other):
		return self.x > Mint.__get_val(other)

	def __eq__(self, other):
		return self.x == Mint.__get_val(other)

	def __iadd__(self, other):
		self.x += Mint.__get_val(other)
		if self.x >= self.__umod():
			self.x -= self.__umod()
		return self

	def __add__(self, other):
		_v = Mint(self.x)
		_v += other
		return _v

	def __isub__(self, other):
		self.x -= Mint.__get_val(other)
		if self.x >= self.__umod():
			self.x += self.__umod()
		return self

	def __sub__(self, other):
		_v = Mint(self.x)
		_v -= other
		return _v

	def __rsub__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v -= self
		return _v

	def __imul__(self, other):
		self.x = self.x * Mint.__get_val(other) % self.__umod()
		return self

	def __mul__(self, other):
		_v = Mint(self.x)
		_v *= other
		return _v

	def __itruediv__(self, other):
		self.x = self.x / Mint.__get_val(other) % self.__umod()
		return self

	def __truediv__(self, other):
		_v = Mint(self.x)
		_v /= other
		return _v

	def __rtruediv__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v /= self
		return _v

	def __ifloordiv__(self, other):
		other = other if isinstance(other, Mint) else Mint(other)
		self *= other.inv()
		return self

	def __floordiv__(self, other):
		_v = Mint(self.x)
		_v //= other
		return _v

	def __rfloordiv__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v //= self
		return _v

	def __pow__(self, other):
		_v = Mint(pow(self.x, Mint.__get_val(other), self.__umod()))
		return _v

	def __rpow__(self, other):
		_v = Mint(pow(Mint.__get_val(other), self.x, self.__umod()))
		return _v

	def __imod__(self, other):
		self.x %= Mint.__get_val(other)
		return self

	def __mod__(self, other):
		_v = Mint(self.x)
		_v %= other
		return _v

	def __rmod__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v %= self
		return _v

	def __ilshift__(self, other):
		self.x <<= Mint.__get_val(other)
		return self

	def __irshift__(self, other):
		self.x >>= Mint.__get_val(other)
		return self

	def __lshift__(self, other):
		_v = Mint(self.x)
		_v <<= other
		return _v

	def __rshift__(self, other):
		_v = Mint(self.x)
		_v >>= other
		return _v

	def __rlshift__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v <<= self
		return _v

	def __rrshift__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v >>= self
		return _v
	__repr__ = __str__
	__radd__ = __add__
	__rmul__ = __mul__

	def __umod(self):
		return self.m

	@staticmethod
	def __get_val(val):
		return val.x if isinstance(val, Mint) else val

	def pow_(self, n: int):
		assert 0 <= n
		x = Mint(self.x)
		r = 1
		while n:
			if n & 1:
				r *= x
			x *= x
			n >>= 1
		return r

	def val(self):
		return self.x

	def mod(self):
		return self.m

	def raw(self, v):
		x = Mint()
		x.x = v
		return x

class scc_graph_sub:

	def __init__(self, n):
		self.internal = scc_graph(n)

	def add_edge(self, _from, _to):
		n = self.internal.num_vertices()
		assert 0 <= _from and _from < n
		assert 0 <= _to and _to < n
		self.internal.add_edge(_from, _to)

	def scc(self):
		return self.internal.scc()

class segtree:

	def __init__(self, op, e, v: list):
		self._n = len(v)
		self.log = ceil_pow2(self._n)
		self.size = 1 << self.log
		self.op = op
		self.e = e
		self.d = [self.e()] * (self.size * 2)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> i)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		return self.d[p + self.size]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (r <= self._n)
		l += self.size
		r += self.size
		(sml, smr) = (self.e(), self.e())
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def max_right(self, l: int, f):
		assert 0 <= l and l <= self._n
		assert f(self.e())
		if l == self._n:
			return self._n
		l += self.size
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not f(self.op(sm, self.d[l])):
				while l < self.size:
					l = 2 * l
					if f(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, f):
		assert 0 <= r and r <= self._n
		assert f(self.e())
		if r == 0:
			return 0
		r += self.size
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not f(self.op(self.d[r], sm)):
				while r < self.size:
					r = 2 * r + 1
					if f(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

def sa_native(s: list):
	from functools import cmp_to_key

	def mycmp(r, l):
		if l == r:
			return -1
		while l < n and r < n:
			if s[l] != s[r]:
				return 1 if s[l] < s[r] else -1
			l += 1
			r += 1
		return 1 if l == n else -1
	n = len(s)
	sa = [i for i in range(n)]
	sa.sort(key=cmp_to_key(mycmp))
	return sa

def sa_doubling(s: list):
	from functools import cmp_to_key

	def mycmp(y, x):
		if rnk[x] != rnk[y]:
			return 1 if rnk[x] < rnk[y] else -1
		rx = rnk[x + k] if x + k < n else -1
		ry = rnk[y + k] if y + k < n else -1
		return 1 if rx < ry else -1
	n = len(s)
	sa = [i for i in range(n)]
	rnk = s
	tmp = [0] * n
	k = 1
	while k < n:
		sa.sort(key=cmp_to_key(mycmp))
		tmp[sa[0]] = 0
		for i in range(1, n):
			tmp[sa[i]] = tmp[sa[i - 1]]
			if mycmp(sa[i], sa[i - 1]):
				tmp[sa[i]] += 1
		(tmp, rnk) = (rnk, tmp)
		k *= 2
	return sa

def sa_is(s: list, upper: int):
	THRESHOLD_NATIVE = 10
	THRESHOLD_DOUBLING = 40
	n = len(s)
	if n == 0:
		return []
	if n == 1:
		return [0]
	if n == 2:
		if s[0] < s[1]:
			return [0, 1]
		else:
			return [1, 0]
	if n < THRESHOLD_NATIVE:
		return sa_native(s)
	if n < THRESHOLD_DOUBLING:
		return sa_doubling(s)
	sa = [0] * n
	ls = [False] * n
	for i in range(n - 2, -1, -1):
		ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
	sum_l = [0] * (upper + 1)
	sum_s = [0] * (upper + 1)
	for i in range(n):
		if not ls[i]:
			sum_s[s[i]] += 1
		else:
			sum_l[s[i] + 1] += 1
	for i in range(upper + 1):
		sum_s[i] += sum_l[i]
		if i < upper:
			sum_l[i + 1] += sum_s[i]

	def induce(lms: list):
		from copy import copy
		for i in range(n):
			sa[i] = -1
		buf = copy(sum_s)
		for d in lms:
			if d == n:
				continue
			sa[buf[s[d]]] = d
			buf[s[d]] += 1
		buf = copy(sum_l)
		sa[buf[s[n - 1]]] = n - 1
		buf[s[n - 1]] += 1
		for i in range(n):
			v = sa[i]
			if v >= 1 and (not ls[v - 1]):
				sa[buf[s[v - 1]]] = v - 1
				buf[s[v - 1]] += 1
		buf = copy(sum_l)
		for i in range(n - 1, -1, -1):
			v = sa[i]
			if v >= 1 and ls[v - 1]:
				buf[s[v - 1] + 1] -= 1
				sa[buf[s[v - 1] + 1]] = v - 1
	lms_map = [-1] * (n + 1)
	m = 0
	for i in range(1, n):
		if not ls[i - 1] and ls[i]:
			lms_map[i] = m
			m += 1
	lms = [i for i in range(1, n) if not ls[i - 1] and ls[i]]
	induce(lms)
	if m:
		sorted_lms = [v for v in sa if lms_map[v] != -1]
		rec_s = [0] * m
		rec_upper = 0
		rec_s[lms_map[sorted_lms[0]]] = 0
		for i in range(1, m):
			l = sorted_lms[i - 1]
			r = sorted_lms[i]
			end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
			end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
			same = True
			if end_l - l != end_r - r:
				same = False
			else:
				while l < end_l:
					if s[l] != s[r]:
						break
					l += 1
					r += 1
				if l == n or s[l] != s[r]:
					same = False
			if not same:
				rec_upper += 1
			rec_s[lms_map[sorted_lms[i]]] = rec_upper
		rec_sa = sa_is(rec_s, rec_upper)
		for i in range(m):
			sorted_lms[i] = lms[rec_sa[i]]
		induce(sorted_lms)
	return sa

def suffix_array(s: list, upper: int):
	assert 0 <= upper
	for d in s:
		assert 0 <= d and d <= upper
	sa = sa_is(s, upper)
	return sa

def suffix_array2(s: list):
	from functools import cmp_to_key
	n = len(s)
	idx = [i for i in range(n)]
	idx.sort(key=cmp_to_key(lambda l, r: s[l] < s[r]))
	s2 = [0] * n
	now = 0
	for i in range(n):
		if i and s[idx[i - 1]] != s[idx[i]]:
			now += 1
		s2[idx[i]] = now
	return sa_is(s2, now)

def suffix_array3(s: str):
	n = len(s)
	s2 = list(map(ord, s))
	return sa_is(s2, 255)

def lcp_array(s: list, sa: list):
	n = len(s)
	assert n >= 1
	rnk = [0] * n
	for i in range(n):
		rnk[sa[i]] = i
	lcp = [0] * (n - 1)
	h = 0
	for i in range(n):
		if h > 0:
			h -= 1
		if rnk[i] == 0:
			continue
		j = sa[rnk[i] - 1]
		while j + h < n and i + h < n:
			if s[j + h] != s[i + h]:
				break
			h += 1
		lcp[rnk[i] - 1] = h
	return lcp

def lcp_array2(s: str, sa: list):
	n = len(s)
	s2 = list(map(ord, s))
	return lcp_array(s2, sa)

def z_algorithm(s: list):
	n = len(s)
	if n == 0:
		return []
	z = [-1] * n
	z[0] = 0
	j = 0
	for i in range(1, n):
		k = z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
		while i + k < n and s[k] == s[i + k]:
			k += 1
		z[i] = k
		if j + z[j] < i + z[i]:
			j = i
	z[0] = n
	return z

def z_algorithm2(s: str):
	n = len(s)
	s2 = list(map(ord, s))
	return z_algorithm(s2)

class two_sat:

	def __init__(self, n: int):
		self._n = n
		self.scc = scc_graph(2 * n)
		self._answer = [False] * n

	def add_clause(self, i: int, f: bool, j: int, g: bool):
		assert 0 <= i and i < self._n
		assert 0 <= j and j < self._n
		self.scc.add_edge(2 * i + (not f), 2 * j + g)
		self.scc.add_edge(2 * j + (not g), 2 * i + f)

	def satisfiable(self) -> bool:
		_id = self.scc.scc_ids()[1]
		for i in range(self._n):
			if _id[2 * i] == _id[2 * i + 1]:
				return False
			self._answer[i] = _id[2 * i] < _id[2 * i + 1]
		return True

	def answer(self):
		return self._answer
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

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

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

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

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

def Main_A():
	(n, q) = read_ints()
	d = dsu(n)
	for _ in range(q):
		(t, u, v) = read_ints()
		if t == 0:
			d.merge(u, v)
		else:
			print(int(d.same(u, v)))

def Main_B():
	(n, q) = read_ints()
	a = read_int_list()
	fw = fenwick_tree(n)
	for (i, x) in enumerate(a):
		fw.add(i, x)
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			fw.add(query[1], query[2])
		else:
			print(fw.sum(query[1], query[2]))

def Main_C():
	for _ in range(read_int()):
		(n, m, a, b) = read_ints()
		print(floor_sum(n, m, a, b))

def Main_D():
	(n, m) = read_ints()
	grid = [list(read_str()) for _ in range(n)]
	mf = mf_graph(n * m + 2)
	start = n * m
	end = start + 1
	dir = [(1, 0), (0, 1)]
	for y in range(n):
		for x in range(m):
			if (y + x) % 2 == 0:
				mf.add_edge(start, m * y + x, 1)
			else:
				mf.add_edge(m * y + x, end, 1)
			if grid[y][x] == '.':
				for (dy, dx) in dir:
					ny = y + dy
					nx = x + dx
					if ny < n and nx < m and (grid[ny][nx] == '.'):
						(f, t) = (y * m + x, ny * m + nx)
						if (y + x) % 2:
							(f, t) = (t, f)
						mf.add_edge(f, t, 1)
	ans = mf.flow(start, end)
	for y in range(n):
		for x in range(m):
			for e in mf.g[y * m + x]:
				(to, rev, cap) = (e.to, e.rev, e.cap)
				(ny, nx) = divmod(to, m)
				if (y + x) % 2 == 0 and cap == 0 and (to != start) and (to != end) and (y * m + x != start) and (y * m + x != end):
					if y + 1 == ny:
						grid[y][x] = 'v'
						grid[ny][nx] = '^'
					elif y == ny + 1:
						grid[y][x] = '^'
						grid[ny][nx] = 'v'
					elif x + 1 == nx:
						grid[y][x] = '>'
						grid[ny][nx] = '<'
					elif x == nx + 1:
						grid[y][x] = '<'
						grid[ny][nx] = '>'
	print(ans)
	print(*[''.join(ret) for ret in grid], sep='\n')

def Main_E():
	(n, k) = read_ints()
	a = [read_int_list() for _ in range(n)]
	mcf = mcf_graph(n * 2 + 2)
	s = n * 2
	t = n * 2 + 1
	for i in range(n):
		mcf.add_edge(s, i, k, 0)
		mcf.add_edge(i + n, t, k, 0)
	mcf.add_edge(s, t, n * k, INF)
	for i in range(n):
		for j in range(n):
			mcf.add_edge(i, n + j, 1, INF - a[i][j])
	result = mcf.flow_(s, t, n * k)
	print(n * k * INF - result[1])
	grid = [['.'] * n for _ in range(n)]
	edges = mcf.edges()
	for e in edges:
		if e._from == s or e._to == t or e.flow == 0:
			continue
		grid[e._from][e._to - n] = 'X'
	print(*[''.join(g) for g in grid], sep='\n')

def Main_F():
	MOD = 998244353
	(n, m) = read_ints()
	a = read_int_list()
	b = read_int_list()
	a = [x % MOD for x in a]
	b = [x % MOD for x in b]
	cnv = convolution(a, b, MOD)
	ans = cnv.convolution()
	print(*ans)

def Main_G():
	sys.setrecursionlimit(10 ** 6)
	(n, m) = read_ints()
	scc = scc_graph(n)
	for _ in range(m):
		(a, b) = read_ints()
		scc.add_edge(a, b)
	ans = scc.scc()
	print(len(ans))
	for v in ans:
		print(len(v), ' '.join(map(str, v[::-1])))

def Main_H():
	(n, d) = read_ints()
	xy = [read_int_list() for _ in range(n)]
	tw = two_sat(n)
	for i in range(n):
		for j in range(i + 1, n):
			for x in range(2):
				if abs(xy[i][0] - xy[j][0]) < d:
					tw.add_clause(i, False, j, False)
				if abs(xy[i][0] - xy[j][1]) < d:
					tw.add_clause(i, False, j, True)
				if abs(xy[i][1] - xy[j][0]) < d:
					tw.add_clause(i, True, j, False)
				if abs(xy[i][1] - xy[j][1]) < d:
					tw.add_clause(i, True, j, True)
	if not tw.satisfiable():
		print('No')
		exit()
	print('Yes')
	ans = tw.answer()
	for (i, flag) in enumerate(ans):
		print(xy[i][0] if flag else xy[i][1])

def Main_I():
	s = read_str()
	sa = suffix_array3(s)
	ans = len(s) * (len(s) + 1) // 2
	for x in lcp_array2(s, sa):
		ans -= x
	print(ans)

def Main_J():

	def op(l, r):
		return max(l, r)

	def e():
		return -1

	def f(n):
		return n < r
	(n, q) = read_ints()
	a = read_int_list()
	seg = segtree(op, e, a)
	query = [read_ints() for _ in range(q)]
	for i in range(q):
		(t, l, r) = query[i]
		if t == 1:
			seg.set_(~-l, r)
		elif t == 2:
			print(seg.prod(~-l, r))
		else:
			print(seg.max_right(~-l, f) + 1)

def Main_K():
	p = 998244353

	def op(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return ((l1 + r1) % p << 32) + l2 + r2

	def e():
		return 0

	def mapping(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return ((l1 * r1 + l2 * r2) % p << 32) + r2

	def composition(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return (l1 * r1 % p << 32) + (l1 * r2 + l2) % p

	def id():
		return 1 << 32
	(n, q) = read_ints()
	A = read_int_list()
	A = [(x << 32) + 1 for x in A]
	seg = lazy_segtree(op, e, mapping, composition, id, A)
	ans = []
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			(l, r, b, c) = query[1:]
			seg.apply(l, r, (b << 32) + c)
		else:
			(l, r) = query[1:]
			print(seg.prod(l, r) >> 32)

def Main_L():

	def op(l: tuple, r: tuple):
		return (l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0])

	def e():
		return (0, 0, 0)

	def mapping(l: bool, r: tuple):
		if not l:
			return r
		return (r[1], r[0], r[1] * r[0] - r[2])

	def composition(l: bool, r: bool):
		return l ^ r

	def id():
		return False
	(n, q) = read_ints()
	A = read_int_list()
	query = [read_ints() for _ in range(q)]
	a = [(1, 0, 0) if i == 0 else (0, 1, 0) for i in A]
	seg = lazy_segtree(op, e, mapping, composition, id, a)
	for (t, l, r) in query:
		if t == 1:
			seg.apply(~-l, r, True)
		else:
			print(seg.prod(~-l, r)[2])
Main_G()


import sys
sys.setrecursionlimit(10 ** 9)

def SCC(G):
	D = []
	C = [len(G) - 1]
	U = [1] * len(G)

	def DFS(x):
		if U[x]:
			U[x] = 0
			for i in range(len(G[x])):
				DFS(G[x][i])
			D.append(x)
	for i in range(len(G)):
		if U[i]:
			DFS(i)
	GR = [[] for i in range(len(G))]
	for i in range(N):
		for j in range(len(G[i])):
			GR[G[i][j]].append(i)
	R = []
	U = [1] * len(G)

	def DFSR(x):
		if U[x]:
			R[-1].append(x)
			U[x] = 0
			for i in range(len(GR[x])):
				DFSR(GR[x][i])
	for i in range(len(G) - 1, -1, -1):
		if U[D[i]]:
			R.append([])
			DFSR(D[i])
	return R
S = sys.stdin.readlines()
(N, M) = map(int, S[0].split())
G = [[] for i in range(N)]
(a, b) = (0, 0)
for i in range(M):
	(a, b) = map(int, S[i + 1].split())
	G[a].append(b)
P = SCC(G)
print(len(P))
for i in range(len(P)):
	print(*[len(P[i])] + P[i])


import sys
input = sys.stdin.readline

def I():
	return int(input())

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

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

def main():

	def scc(Edge):
		N = len(Edge)
		Edgeinv = [[] for _ in range(N)]
		for vn in range(N):
			for vf in Edge[vn]:
				Edgeinv[vf].append(vn)
		used = [False] * N
		dim = [len(Edge[i]) for i in range(N)]
		order = []
		for st in range(N):
			if not used[st]:
				stack = [st, 0]
				while stack:
					(vn, i) = (stack[-2], stack[-1])
					if not i and used[vn]:
						stack.pop()
						stack.pop()
					else:
						used[vn] = True
						if i < dim[vn]:
							stack[-1] += 1
							stack.append(Edge[vn][i])
							stack.append(0)
						else:
							stack.pop()
							order.append(stack.pop())
		res = [None] * N
		used = [False] * N
		cnt = -1
		for st in order[::-1]:
			if not used[st]:
				cnt += 1
				stack = [st]
				res[st] = cnt
				used[st] = True
				while stack:
					vn = stack.pop()
					for vf in Edgeinv[vn]:
						if not used[vf]:
							used[vf] = True
							res[vf] = cnt
							stack.append(vf)
		M = cnt + 1
		components = [[] for _ in range(M)]
		for i in range(N):
			components[res[i]].append(i)
		return (res, components)
	(N, M) = MI()
	adj = [[] for _ in range(N)]
	for i in range(M):
		(a, b) = MI()
		adj[a].append(b)
	(res, compo) = scc(adj)
	M = max(res) + 1
	print(M)
	for i in range(M):
		length = len(compo[i])
		print(' '.join(map(str, [length] + compo[i])))
main()


import types
_atcoder_code = "\n# Python port of AtCoder Library.\n\n__version__ = '0.0.1'\n"
atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)
_atcoder__scc_code = "\nimport copy\nimport sys\nimport typing\n\n\nclass CSR:\n    def __init__(\n            self, n: int, edges: typing.List[typing.Tuple[int, int]]) -> None:\n        self.start = [0] * (n + 1)\n        self.elist = [0] * len(edges)\n\n        for e in edges:\n            self.start[e[0] + 1] += 1\n\n        for i in range(1, n + 1):\n            self.start[i] += self.start[i - 1]\n\n        counter = copy.deepcopy(self.start)\n        for e in edges:\n            self.elist[counter[e[0]]] = e[1]\n            counter[e[0]] += 1\n\n\nclass SCCGraph:\n    '''\n    Reference:\n    R. Tarjan,\n    Depth-First Search and Linear Graph Algorithms\n    '''\n\n    def __init__(self, n: int) -> None:\n        self._n = n\n        self._edges = []\n\n    def num_vertices(self) -> int:\n        return self._n\n\n    def add_edge(self, from_vertex: int, to_vertex: int) -> None:\n        self._edges.append((from_vertex, to_vertex))\n\n    def scc_ids(self) -> typing.Tuple[int, typing.List[int]]:\n        g = CSR(self._n, self._edges)\n        now_ord = 0\n        group_num = 0\n        visited = []\n        low = [0] * self._n\n        order = [-1] * self._n\n        ids = [0] * self._n\n\n        sys.setrecursionlimit(max(self._n + 1000, sys.getrecursionlimit()))\n\n        def dfs(v: int) -> None:\n            nonlocal now_ord\n            nonlocal group_num\n            nonlocal visited\n            nonlocal low\n            nonlocal order\n            nonlocal ids\n\n            low[v] = now_ord\n            order[v] = now_ord\n            now_ord += 1\n            visited.append(v)\n            for i in range(g.start[v], g.start[v + 1]):\n                to = g.elist[i]\n                if order[to] == -1:\n                    dfs(to)\n                    low[v] = min(low[v], low[to])\n                else:\n                    low[v] = min(low[v], order[to])\n\n            if low[v] == order[v]:\n                while True:\n                    u = visited[-1]\n                    visited.pop()\n                    order[u] = self._n\n                    ids[u] = group_num\n                    if u == v:\n                        break\n                group_num += 1\n\n        for i in range(self._n):\n            if order[i] == -1:\n                dfs(i)\n\n        for i in range(self._n):\n            ids[i] = group_num - 1 - ids[i]\n\n        return group_num, ids\n\n    def scc(self) -> typing.List[typing.List[int]]:\n        ids = self.scc_ids()\n        group_num = ids[0]\n        counts = [0] * group_num\n        for x in ids[1]:\n            counts[x] += 1\n        groups = [[] for _ in range(group_num)]\n        for i in range(self._n):\n            groups[ids[1][i]].append(i)\n\n        return groups\n"
atcoder._scc = types.ModuleType('atcoder._scc')
exec(_atcoder__scc_code, atcoder._scc.__dict__)
_atcoder_scc_code = '\nimport typing\n\n# import atcoder._scc\n\n\nclass SCCGraph:\n    def __init__(self, n: int = 0) -> None:\n        self._internal = atcoder._scc.SCCGraph(n)\n\n    def add_edge(self, from_vertex: int, to_vertex: int) -> None:\n        n = self._internal.num_vertices()\n        assert 0 <= from_vertex < n\n        assert 0 <= to_vertex < n\n        self._internal.add_edge(from_vertex, to_vertex)\n\n    def scc(self) -> typing.List[typing.List[int]]:\n        return self._internal.scc()\n'
atcoder.scc = types.ModuleType('atcoder.scc')
exec(_atcoder_scc_code, atcoder.scc.__dict__)
atcoder.scc.__dict__['atcoder'] = atcoder
atcoder.scc.__dict__['atcoder._scc'] = atcoder._scc
SCCGraph = atcoder.scc.SCCGraph
import sys

def main() -> None:
	(n, m) = map(int, sys.stdin.readline().split())
	g = SCCGraph(n)
	for i in range(m):
		(u, v) = map(int, sys.stdin.readline().split())
		g.add_edge(u, v)
	scc = g.scc()
	print(len(scc))
	for v in scc:
		print(len(v), end='')
		for x in v:
			print(f' {x}', end='')
		print('')
main()


class scc_graph:

	def __init__(s, n):
		s._n = n
		s.edge = [s.component() for i in range(n)]

	def num_vertices(s):
		return s._n

	def add_edge(s, frm, to):
		s.edge[frm].add_go(to)
		s.edge[to].add_rgo(frm)

	def scc_ids(s):

		def dfs(v):
			stack = [v]
			while stack:
				t = stack.pop()
				vis[t] = True
				for i in s.edge[t].go:
					if not vis[i]:
						stack.append(t)
						stack.append(i)
						break
				else:
					vs.append(t)

		def rdfs(v, n):
			stack = [v]
			vis[v] = True
			ids[v] = n
			while stack:
				t = stack.pop()
				vis[t] = True
				for i in s.edge[t].rgo:
					if not vis[i]:
						ids[i] = n
						stack.append(i)
		vis = [False] * s._n
		vs = []
		ids = [-1] * s._n
		for i in range(s._n):
			if not vis[i]:
				dfs(i)
		group_num = 0
		vis = [False] * s._n
		for i in vs[::-1]:
			if not vis[i]:
				rdfs(i, group_num)
				group_num += 1
		return (group_num, ids)

	def scc(s):
		ids = s.scc_ids()
		group_num = ids[0]
		counts = [0] * group_num
		for x in ids[1]:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for i in range(s._n):
			groups[ids[1][i]].append(i)
		return groups

	class component:

		def __init__(s):
			s.go = []
			s.rgo = []

		def add_go(s, to):
			s.go.append(to)

		def add_rgo(s, frm):
			s.rgo.append(frm)
import sys

def main():
	input = sys.stdin.readline
	(n, m) = list(map(int, input().split()))
	ab = [list(map(int, input().split())) for _ in range(m)]
	g = scc_graph(n)
	for i in range(m):
		(u, v) = ab[i]
		g.add_edge(u, v)
	scc = g.scc()
	print(len(scc))
	for v in scc:
		print(len(v), end=' ')
		for x in v:
			print(x, end=' ')
		print('')
main()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
E = [[] for i in range(N)]
E_INV = [[] for i in range(N)]
for i in range(M):
	(x, y) = map(int, input().split())
	E[x].append(y)
	E_INV[y].append(x)
QUE = list(range(N))
check = [0] * N
TOP_SORT = []

def dfs(x):
	if check[x] == 1:
		return
	check[x] = 1
	for to in E[x]:
		if check[to] == 0:
			dfs(to)
	TOP_SORT.append(x)
	check[x] = 1
while QUE:
	x = QUE.pop()
	dfs(x)
USE = [0] * N
SCC = []

def dfs2(x):
	Q = [x]
	USE[x] = 1
	ANS = []
	while Q:
		x = Q.pop()
		ANS.append(x)
		for to in E_INV[x]:
			if USE[to] == 0:
				USE[to] = 1
				Q.append(to)
	return ANS
for x in TOP_SORT[::-1]:
	if USE[x] == 0:
		SCC.append(dfs2(x))
print(len(SCC))
for x in SCC:
	print(len(x), *x)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(5 * 10 ** 5)
(N, M) = map(int, input().split())
edge = [[] for i in range(N)]
rev_edge = [[] for i in range(N)]
for _ in range(M):
	(a, b) = map(int, input().split())
	edge[a].append(b)
	rev_edge[b].append(a)
seen = [False] * N
stop = []

def dfs(v):
	for nv in edge[v]:
		if not seen[nv]:
			seen[nv] = True
			dfs(nv)
	stop.append(v)
for i in range(N):
	if not seen[i]:
		seen[i] = True
		dfs(i)
seen = [False] * N

def scc():
	res = []
	connect = []

	def rev_dfs(v):
		for nv in rev_edge[v]:
			if not seen[nv]:
				connect.append(nv)
				seen[nv] = True
				rev_dfs(nv)
	while stop:
		while stop and seen[stop[-1]]:
			stop.pop()
		if not stop:
			break
		connect = [stop[-1]]
		seen[stop[-1]] = True
		rev_dfs(stop[-1])
		res.append(connect)
	return res
res = scc()
print(len(res))
for L in res:
	print(len(L), *L)


from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 9)
input = stdin.buffer.readline
(n, m) = map(int, input().split())
edges = [[] for _ in range(n)]
reversed_edges = [[] for _ in range(n)]
for _ in range(m):
	(i, j) = map(int, input().split())
	edges[i].append(j)
	reversed_edges[j].append(i)

def scc(n, edges, reversed_edges):
	order = []
	seen = [True] * n

	def dfs(node):
		seen[node] = False
		for i in edges[node]:
			if seen[i]:
				dfs(i)
		order.append(node)
	for i in range(n):
		if seen[i]:
			dfs(i)
	groups = []
	seen = [True] * n
	for start in reversed(order):
		if seen[start]:
			seen[start] = False
			todo = [start]
			group = [start]
			while len(todo) > 0:
				node = todo.pop(-1)
				for j in reversed_edges[node]:
					if seen[j]:
						seen[j] = False
						todo.append(j)
						group.append(j)
			group.reverse()
			groups.append(group)
	return groups
groups = scc(n, edges, reversed_edges)
print(len(groups))
for group in groups:
	print(len(group), ' '.join(map(str, group)))


class SCC:

	def __init__(self, N):
		self.N = N
		self.G1 = [[] for _ in range(N)]
		self.G2 = [[] for _ in range(N)]

	def add_edge(self, a, b):
		self.G1[a].append(b)
		self.G2[b].append(a)

	def scc(self):
		self.seen = [0] * self.N
		self.postorder = [-1] * self.N
		self.order = 0
		for i in range(self.N):
			if self.seen[i]:
				continue
			self._dfs(i)
		self.seen = [0] * self.N
		scclist = []
		for i in self._argsort(self.postorder, reverse=True):
			if self.seen[i]:
				continue
			cc = self._dfs2(i)
			scclist.append(cc)
		return scclist

	def _argsort(self, arr, reverse=False):
		shift = self.N.bit_length() + 2
		tmp = sorted([arr[i] << shift | i for i in range(len(arr))], reverse=reverse)
		mask = (1 << shift) - 1
		return [tmp[i] & mask for i in range(len(arr))]

	def _dfs(self, v0):
		todo = [~v0, v0]
		while todo:
			v = todo.pop()
			if v >= 0:
				self.seen[v] = 1
				for next_v in self.G1[v]:
					if self.seen[next_v]:
						continue
					todo.append(~next_v)
					todo.append(next_v)
			elif self.postorder[~v] == -1:
				self.postorder[~v] = self.order
				self.order += 1
		return

	def _dfs2(self, v):
		todo = [v]
		self.seen[v] = 1
		cc = [v]
		while todo:
			v = todo.pop()
			for next_v in self.G2[v]:
				if self.seen[next_v]:
					continue
				self.seen[next_v] = 1
				todo.append(next_v)
				cc.append(next_v)
		return cc

def main():
	(N, M) = map(int, input().split())
	scc = SCC(N)
	for i in range(M):
		(a, b) = map(int, input().split())
		scc.add_edge(a, b)
	scclist = scc.scc()
	print(len(scclist))
	for cc in scclist:
		print(len(cc), *cc)
main()


import sys
input = sys.stdin.buffer.readline

class StronglyConnectedComponents:

	def __init__(self, graph):
		self.n = len(graph)
		self.graph = graph
		self.out_degree = [len(self.graph[i]) for i in range(self.n)]
		self.label = 0
		self.group = [-1] * self.n
		self.rev_graph = [[] for i in range(self.n)]
		for a in range(self.n):
			for b in self.graph[a]:
				self.rev_graph[b].append(a)
		self.post_order = []
		self.used = [False] * self.n
		for v in range(self.n):
			if not self.used[v]:
				self._dfs(v)
		for v in reversed(self.post_order):
			if self.group[v] == -1:
				self._rev_dfs(v, self.label)
				self.label += 1

	def _dfs(self, v):
		st = [v, 0]
		while st:
			(v, ind) = (st[-2], st[-1])
			if not ind and self.used[v]:
				st.pop()
				st.pop()
			else:
				self.used[v] = True
				if ind < self.out_degree[v]:
					st[-1] += 1
					st.append(self.graph[v][ind])
					st.append(0)
				else:
					st.pop()
					self.post_order.append(st.pop())

	def _rev_dfs(self, v, label):
		st = [v]
		self.group[v] = label
		while st:
			v = st.pop()
			for nxt_v in self.rev_graph[v]:
				if self.group[nxt_v] >= 0:
					continue
				st.append(nxt_v)
				self.group[nxt_v] = label

	def construct(self):
		self.red_graph = [set() for i in range(self.label)]
		self.red_comps = [[] for i in range(self.label)]
		for v in range(self.n):
			lb = self.group[v]
			for nxt_v in self.graph[v]:
				nxt_lb = self.group[nxt_v]
				if lb == nxt_lb:
					continue
				self.red_graph[lb].add(nxt_lb)
			self.red_comps[lb].append(v)
		return (self.red_graph, self.red_comps)

	def tp_sort(self):
		red_n = len(self.red_graph)
		indegree = [0] * red_n
		for v in range(red_n):
			for nxt_v in self.red_graph[v]:
				indegree[nxt_v] += 1
		tp_order = [i for i in range(red_n) if indegree[i] == 0]
		st = tp_order[:]
		while st:
			v = st.pop()
			for nxt_v in self.red_graph[v]:
				indegree[nxt_v] -= 1
				if indegree[nxt_v] == 0:
					st.append(nxt_v)
					tp_order.append(nxt_v)
		return tp_order
(n, m) = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for (u, v) in edges:
	graph[u].append(v)
scc = StronglyConnectedComponents(graph)
(_, red_comps) = scc.construct()
tp = scc.tp_sort()
print(len(red_comps))
for v in tp:
	print(len(red_comps[v]), *red_comps[v])


def SCC_Tarjan(g):
	n = len(g)
	order = [-1] * n
	low = [0] * n
	ord_now = 0
	parent = [-1] * n
	gp = [0] * n
	gp_num = 0
	S = []
	q = []
	for i in range(n):
		if order[i] == -1:
			q.append(i)
			while q:
				v = q.pop()
				if v >= 0:
					if order[v] != -1:
						continue
					order[v] = low[v] = ord_now
					ord_now += 1
					S.append(v)
					q.append(~v)
					for c in g[v]:
						if order[c] == -1:
							q.append(c)
							parent[c] = v
						else:
							low[v] = min(low[v], order[c])
				else:
					v = ~v
					if parent[v] != -1:
						low[parent[v]] = min(low[parent[v]], low[v])
					if low[v] == order[v]:
						while True:
							w = S.pop()
							order[w] = n
							gp[w] = gp_num
							if w == v:
								break
						gp_num += 1
	scc = [[] for _ in range(gp_num)]
	for i in range(n):
		gp[i] = gp_num - gp[i] - 1
		scc[gp[i]].append(i)
	return scc
import sys
readline = sys.stdin.readline
read = sys.stdin.read
(n, m) = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, readline().split())
	g[a].append(b)
scc = SCC_Tarjan(g)
print(len(scc))
for lst in scc:
	print(*[len(lst)] + lst)


(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]
import sys
sys.setrecursionlimit(10 ** 8)

class Scc:

	def __init__(self, n):
		self.n = n
		self.edges = []

	def add_edge(self, fr, to):
		assert 0 <= fr < self.n
		assert 0 <= to < self.n
		self.edges.append((fr, to))

	def scc(self):
		csr_start = [0] * (self.n + 1)
		csr_elist = [0] * len(self.edges)
		for (fr, to) in self.edges:
			csr_start[fr + 1] += 1
		for i in range(1, self.n + 1):
			csr_start[i] += csr_start[i - 1]
		counter = csr_start[:]
		for (fr, to) in self.edges:
			csr_elist[counter[fr]] = to
			counter[fr] += 1
		self.now_ord = self.group_num = 0
		self.visited = []
		self.low = [0] * self.n
		self.ord = [-1] * self.n
		self.ids = [0] * self.n

		def _dfs(v):
			self.low[v] = self.ord[v] = self.now_ord
			self.now_ord += 1
			self.visited.append(v)
			for i in range(csr_start[v], csr_start[v + 1]):
				to = csr_elist[i]
				if self.ord[to] == -1:
					_dfs(to)
					self.low[v] = min(self.low[v], self.low[to])
				else:
					self.low[v] = min(self.low[v], self.ord[to])
			if self.low[v] == self.ord[v]:
				while 1:
					u = self.visited.pop()
					self.ord[u] = self.n
					self.ids[u] = self.group_num
					if u == v:
						break
				self.group_num += 1
		for i in range(self.n):
			if self.ord[i] == -1:
				_dfs(i)
		for i in range(self.n):
			self.ids[i] = self.group_num - 1 - self.ids[i]
		groups = [[] for _ in range(self.group_num)]
		for i in range(self.n):
			groups[self.ids[i]].append(i)
		return groups
scc = Scc(N)
for (a, b) in AB:
	scc.add_edge(a, b)
ans = scc.scc()
print(len(ans))
for row in ans:
	print(*[len(row)] + row)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

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

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

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

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def scc(n, e, re):
	v = [None] * n
	t = []

	def dfs(i):
		v[i] = 0
		for b in e[i]:
			if v[b] is None:
				dfs(b)
		t.append(i)
	for i in range(n):
		if v[i] is None:
			dfs(i)
	r = [None] * n

	def dfs2(i, p):
		r[i] = p
		for b in re[i]:
			if r[b] is None:
				dfs2(b, p)
	for c in t[::-1]:
		if r[c] is None:
			dfs2(c, c)
	return r

def main():
	(n, m) = LI()
	ab = [LI() for _ in range(m)]
	e = collections.defaultdict(set)
	re = collections.defaultdict(set)
	for (a, b) in ab:
		e[a].add(b)
		re[b].add(a)
	sc = scc(n, e, re)
	d = {}
	ci = collections.defaultdict(list)
	for (i, c) in enumerate(sc):
		ci[c].append(i)
		d[i] = c
	cs = list(ci.keys())
	se = collections.defaultdict(set)
	sre = collections.defaultdict(set)
	for (a, b) in ab:
		if d[a] == d[b]:
			continue
		se[d[a]].add(d[b])
		sre[d[b]].add(d[a])
	rr = []
	q = []
	for c in cs:
		if len(sre[c]) == 0:
			q.append(c)
	qi = 0
	while qi < len(q):
		c = q[qi]
		qi += 1
		rr.append(JA([len(ci[c])] + ci[c], ' '))
		for nc in se[c]:
			sre[nc].remove(c)
			if len(sre[nc]) == 0:
				q.append(nc)
	return JA([len(rr)] + rr, '\n')
print(main())


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

def scc(N, g, rg):
	V = list(range(N))

	def dfs(u, done, o):
		done.add(u)
		for v in g[u]:
			if v in done:
				continue
			done.add(v)
			dfs(v, done, o)
		o.append(u)

	def dfs_rev(u, done, c):
		done.add(u)
		c.append(u)
		for v in rg[u]:
			if v in done:
				continue
			dfs_rev(v, done, c)
	done = set()
	o = []
	for v in V:
		if v in done:
			continue
		dfs(v, done, o)
	done = set()
	ans = []
	while o:
		u = o.pop()
		if u in done:
			continue
		vv = []
		dfs_rev(u, done, vv)
		ans.append(vv)
	return ans

def atcoder_practice2_g():
	(N, M) = map(int, input().split())
	g = defaultdict(list)
	rg = defaultdict(list)
	for _ in range(M):
		(a, b) = map(int, input().split())
		g[a].append(b)
		rg[b].append(a)
	vv = scc(N, g, rg)
	print(len(vv))
	for r in vv:
		print(len(r), *r)

def test():
	g = {1: [2], 5: [2], 2: [4, 3], 3: [4, 7, 6], 4: [5, 8], 6: [9], 7: [8], 8: [9], 9: [7, 10], 10: []}
	vv = scc(g)
	for r in vv:
		print(r)
atcoder_practice2_g()


(N, M) = map(int, input().split())
G1 = [[] for _ in range(N)]
G2 = [[] for _ in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	if a == b:
		continue
	G1[a].append(b)
	G2[b].append(a)

def dfs(a0):
	global order
	todo = [~a0, a0]
	while todo:
		a = todo.pop()
		if a >= 0:
			seen[a] = 1
			for b in G1[a]:
				if seen[b]:
					continue
				todo.append(~b)
				todo.append(b)
		elif postorder[~a] == -1:
			postorder[~a] = order
			order += 1
	return

def dfs2(v):
	todo = [v]
	seen[v] = 1
	cc = [v]
	while todo:
		v = todo.pop()
		for next_v in G2[v]:
			if seen[next_v]:
				continue
			seen[next_v] = 1
			todo.append(next_v)
			cc.append(next_v)
	return cc
seen = [0] * N
postorder = [-1] * N
order = 0
for i in range(N):
	if seen[i]:
		continue
	dfs(i)
seen = [0] * N
scc = []
for (i, _) in sorted(enumerate(postorder), key=lambda x: x[1], reverse=True):
	if seen[i]:
		continue
	cc = dfs2(i)
	scc.append(cc)
print(len(scc))
for cc in scc:
	print(len(cc), *cc)


from collections import defaultdict

def scc(V, E):
	g = defaultdict(list)
	rg = defaultdict(list)
	for (u, v) in E:
		g[u].append(v)
		rg[v].append(u)
	o = []
	done = set()
	for u in V:
		if u in done:
			continue
		s = [(u, True)]
		while s:
			(u, f) = s.pop()
			if f:
				if u in done:
					continue
				done.add(u)
				s.append((u, False))
				for v in g[u]:
					if v in done:
						continue
					s.append((v, True))
			else:
				o.append(u)
	done = set()
	ans = []
	while o:
		u = o.pop()
		if u in done:
			continue
		s = [u]
		vv = [u]
		done.add(u)
		while s:
			u = s.pop()
			for v in rg[u]:
				if v in done:
					continue
				vv.append(v)
				s.append(v)
				done.add(v)
		ans.append(vv)
	return ans

def atcoder_practice2_g():
	import sys
	input = sys.stdin.buffer.readline
	(N, M) = map(int, input().split())
	E = []
	for _ in range(M):
		(a, b) = map(int, input().split())
		E.append((a, b))
	V = list(range(N))
	vv = scc(V, E)
	print(len(vv))
	for r in vv:
		print(len(r), *r)
atcoder_practice2_g()


import sys
readline = sys.stdin.readline
import sys

def scc(Edge):
	N = len(Edge)
	Edgeinv = [[] for _ in range(N)]
	for vn in range(N):
		for vf in Edge[vn]:
			Edgeinv[vf].append(vn)
	used = [0] * N
	order = []
	for st in range(N):
		if used[st]:
			continue
		stack = [~st, st]
		while stack:
			vn = stack.pop()
			if vn >= 0:
				if used[vn]:
					continue
				used[vn] = 1
				for vf in Edge[vn]:
					if used[vf]:
						continue
					stack.append(~vf)
					stack.append(vf)
			elif used[~vn] != 2:
				used[~vn] = 2
				order.append(~vn)
	res = [None] * N
	used = [False] * N
	cnt = -1
	for st in order[::-1]:
		if not used[st]:
			cnt += 1
			stack = [st]
			res[st] = cnt
			used[st] = True
			while stack:
				vn = stack.pop()
				for vf in Edgeinv[vn]:
					if not used[vf]:
						used[vf] = True
						res[vf] = cnt
						stack.append(vf)
	M = cnt + 1
	components = [[] for _ in range(M)]
	for i in range(N):
		components[res[i]].append(i)
	return (res, components)
(N, M) = map(int, readline().split())
Edge = [[] for _ in range(N)]
for _ in range(M):
	(a, b) = map(int, readline().split())
	Edge[a].append(b)
(R, comp) = scc(Edge)
Ans = [str(len(comp))]
for c in comp:
	Ans.append(f'{len(c)} ' + ' '.join(map(str, c)))
print('\n'.join(Ans))


class csr:

	def __init__(self, n, edges):
		from copy import deepcopy
		self.start = [0] * (n + 1)
		self.elist = [[] for _ in range(len(edges))]
		for e in edges:
			self.start[e[0] + 1] += 1
		for i in range(1, n + 1):
			self.start[i] += self.start[i - 1]
		counter = deepcopy(self.start)
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class scc_graph:
	edges = []

	def __init__(self, n: int):
		self._n = n

	def num_vertices(self):
		return self._n

	def add_edge(self, _from: int, _to: int):
		self.edges.append((_from, [_to]))

	def scc_ids(self):
		g = csr(self._n, self.edges)
		self.now_ord = 0
		self.group_num = 0
		visited = []
		low = [0] * self._n
		ord = [-1] * self._n
		ids = [0] * self._n

		def dfs(s, v):
			low[v] = ord[v] = self.now_ord
			self.now_ord += 1
			visited.append(v)
			for i in range(g.start[v], g.start[v + 1]):
				to = g.elist[i][0]
				if ord[to] == -1:
					s(s, to)
					low[v] = min(low[v], low[to])
				else:
					low[v] = min(low[v], ord[to])
			if low[v] == ord[v]:
				while True:
					u = visited.pop()
					ord[u] = self._n
					ids[u] = self.group_num
					if u == v:
						break
				self.group_num += 1
		for i in range(self._n):
			if ord[i] == -1:
				dfs(dfs, i)
		for i in range(self._n):
			ids[i] = self.group_num - 1 - ids[i]
		return (self.group_num, ids)

	def scc(self):
		ids = self.scc_ids()
		group_num = ids[0]
		counts = [0] * group_num
		for x in ids[1]:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for i in range(self._n):
			groups[ids[1][i]].append(i)
		return groups
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

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

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

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

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

def Main():
	(n, m) = read_ints()
	scc = scc_graph(n)
	for _ in range(m):
		(a, b) = read_ints()
		scc.add_edge(a, b)
	ans = scc.scc()
	print(len(ans))
	for v in ans:
		print(len(v), ' '.join(map(str, v[::-1])))
Main()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, m) = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = map(int, input().split())
	ns[u].append(v)

def scc():
	preorder = {}
	lowlink = {}
	seen = [False] * n
	scc_queue = []
	i = 0
	ans = []
	for source in range(n):
		if seen[source]:
			continue
		queue = [source]
		while queue:
			v = queue[-1]
			if v not in preorder:
				i = i + 1
				preorder[v] = i
			done = True
			for w in ns[v]:
				if w not in preorder:
					queue.append(w)
					done = False
					break
			if done:
				lowlink[v] = preorder[v]
				for w in ns[v]:
					if seen[w]:
						continue
					if preorder[w] > preorder[v]:
						lowlink[v] = min([lowlink[v], lowlink[w]])
					else:
						lowlink[v] = min([lowlink[v], preorder[w]])
				queue.pop()
				if lowlink[v] == preorder[v]:
					scc = {v}
					seen[v] = True
					while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
						k = scc_queue.pop()
						scc.add(k)
						seen[k] = True
					ans.append(scc)
				else:
					scc_queue.append(v)
	return ans
comp = scc()
print(len(comp))
for item in reversed(comp):
	print(len(item), ' '.join(map(str, item)))


from collections import deque

class Graph:

	def __init__(self, n, edge):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.rev = [[] for _ in range(n)]
		self.deg = [0 for _ in range(n)]
		for e in edge:
			self.graph[e[0]].append(e[1])
			self.rev[e[1]].append(e[0])
			self.deg[e[1]] += 1

	def strongry_connected(self):
		group = [None for _ in range(self.n)]
		used = [0 for _ in range(self.n)]
		order = []
		for s in range(self.n):
			if not used[s]:
				stack = [s]
				used[s] = 1
				while stack:
					node = stack.pop()
					movable = False
					for adj in self.graph[node]:
						if not used[adj]:
							movable = True
							used[adj] = 1
							stack.append(node)
							stack.append(adj)
							break
					if not movable:
						order.append(node)
		used = [0 for _ in range(self.n)]
		count = 0
		for s in order[::-1]:
			if not used[s]:
				stack = [s]
				group[s] = count
				while stack:
					node = stack.pop()
					used[node] = 1
					for adj in self.rev[node]:
						if not used[adj]:
							group[adj] = count
							stack.append(adj)
				count += 1
		return (group, count)

	def topological_sort(self):
		res = [i for i in range(self.n) if self.deg[i] == 0]
		queue = deque(res)
		while queue:
			node = queue.popleft()
			for adj in self.graph[node]:
				self.deg[adj] -= 1
				if self.deg[adj] == 0:
					queue.append(adj)
					res.append(adj)
		return res

def simplify(edge):
	res = []
	for e in edge:
		if e[0] == e[1]:
			continue
		res.append(e)
	return tuple(set(res))
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]
edge = simplify(edge)
g = Graph(N, edge)
(group, count) = g.strongry_connected()
group_to_node = [[] for _ in range(count)]
for i in range(N):
	group_to_node[group[i]].append(i)
new_edge = []
for (a, b) in edge:
	new_edge.append((group[a], group[b]))
new_edge = simplify(new_edge)
new_g = Graph(count, new_edge)
ts = new_g.topological_sort()
res = [[] for _ in range(count)]
for i in range(count):
	res[i].append(len(group_to_node[ts[i]]))
	res[i].extend(group_to_node[ts[i]])
print(count)
print('\n'.join(map(lambda x: ' '.join(map(str, x)), res)))


from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify
import itertools
import math, fractions
import sys, copy

def L():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline().rstrip())

def SL():
	return list(sys.stdin.readline().rstrip())

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI1():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def R(n):
	return [sys.stdin.readline().strip() for _ in range(n)]

def LR(n):
	return [L() for _ in range(n)]

def IR(n):
	return [I() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def LIR1(n):
	return [LI1() for _ in range(n)]

def SR(n):
	return [SL() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]

def perm(n, r):
	return math.factorial(n) // math.factorial(r)

def comb(n, r):
	return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

def make_list(n, *args, default=0):
	return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = 'abcdefghijklmnopqrstuvwxyz'
ALPHABETS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
MOD = 1000000007
INF = float('inf')
sys.setrecursionlimit(1000000)

class DAG:

	def __init__(self, n, AB):
		self.n = n
		self.G = [[] for _ in range(n)]
		self.revG = [[] for _ in range(n)]
		self.AB = AB
		for (a, b) in AB:
			self.G[a].append(b)
			self.revG[b].append(a)

	def scc(self):
		visited = [False] * self.n
		order = []
		for i in range(self.n):
			if visited[i]:
				continue
			q = deque([i])
			visited[i] = True
			while q:
				v = q[-1]
				for u in self.G[v]:
					if not visited[u]:
						q.append(u)
						visited[u] = True
						break
				else:
					q.pop()
					order.append(v)
		visited = [False] * self.n
		scc = []
		for i in order[::-1]:
			if visited[i]:
				continue
			tmp = [i]
			visited[i] = True
			q = deque([i])
			while q:
				v = q.pop()
				for u in self.revG[v]:
					if visited[u]:
						continue
					visited[u] = True
					tmp.append(u)
					q.append(u)
			scc.append(tmp)
		return scc

def main():
	(N, M) = LI()
	AB = LIR(M)
	g = DAG(N, AB)
	scc = g.scc()
	print(len(scc))
	for es in scc:
		print(len(es), *es)
main()


from operator import itemgetter
from itertools import *
from bisect import *
from collections import *
from heapq import *
import sys
sys.setrecursionlimit(10 ** 6)

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

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

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

def SI():
	return sys.stdin.readline()[:-1]

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI1():
	return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep='\n')
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def scc(to, ot):
	n = len(to)

	def dfs(u):
		for v in to[u]:
			if com[v]:
				continue
			com[v] = 1
			dfs(v)
		top.append(u)
	top = []
	com = [0] * n
	for u in range(n):
		if com[u]:
			continue
		com[u] = 1
		dfs(u)

	def rdfs(u, k):
		for v in ot[u]:
			if com[v] != -1:
				continue
			com[v] = k
			rdfs(v, k)
	com = [-1] * n
	k = 0
	for u in top[::-1]:
		if com[u] != -1:
			continue
		com[u] = k
		rdfs(u, k)
		k += 1
	return (k, com)
(n, m) = MI()
to = [[] for _ in range(n)]
ot = [[] for _ in range(n)]
for _ in range(m):
	(u, v) = MI()
	to[u].append(v)
	ot[v].append(u)
(k, com) = scc(to, ot)
group = [[] for _ in range(k)]
for (u, g) in enumerate(com):
	group[g].append(u)
print(k)
for uu in group:
	print(len(uu), end=' ')
	print(*uu)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
es = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	es[a].append(b)

def scc(n_node, es):
	esinv = [[] for _ in range(n_node)]
	for i in range(n_node):
		for e in es[i]:
			esinv[e].append(i)
	used = [False] * n_node
	dim = [len(es[i]) for i in range(n_node)]
	order = []
	for st in range(n_node):
		if not used[st]:
			stack = [(st, 0)]
			while stack:
				(now, i) = stack.pop()
				if not i and used[now]:
					continue
				else:
					used[now] = True
					if i < dim[now]:
						stack.append((now, i + 1))
						stack.append((es[now][i], 0))
					else:
						order.append(now)
	res = [-1] * n_node
	used = [False] * n_node
	cnt = -1
	for st in order[::-1]:
		if not used[st]:
			cnt += 1
			stack = [st]
			res[st] = cnt
			used[st] = True
			while stack:
				now = stack.pop()
				for e in esinv[now]:
					if not used[e]:
						used[e] = True
						res[e] = cnt
						stack.append(e)
	n_group = cnt + 1
	components = [[] for _ in range(n_group)]
	for i in range(n_node):
		components[res[i]].append(i)
	return components
comp = scc(n, es)
row = len(comp)
print(row)
for i in range(row):
	length = len(comp[i])
	print(length, *comp[i])


class Graph:

	def __init__(self, n, edge, indexed=1):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.rev = [[] for _ in range(n)]
		self.deg = [0 for _ in range(n)]
		for e in edge:
			self.graph[e[0] - indexed].append(e[1] - indexed)
			self.rev[e[1] - indexed].append(e[0] - indexed)
			self.deg[e[1] - indexed] += 1

	def strongry_connected(self):
		group = [None for _ in range(self.n)]
		used = [0 for _ in range(self.n)]
		order = []
		for s in range(self.n):
			if not used[s]:
				stack = [s]
				used[s] = 1
				while stack:
					node = stack.pop()
					movable = False
					for adj in self.graph[node]:
						if not used[adj]:
							movable = True
							used[adj] = 1
							stack.append(node)
							stack.append(adj)
							break
					if not movable:
						order.append(node)
		used = [0 for _ in range(self.n)]
		count = 0
		for s in order[::-1]:
			if not used[s]:
				stack = [s]
				group[s] = count
				while stack:
					node = stack.pop()
					used[node] = 1
					for adj in self.rev[node]:
						if not used[adj]:
							group[adj] = count
							stack.append(adj)
				count += 1
		return (group, count)
import sys
input = sys.stdin.buffer.readline
(N, M) = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(M)]
g = Graph(N, E, 0)
(group, count) = g.strongry_connected()
res = [[] for _ in range(count)]
for (i, k) in enumerate(group):
	res[k].append(i)
print(count)
for r in res:
	print(len(r), *r)


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
mod = 10 ** 9 + 7
INF = float('inf')

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

def inverse(N, mod):
	return pow(N, mod - 2, mod)

class Graph(object):

	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def scc(N, G, Grev):
	order = []
	visit = [0] * N
	group = [None] * N

	def dfs(node):
		visit[node] = 1
		for i in G.graph[node]:
			if not visit[i]:
				dfs(i)
		order.append(node)

	def dfs_rev(node, num):
		group[node] = num
		visit[node] = 1
		for i in Grev.graph[node]:
			if not visit[i]:
				dfs_rev(i, num)
	for i in range(N):
		if not visit[i]:
			dfs(i)
	visit = [0] * N
	num = 0
	for i in reversed(order):
		if not visit[i]:
			dfs_rev(i, num)
			num += 1
	return (num, group)

def construct(N, G, num, group):
	DAG = [[] for i in range(num)]
	for i in range(N):
		itr = group[i]
		DAG[itr].append(i)
	return DAG

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

def main():
	(N, M) = getlist()
	G = Graph()
	Grev = Graph()
	for i in range(M):
		(a, b) = getlist()
		G.add_edge(a, b)
		Grev.add_edge(b, a)
	(num, group) = scc(N, G, Grev)
	DAG = construct(N, G, num, group)
	x = len(DAG)
	print(x)
	for i in range(x):
		print(len(DAG[i]), *DAG[i])
main()


from collections import deque

class csr:

	def __init__(self, N, edges):
		self.start = [0] * (N + 1)
		self.elist = [0] * len(edges)
		for e in edges:
			self.start[e[0] + 1] += 1
		for i in range(1, N + 1):
			self.start[i] += self.start[i - 1]
		counter = self.start[:]
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class scc_graph:

	def __init__(self, N):
		self.N = N
		self.edges = []

	def add_edge(self, v, w):
		self.edges.append((v, w))

	def scc_ids(self):
		g = csr(self.N, self.edges)
		now_ord = group_num = 0
		visited = deque()
		low = [0] * self.N
		order = [-1] * self.N
		ids = [0] * self.N
		parent = [-1] * self.N
		for i in range(self.N):
			if order[i] == -1:
				stack = deque()
				stack.append(i)
				stack.append(i)
				while stack:
					v = stack.pop()
					if order[v] == -1:
						low[v] = order[v] = now_ord
						now_ord += 1
						visited.append(v)
						for i in range(g.start[v], g.start[v + 1]):
							to = g.elist[i]
							if order[to] == -1:
								stack.append(to)
								stack.append(to)
								parent[to] = v
							else:
								low[v] = min(low[v], order[to])
					else:
						if low[v] == order[v]:
							while True:
								u = visited.pop()
								order[u] = self.N
								ids[u] = group_num
								if u == v:
									break
							group_num += 1
						if parent[v] != -1:
							low[parent[v]] = min(low[parent[v]], low[v])
		for (i, x) in enumerate(ids):
			ids[i] = group_num - 1 - x
		return (group_num, ids)

	def scc(self):
		(group_num, ids) = self.scc_ids()
		groups = [[] for _ in range(group_num)]
		for (i, x) in enumerate(ids):
			groups[x].append(i)
		return groups
import sys
input = sys.stdin.buffer.readline
(N, M) = map(int, input().split())
sg = scc_graph(N)
for i in range(M):
	(a, b) = map(int, input().split())
	sg.add_edge(a, b)
scc = sg.scc()
print(len(scc))
for group in scc:
	print(str(len(group)) + ' ' + ' '.join(map(str, group)))


class csr:

	def __init__(self, n: int, edges: list):
		self.start = [0] * (n + 1)
		self.elist = [0] * len(edges)
		for e in edges:
			self.start[e[0] + 1] += 1
		for i in range(1, n + 1):
			self.start[i] += self.start[i - 1]
		counter = self.start[:]
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class internal_scc_graph:

	def __init__(self, n: int=0):
		self.__n = n
		self.__edges = []

	def num_vertices(self):
		return self.__n

	def add_edge(self, from_: int, to: int):
		self.__edges.append([from_, to])

	def scc_ids(self):
		g = csr(self.__n, self.__edges)
		now_ord = 0
		group_num = 0
		visited = []
		low = [0] * self.__n
		ord = [-1] * self.__n
		ids = [0] * self.__n
		parent = [-1] * self.__n
		for root in range(self.__n):
			if ord[root] == -1:
				stack = []
				stack.extend([root] * 2)
				while stack:
					v = stack.pop()
					if ord[v] == -1:
						visited.append(v)
						low[v] = now_ord
						ord[v] = now_ord
						now_ord += 1
						for i in range(g.start[v], g.start[v + 1]):
							to = g.elist[i]
							if ord[to] == -1:
								stack.extend([to] * 2)
								parent[to] = v
							else:
								low[v] = min(low[v], ord[to])
					else:
						if low[v] == ord[v]:
							while True:
								u = visited.pop()
								ord[u] = self.__n
								ids[u] = group_num
								if u == v:
									break
							group_num += 1
						if parent[v] != -1:
							low[parent[v]] = min(low[parent[v]], low[v])
		for (i, x) in enumerate(ids):
			ids[i] = group_num - 1 - x
		return [group_num, ids]

	def scc(self):
		ids = self.scc_ids()
		group_num = ids[0]
		counts = [0] * group_num
		for x in ids[1]:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for (i, x) in enumerate(ids[1]):
			groups[x].append(i)
		return groups

class scc_graph:

	def __init__(self, n: int):
		self.__internal = internal_scc_graph(n)

	def add_edge(self, from_: int, to: int):
		n = self.__internal.num_vertices()
		assert (0 <= from_) & (from_ < n)
		assert (0 <= to) & (to < n)
		self.__internal.add_edge(from_, to)

	def scc(self):
		return self.__internal.scc()
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(n, m) = map(int, readline().split())
data = list(map(int, read().split()))
sg = scc_graph(n)
it = iter(data)
for (a, b) in zip(it, it):
	sg.add_edge(a, b)
scc = sg.scc()
print(len(scc))
ans = []
for group in scc:
	tmp = [len(group)] + group
	ans.append(' '.join(map(str, tmp)))
print('\n'.join(map(str, ans)))


class CSR:

	def __init__(self, n: int, edges: list):
		self.start = [0] * (n + 1)
		self.elist = [0] * len(edges)
		for e in edges:
			self.start[e[0] + 1] += 1
		for i in range(1, n + 1):
			self.start[i] += self.start[i - 1]
		counter = self.start[:]
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class SccGraph:

	def __init__(self, n: int=0):
		self.__n = n
		self.__edges = []

	def __len__(self):
		return self.__n

	def add_edge(self, s: int, t: int):
		assert 0 <= s < self.__n and 0 <= t < self.__n
		self.__edges.append([s, t])

	def __scc_ids(self):
		g = CSR(self.__n, self.__edges)
		now_ord = group_num = 0
		visited = []
		low = [0] * self.__n
		order = [-1] * self.__n
		ids = [0] * self.__n
		parent = [-1] * self.__n
		for root in range(self.__n):
			if order[root] == -1:
				stack = [root, root]
				while stack:
					v = stack.pop()
					if order[v] == -1:
						visited.append(v)
						low[v] = order[v] = now_ord
						now_ord += 1
						for i in range(g.start[v], g.start[v + 1]):
							t = g.elist[i]
							if order[t] == -1:
								stack += [t, t]
								parent[t] = v
							else:
								low[v] = min(low[v], order[t])
					else:
						if low[v] == order[v]:
							while True:
								u = visited.pop()
								order[u] = self.__n
								ids[u] = group_num
								if u == v:
									break
							group_num += 1
						if parent[v] != -1:
							low[parent[v]] = min(low[parent[v]], low[v])
		for (i, x) in enumerate(ids):
			ids[i] = group_num - 1 - x
		return (group_num, ids)

	def scc(self):
		(group_num, ids) = self.__scc_ids()
		counts = [0] * group_num
		for x in ids:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for (i, x) in enumerate(ids):
			groups[x].append(i)
		return groups
(N, M) = map(int, input().split())
sg = SccGraph(N)
for _ in range(M):
	(a, b) = map(int, input().split())
	sg.add_edge(a, b)
scc = sg.scc()
print(len(scc))
for group in scc:
	print(*[len(group)] + group)


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** (-10)

def SCC(N, edges):
	nodes1 = [[] for i in range(N)]
	nodes2 = [[] for i in range(N)]
	for (u, v) in edges:
		nodes1[u].append(v)
		nodes2[v].append(u)
	T = []
	visited = [False] * N

	def rec1(cur):
		visited[cur] = True
		for nxt in nodes1[cur]:
			if not visited[nxt]:
				rec1(nxt)
		T.append(cur)
	for u in range(N):
		if not visited[u]:
			rec1(u)
	visited = [False] * N
	group = [0] * N
	grpnum = 0

	def rec2(cur):
		group[cur] = grpnum
		visited[cur] = True
		for nxt in nodes2[cur]:
			if not visited[nxt]:
				rec2(nxt)
	for u in reversed(T):
		if not visited[u]:
			rec2(u)
			grpnum += 1
	return (grpnum, group)
(N, M) = MAP()
edges = []
for i in range(M):
	(a, b) = MAP()
	edges.append((a, b))
(grpnum, group) = SCC(N, edges)
ans = [[] for i in range(grpnum)]
for i in range(N):
	ans[group[i]].append(i)
print(grpnum)
for i in range(grpnum):
	ans[i].insert(0, len(ans[i]))
	print(*ans[i])