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 <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;

using namespace std;
typedef long long ll;

const int N_MAX = 500000;
int N;
bool used[N_MAX];
int idx[N_MAX];
vector<int> vs;
vector<int> buf;
vector<int> G[N_MAX];
vector<int> G_inv[N_MAX];
vector<vector<int>> ans;

void clear(){
    for(int i = 0; i < N; i++) used[i] = false;
}

void dfs1(int v){
    used[v] = true;
    for(int i = 0; i < G[v].size(); i++){
        if(!used[G[v][i]]) dfs1(G[v][i]);
    }
    vs.push_back(v);
}

void dfs2(int v, int k){
    used[v] = true;
    idx[v] = k;
    for(int i = 0; i < G_inv[v].size(); i++){
        if(!used[G_inv[v][i]]) dfs2(G_inv[v][i], k);
    }
    buf.push_back(v);
}

void scc(){
    for(int i = 0; i < N; i++){
        if(!used[i]) dfs1(i);
    }
    clear();
    int cur = 0;
    for(int i = vs.size()-1; i >= 0; i--){
        if(!used[vs[i]]) {
            dfs2(vs[i], cur);
            cur++;
            ans.push_back(buf);
            buf.clear();
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int M;
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int a, b; cin >> a >> b;
        if(a == b) continue;
        G[a].push_back(b);
        G_inv[b].push_back(a);
    }
    scc();
    cout << ans.size() << endl;
    for(auto v : ans){
        cout << v.size() << ' ';
        for(int i : v) cout << i << ' ';
        cout << endl;
    }
}