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

Solution:
#include <vector>
#include <algorithm>
#include <cstddef>

struct strongly_connected_component {
	using size_type = std::size_t;
private : 
	std::vector<std::vector<size_type>> g, revg;
	std::vector<size_type> order, index;
	std::vector<bool> seen;

	void dfs (size_type v) {
		seen[v] = true;
		for (const size_type &u : g[v]) {
			if (not seen[u]) dfs(u);
		}
		order.push_back(v);
	}

	void dfs2 (size_type v, const size_type idx) {
		seen[v] = true;
		index[v] = idx;
		for (size_type u : revg[v]) {
			if (not seen[u]) dfs2(u, idx);
		}
	}

public : 
	strongly_connected_component (size_type n)
	: g(n), revg(n), index(n), seen(n) { }

	void add_edge (size_type u, size_type v) noexcept {
		g[u].push_back(v);
		revg[v].push_back(u);
	}

	size_type build() {
		order.clear();
		std::fill(seen.begin(), seen.end(), false);
		for (size_type v = 0; v < g.size(); v++) {
			if (not seen[v]) dfs(v);
		}
		
		size_type idx = 0;
		std::fill(seen.begin(), seen.end(), false);
		std::reverse(order.begin(), order.end());
		for (const size_type &v : order) {
			if (not seen[v]) dfs2(v, idx++);
		}
		return idx;
	}

	size_type operator[] (size_type v) {
		return (index[v]);
	}

};

#include <iostream>
#include <vector>
#include <cstddef>

using usize = std::size_t;

int main() {
	usize n, m;
	std::cin >> n >> m;
	strongly_connected_component g(n);
	for (usize i = 0; i < m; i++) {
		usize a, b;
		std::cin >> a >> b;
		g.add_edge(a, b);
	}
	
	std::vector<std::vector<usize>> ans(g.build());

	for (usize i = 0; i < n; i++) {
		ans[g[i]].push_back(i);
	}
	
	std::cout << ans.size() << '\n';
	for (usize i = 0; i < ans.size(); i++) {
		std::cout << ans[i].size();
		for (usize v : ans[i]) std::cout << ' ' << v;
		std::cout << '\n';
	}

	return 0;
}