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;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

int N,M;
vector<int>G[500005],rG[500005];
bool used[500005];
vector<int>vs,vs2;
void dfs(int x){
	used[x]=true;
	for(int i:G[x])if(!used[i])dfs(i);
	vs.push_back(x);
}
void rdfs(int x){
	used[x]=true;
	vs2.push_back(x);
	for(int i:rG[x])if(!used[i])rdfs(i);
}
void scc(){
	rep(i,N)if(!used[i])dfs(i);
	vector<vector<int>>ans;
	memset(used,0,sizeof(used));
	rev(i,N)if(!used[vs[i]]){
		vs2.clear();rdfs(vs[i]);
		ans.push_back(vs2);
	}
	cout<<len(ans)<<"\n";
	for(auto i:ans){
		cout<<len(i)<<" ";
		for(int j:i)cout<<j<<" ";
		cout<<"\n";
	}
}
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N>>M;
	rep(i,M){
		int a,b;cin>>a>>b;G[a].push_back(b);rG[b].push_back(a);
	}
	scc();
}