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>
using namespace std;
int N, M; 
vector<int> E[500010]; 
vector<int> F[500010];
vector<int> order; 
vector<int> scc[500010]; 
bool used[500010]; 
void dfs(int v){
	used[v] = true; 
	for(int p : E[v]){
		if(used[p]) continue; 
		dfs(p); 
	}
	order.emplace_back(v); 
}
void dfs2(int v, int k){
	used[v] = true; 
	scc[k].emplace_back(v); 
	for(auto p : F[v]){
		if(used[p]) continue; 
		dfs2(p, k); 
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for(int i = 0; i < M; i++){
		int u, v; cin >> u >> v; 
		E[u].emplace_back(v); 
		F[v].emplace_back(u); 
	}
	for(int i = 0; i < N; i++){
		if(used[i]) continue; 
		dfs(i); 
	}
	fill(used, used + N, false); 
	reverse(order.begin(), order.end()); 
	int k = 0; 
	for(auto p : order){
		if(used[p]) continue; 
		dfs2(p, k); k++; 
	}
	cout << k << "\n";
	for(int i = 0; i < k; i++){
		cout << scc[i].size() << " "; 
		for(auto p : scc[i]) cout << p << " ";
		cout << "\n"; 
	}	
}