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;
const int maxx = 500005;
vector<int> g[maxx], t[maxx];
bool visited[maxx];
stack<int> topo;// stack
vector<int> v[maxx]; // save the strongly connected components
void dfs(int u) // dfs push all vertices as their finish time to a stack
{
    visited[u] = 1;
    for(int nei: g[u])
        if(!visited[nei])
            dfs(nei);
    topo.push(u);
}
 
void scc(int idx, int u)
{
    visited[u] = 1;
    v[idx].push_back(u);
    for(int nei: t[u])
        if(!visited[nei])
            scc(idx, nei);
}
int main()
{
    cin >> n; // the number of vertice
    cin >> m; // the number of edge
    for(int i = 0; i < m; i++){
		int x, y; cin>>x>>y;
        g[x].push_back(y);
        t[y].push_back(x); // transpose of g
    }
    
    memset(visited, 0, sizeof(visited)); //mark all vertices unvisited for the second DFS
    for(int i = 0; i < n; i++)
    {
        if(!visited[i])
            dfs(i);
    }
    memset(visited, 0, sizeof(visited));//mark all vertices unvisited for the second DFS
    int x = 0;
    while(!topo.empty())
    {
        int u = topo.top(); topo.pop();
        if(!visited[u])
            scc(x++, u);
    }
    cout<<x<<endl;
	for(int i = 0; i < x; i++){
		cout<<v[i].size()<<" ";
		for(int j : v[i]){
			cout<<j<<" ";
		}
		cout<<endl;
	}
}