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;
using ll = long long;

class Scc {
private:
	int n;
	vector<vector<int>> edge, rev;
	vector<int>  post_order;
	vector<bool> seen0, seen1;
	vector<int>  typea;
	vector<vector<int>> new_edge;
	int ord;
	int type_num;

	void dfs0(int v) {
		if(seen0[v])return;
		seen0[v] = true;
		for(auto i : edge[v]) {
			dfs0(i);
		}
		post_order[v] = ord++;
	}

	void dfs1(int v, int typ) {
		if(seen1[v])return;
		seen1[v] = true;
		typea[v] = typ;
		for(auto i : rev[v]) {
			dfs1(i, typ);
		}
	}


public:


	int types(){return type_num;}
	int type(int vertex){return typea[vertex];}

	Scc(const vector<vector<int>>& _edge):edge(_edge) {
		n = edge.size();
		typea.resize(n), post_order.resize(n), seen0.resize(n), seen1.resize(n), rev.resize(n);
		ord = 0;
		for(int i = 0; i < n; i++)dfs0(i);
		for(int i = 0; i < n; i++) {
			for(auto j : edge[i])rev[j].push_back(i);
		}
		vector<int> dfs1_ord(n);
		for(int i = 0; i < n; i++)dfs1_ord[post_order[i]] = i;
		type_num = 0;
		for(int i = n - 1; i >= 0; i--)if(!seen1[dfs1_ord[i]])dfs1(dfs1_ord[i], type_num++);
	}
};

/*
	Constructor   : O(V)
	Scc::types()  : O(1) 強連結成分の数 
	Scc::type(int): O(1) 引数がどの強連結成分に属するか(type(i) < type(j)ならばトポロジカルソート順でi < j)
*/


int main()
{
	int n, m; cin >> n >> m;
	vector<vector<int>> hen(n);
	for(int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		hen[a].push_back(b);
	}
	Scc scc(hen);
	cout << scc.types() << endl;
	vector<vector<int>> type(scc.types());
	for(int i = 0; i < n; i++)type[scc.type(i)].push_back(i);
	for(int i = 0; i < scc.types(); i++) {
		int ns = type[i].size();
		cout << ns << " ";
		for(int j = 0; j < ns; j++)cout << type[i][j] << (j == ns - 1 ? '\n' : ' ');
	}
	return 0;
}