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;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
struct StronglyConnectedComponent{
  int n, comp_size;
  vector<vector<int>> g, revg;
  vector<int> comp, order, used;

  StronglyConnectedComponent (int sz) {
    n = sz;
    g.resize(n); revg.resize(n);
    comp.assign(n, -1);
    used.assign(n, 0);
  }

  int operator[] (int u) {
    return comp[u];
  }

  void add_edge (int u, int v){
    g[u].emplace_back(v);
    revg[v].emplace_back(u);
  }

  void dfs (int u){
    if (used[u]) return ;
    used[u] = 1;
    for (auto v : g[u]) dfs(v);
    order.emplace_back(u);
    return ;
  }

  void rdfs (int u, int k){
    if (comp[u] != -1) return ;
    comp[u] = k;
    for (auto v : revg[u]) rdfs(v, k);
    return ;
  }

  void build (vector<vector<int>> &ref){
    for (int i = 0; i < n; i++) dfs(i);
    reverse(order.begin(), order.end());
    int cur = 0;
    for (auto i : order) {
      if (comp[i] == -1) {
        rdfs(i, cur);
        cur++;
      }
    }
    ref.resize(cur);
    for (int i = 0; i < g.size(); i++) {
      for (auto j : g[i]) {
        int u = comp[i], v = comp[j];
        if (u == v) continue;
        ref[u].emplace_back(v);
      }
    }
  }

};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  StronglyConnectedComponent scc(n);
  rep(i,m) {
    int a, b;
    cin >> a >> b;
    scc.add_edge(a, b);
  }

  vector<vector<int>> g;
  scc.build(g);
  vector<vector<int>> res(g.size());
  for (int i = 0; i < n; i++) res[scc[i]].emplace_back(i);

  cout << g.size() << "\n";
  for (int i = 0; i < (int)g.size(); i++) {
    cout << res[i].size() << " ";
    for (auto e : res[i]) cout << e << " ";
    cout << "\n";
  }
  return 0; 
}