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 <deque>
using i64 = long long;

std::vector<int> comp, done;
std::vector<std::vector<int>> g, r, scc, vs;
std::deque<int> t;

void add_edge(const int u, const int v) {
    g[u].push_back(v);
    r[v].push_back(u);
}

void dfs(const int v, const int p = -1) {
    if (done[v]) return;
    done[v] = 1;
    for (auto to : g[v]) {
        if (v == p) continue;
        dfs(to, v);
    }
    t.push_front(v);
}

void dfs2(const int v, const int p, const int c) {
    if (comp[v] >= 0) return;
    comp[v] = c;
    for (auto to : r[v]) {
        if (v == p) continue;
        dfs2(to, v, c);
    }
}

int main() {
    int n, m;
    std::cin >> n >> m;
    g.resize(n); r.resize(n); comp.resize(n, -1); done.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;
        add_edge(a, b);
    }

    for (int i = 0; i < n; i++) if (!done[i]) dfs(i);

    int c = 0;
    for (auto i : t) if (comp[i] < 0) dfs2(i, -1, c++);

    scc.resize(c), vs.resize(c);
    for (int i = 0; i < n; i++) {
        vs[comp[i]].push_back(i);
        for (const auto to : g[i]) {
            const int j = comp[i], k = comp[to];
            if (j != k) scc[j].push_back(k);
        }
    }

    std::cout << c << '\n';
    for (int i = 0; i < c; i++) {
        std::cout << vs[i].size();
        for (const int v : vs[i]) std::cout << ' ' << v;
        std::cout << '\n';
    }

    return 0;
}