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>
using namespace std;
const int MAXN = 1e5 + 5;
// LatexBegin
struct SCC { int stamp, scc_num;
  struct Node : vector<int> { 
    int dfn, low, scc; bool inS;
    Node() { dfn = low = scc = -1; inS = false; }
  };
  vector<Node> N; vector<int> stk;
  void init(int n) { 
    N.clear(); N.resize(n); stk.clear();
  }
  void addEdge(int u, int v) { N[u].push_back(v); }
  void Tarjan(int u) { N[u].low = N[u].dfn = stamp++;
    stk.push_back(u); N[u].inS = true;
    for (auto &v : N[u]) if (!~N[v].dfn) Tarjan(v),
      N[u].low = min(N[u].low, N[v].low);
    else if (N[v].inS)
      N[u].low = min(N[u].low, N[v].dfn);
    if (N[u].dfn == N[u].low) {
      int v; do { v = stk.back(); stk.pop_back();
        N[v].scc = scc_num; N[v].inS = false;
      } while (v != u); scc_num++;
    }
  }
  void run() { stamp = scc_num = 0;
    for (int i = 0 ; i < N.size() ; i++)
      if (!~N[i].dfn) Tarjan(i);
  }
} solver;
// LatexEnd
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    solver.init(n);
    while (m--) {
        int u, v; cin >> u >> v;
        solver.addEdge(u, v);
    }
    solver.run();
    auto N = solver.N;
    vector<vector<int>> ans(solver.scc_num);
    for (int i = 0 ; i < n ; i++) 
        ans[N[i].scc].push_back(i);
    reverse(ans.begin(), ans.end());
    cout << solver.scc_num << '\n';
    for (int i = 0 ; i < solver.scc_num ; i++) {
        cout << ans[i].size();
        for (auto &v : ans[i])
            cout << ' ' << v;
        cout << '\n';
    }
}