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 <iostream>
#include <vector>
#include <map>
using namespace std;

struct Graph
{
    int n;
    vector<vector<int>> g;
    
    Graph(){}
    
    Graph(int n) : n(n){
        g.resize(n);
    }
    
    void add_edge(int from, int to){
        g[from].push_back(to);
    }
};

struct SCC      //StronglyConnectedComponents
{
    int n;
    int k;
    vector<vector<int>> g, rg;
    vector<bool> used;
    vector<int> cmp;
    vector<int> vs;
    
    void add_edge(int from, int to){
        g[from].push_back(to);
        rg[to].push_back(from);
    }
    
    SCC(int n) : n(n){
        g.resize(n);
        rg.resize(n);
        used.resize(n);
        cmp.resize(n);
        vs.resize(n);
    }
    
    void dfs(int u, int &l){
        used[u] = true;
        for(int v : g[u]){
            if(!used[v]) dfs(v, l);
        }
        vs[l] = u;
        l++;
    }
    
    void rdfs(int u, int k){
        used[u] = true;
        cmp[u] = k;
        for(int v : rg[u]){
            if(!used[v]) rdfs(v, k);
        }
    }
    
    int decomposition(){
        int l = 0;
        for(int i = 0; i < n; i++){
            if(!used[i]) dfs(i, l);
        }
        for(int i = 0; i < n; i++) used[i] = false;
        k = 0;
        for(int i = n - 1; i >= 0; i--){
            if(!used[vs[i]]){
                rdfs(vs[i], k);
                k++;
            }
        }
        return k;
    }
};

vector<int> v[500005];

int main()
{
    int n, m;
    cin >> n >> m;
    SCC g(n);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        g.add_edge(a, b);
    }
    int k = g.decomposition();
    for(int i = 0; i < n; i++){
        v[g.cmp[i]].push_back(i);
    }
    cout << k << endl;
    for(int i = 0; i < k; i++){
        cout << (int)v[i].size();
        for(int j : v[i]) cout << " " << j;
        cout << endl;
    }
}