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>
//#include <chrono>
//#pragma GCC optimize("Ofast")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
typedef pair<ll, ll> P;
const ll INF = (1LL<<60);

void dfs1(int v, int &k, mat &G, vec &level){
    level[v] = -2;
    for(int to : G[v]){
        if(level[to] == -1) dfs1(to, k, G, level);
    }
    level[v] = k++;
}

void dfs2(int v, mat &G, vector<bool> &used, vec &res){
    used[v] = true;
    res.push_back(v);
    for(int to : G[v]) if(!used[to]) dfs2(to, G, used, res);
}

void scc(mat &G, mat &res){
    int n = G.size();
    mat G_rev(n, vec(0));
    rep(u, n) rep(v, (int)G[u].size()) G_rev[G[u][v]].push_back(u);
    vec level(n, -1), ord(n);
    vector<bool> used(n, false);
    int k(0);
    rep(i, n) if(level[i] == -1) dfs1(i, k, G, level);
    rep(i, n) ord[level[i]] = i;
    Rrep(i, n) {
        if(!used[ord[i]]) {
            vec temp(0);
            dfs2(ord[i], G_rev, used, temp);
            res.push_back(temp);
        }
    }
}

int main() {
    cin>>N>>M;
    mat G(N, vec(0));
    vec num_in(N, 0);
    rep(i,M){
        int a, b;
        scanf("%d%d", &a, &b);
        G[a].push_back(b);
    }
    mat scc_list(0);
    scc(G, scc_list);
    printf("%d\n", (int)scc_list.size());
    for(vec v : scc_list){
        int n = v.size();
        printf("%d ", n);
        rep(i, n) printf("%lld%c", v[i], " \n"[i == n - 1]);
    }
}