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>
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
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;

struct SCC{
	vector<vector<int>>G,rG;
	vector<bool>used;
	vector<int>vs;
	void addEdge(int x,int y){
		G[x].push_back(y);
		rG[y].push_back(x);
	}
	void dfs(int x){
		used[x]=true;
		for(int i:G[x])if(!used[i])dfs(i);
		vs.push_back(x);
	}
	vector<int>cmp;
	void rdfs(int v,int k){
		used[v]=true;
		cmp[v]=k;
		for(int i:rG[v])if(!used[i])rdfs(i,k);
	}
	void scc(){
		fill(all(used),false);
		rep(i,len(G))if(!used[i])dfs(i);
		fill(all(used),false);
		int k=0;
		rev(i,len(vs))if(!used[vs[i]])rdfs(vs[i],k++);
	}
	SCC(int N):G(N),rG(N),used(N),cmp(N){}
};
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int N,M;
	cin>>N>>M;
	SCC scc(N);
	rep(i,M){
		int a,b;cin>>a>>b;
		scc.addEdge(a,b);
	}
	scc.scc();
	map<int,vector<int>>mp;
	rep(i,N)mp[scc.cmp[i]].push_back(i);
	cout<<len(mp)<<"\n";
	for(auto i:mp){
		cout<<len(i.second)<<" ";
		for(int j:i.second)cout<<j<<" ";
		cout<<"\n";
	}
}