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 <iostream>
#include <vector>
using namespace std;

struct StronglyConnectedComponents
{
	int V;
	const vector<vector<int>> &g;
	int num_of_comp;
	vector<int> comp;
	vector<vector<int>> dag;
	vector<vector<int>> group_set;

	vector<vector<int>> rg;
	vector<int> order;
	vector<bool> used;

	StronglyConnectedComponents(const vector<vector<int>> &g) : V(g.size()), g(g) {}

	void calc() {
		num_of_comp = 0;
		comp.assign(V, -1);
		used.assign(V, false);
		order.reserve(V);
		rg.resize(V);
		for (int i = 0; i < V; i++) {
			for (int e : g[i]) {
				rg[e].push_back(i);
			}
		}
		for (int i = 0; i < V; i++) {
			if (!used[i]) dfs1(i);
		}
		for (int i = V-1; i >= 0; i--) {
			const int v = order[i];
			if (comp[v] == -1) {
				dfs2(v);
				num_of_comp++;
			}
		}
		dag.resize(num_of_comp);
		group_set.resize(num_of_comp);
		for (int i = 0; i < V; i++) group_set[comp[i]].push_back(i);
		for (int i = 0; i < V; i++) {
			for (int e : g[i]) {
				const int x = comp[i], y = comp[e];
				if (x != y) dag[x].push_back(y);
			}
		}

	}

	void dfs1(int v) {
		used[v] = true;
		for (int nv : g[v]) {
			if (used[nv]) continue;
			dfs1(nv);
		}
		order.push_back(v);
	}

	void dfs2(int v) {
		comp[v] = num_of_comp;
		for (int nv : rg[v]) {
			if (comp[nv] != -1) continue;
			dfs2(nv);
		}
	}
};

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
	}
	StronglyConnectedComponents scc(g);
	scc.calc();
	cout << scc.num_of_comp << endl;
	for (int i = 0; i < scc.num_of_comp; i++) {
		int l = scc.group_set[i].size();
		printf("%d", l);
		for (int j = 0; j < l; j++) {
			printf(" %d", scc.group_set[i][j]);
		}
		printf("\n");
	}
	return 0;
}