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

Solution (in PYTHON3):

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

	#順方向のグラフ上でDFSを行い、帰りがけ順に頂点を記録
	for i in range(N):
		if not visit[i]:
			dfs(i)

	#逆方向のグラフ上で帰りが遅かった頂点から順にDFSを行い分解
	visit = [0] * N
	num = 0
	for i in reversed(order):
		if not visit[i]:
			dfs_rev(i, num)
			num += 1

	return num, group

#scc後のDAGを構築
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])




if __name__ == '__main__':
	main()