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>

template<typename T>
struct edge {
    std::size_t to; T cost;
    edge (std::size_t to, T cost = 1) : to(to), cost(cost) { }
    bool operator< (const edge &r) const { return (cost < r.cost); }
};

template<typename T>
using graph = std::vector<std::vector<edge<T>>>;

#include <stack>
#include <cstddef>
#include <functional>
#include <algorithm>

template<class T>
std::vector<std::vector<std::size_t>> strongly_connected_component (const graph<T> &g) {
	using std::size_t;
	size_t index = 0;
	std::vector<std::vector<size_t>> scc;
	std::vector<size_t> low(g.size()), order(g.size());
	std::stack<size_t> stack;
	std::vector<bool> instack(g.size(), false);
	std::function<void(size_t)> dfs = [&] (size_t v) {
		low[v] = order[v] = ++index;
		stack.push(v); instack[v] = true;
		for (const auto &e : g[v]) {
			if (order[e.to] == 0) {
				dfs(e.to);
				if (low[v] > low[e.to]) low[v] = low[e.to];
			} else if (instack[e.to] and low[v] > order[e.to]) {
				low[v] = order[e.to];
			}
		}
		if (low[v] == order[v]) {
			scc.push_back(std::vector<size_t>());
			while (true) {
				const size_t u = stack.top();
				stack.pop(); instack[u] = false;
				scc.back().push_back(u);
				if (v == u) break;
			}
		}
	};
	for (size_t v = 0; v < g.size(); v++) {
		if (order[v] == 0) dfs(v);
	}
	std::reverse(scc.begin(), scc.end());
	return scc;
}

#include <iostream>

using usize = std::size_t;

int main() {
	usize n, m;
	std::cin >> n >> m;
	graph<int> g(n);
	for (usize i = 0; i < m; i++) {
		usize a, b;
		std::cin >> a >> b;
		g[a].emplace_back(b);
	}
	
	auto scc = strongly_connected_component(g);
	std::cout << scc.size() << '\n';
	for (auto &v : scc) {
		std::cout << v.size();
		for (auto &e : v) std::cout << ' ' << e;
		std::cout << '\n';
	}
	
	return 0;
}