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 <bits/stdc++.h>
#define Int int64_t

using namespace std;

struct StronglyConnectedComponent {
	int N;
	vector<vector<int>> G, rG, T, C;
	vector<int> vs, used, belong;
	StronglyConnectedComponent(int n) :
		N(n), used(n), belong(n), G(n), rG(n)
	{}

	void add_edge(int from, int to) {
		G[from].push_back(to);
		rG[to].push_back(from);
	}
	void dfs(int v) {
		used[v] = 1;
		for (auto u : G[v]) {
			if (!used[u]) { dfs(u); }
		}
		vs.push_back(v);
	}
	void rdfs(int v, int k) {
		used[v] = 1;
		belong[v] = k;
		C[k].push_back(v);
		for (auto u : rG[v]) {
			if (!used[u]) { rdfs(u, k); }
		}
	}

	int build() {
		fill(used.begin(), used.end(), 0);
		vs.clear();
		for (int i = 0; i < N; ++i) {
			if (!used[i]) { dfs(i); }
		}
		fill(used.begin(), used.end(), 0);
		int k = 0;
		for (int i = vs.size() - 1; i >= 0; --i) {
			if (used[vs[i]]) { continue; }
			T.push_back(vector<int>());
			C.push_back(vector<int>());
			rdfs(vs[i], k++);
		}
		for (int i = 0; i < N; ++i) {
			for (auto u : G[i]) {
				if (belong[i] != belong[u]) {
					T[belong[i]].push_back(belong[u]);
				}
			}
		}
		for (int i = 0; i < k; ++i) {
			sort(T[i].begin(), T[i].end());
			T[i].erase(unique(T[i].begin(), T[i].end()), T[i].end());
		}
		return k;
	}
};

int main() {
	int N, M;
	cin >> N >> M;
	StronglyConnectedComponent scc(N);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		scc.add_edge(a, b);
	}

	int K = scc.build();
	cout << K << "\n";
	for (int i = 0; i < K; ++i) {
		int n = scc.C[i].size();
		cout << n << " ";
		for (int j = 0; j < n; ++j) {
			cout << scc.C[i][j] << (j < n - 1 ? " " : "\n");
		}
	}

	return 0;
}