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 <algorithm>
#include <set>
using namespace std;
struct scc{
    int N;
    vector<vector<int>> G, rG;
    vector<bool> used;
    vector<int> temp;
    vector<int> order;//分解後のトポロジカル順序
    vector<vector<int>> cnt;
    scc(int V){
        G.resize(V);
        rG.resize(V);
        N = V;
        order.resize(V);
    }
    void add(int s, int t){
        G[s].emplace_back(t);
        rG[t].emplace_back(s);
    }
    void dfs(int s){
        used[s] = true;
        for(int j: G[s]){
            if(!used[j]) dfs(j);
        }
        temp.emplace_back(s);
    }
    void rdfs(int s, int k){
        used[s] = true;
        order[s] = k;
        for(int j: rG[s]){
            if(!used[j]) rdfs(j, k);
        }
    }
    vector<vector<int>> solve(){//分解後の頂点数を返す
        used.resize(N, false);
        for(int i = 0; i < N; i++){
            if(!used[i]) dfs(i);
        }
        used.assign(N, false);  
        int k = 0;
        for(int i = (int)temp.size() - 1; i >= 0; i--){ //番号が大きい方から順にdfs
            if(!used[temp[i]]) {
                rdfs(temp[i], k);
                k++;
            }
        }
        cnt.resize(k);
        for(int i = 0; i < N; i++){
            cnt[order[i]].emplace_back(i);
        }
        return cnt;
    }
};
int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    scc scc(N);
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        scc.add(a, b);
    }
    vector<vector<int>> k = scc.solve();
    cout << k.size() << endl;
    for(int i = 0; i < (int)k.size(); i++){
        int size = k[i].size();
        cout << size << ' ';
        for(int j = 0; j < size; j++){
            if(j != size - 1) cout << k[i][j] << ' ';
            else cout << k[i][j] << endl;
        }
    }
}