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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
struct SCC{
	vector<vector<int>> g;
	int n, k;
	vector<int> cmp, ord, low, visited;
	int num;
	void dfs(int x){
		ord[x]=low[x]=num++;
		visited.push_back(x);
		for(auto y:g[x]){
			if(ord[y]==-1){
				dfs(y);
				low[x]=min(low[x], low[y]);
			}else{
				low[x]=min(low[x], ord[y]);
			}
		}
		if(ord[x]==low[x]){
			while(1){
				int v=visited.back();
				visited.pop_back();
				cmp[v]=k;
				ord[v]=n;
				if(v==x) break;
			}
			k++;
		}
	}
	SCC(const vector<vector<int>> &g):g(g), n(g.size()), cmp(n), ord(n, -1), low(n){
		num=0, k=0;
		for(int x=0; x<n; x++){
			if(ord[x]==-1) dfs(x);
		}
		for(int x=0; x<n; x++){
			cmp[x]=k-1-cmp[x];
		}
	}
};
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	vector<vector<int>> g(n);
	for(int i=0; i<m; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		g[a].push_back(b);
	}
	SCC scc(g);
	printf("%d\n", scc.k);
	vector<vector<int>> v(scc.k);
	for(int i=0; i<n; i++) v[scc.cmp[i]].push_back(i);
	for(auto w:v){
		printf("%d", w.size());
		for(auto x:w) printf(" %d", x);
		printf("\n");
	}
	return 0;
}