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;

class SCC {
private:
  const int N;
  vector<vector<int>> G;
  vector<vector<int>> R;
  vector<int> ord, low;
  stack<int> st;
  void dfs(const int u, int &tm) {
    ord.at(u) = low.at(u) = tm++, st.push(u);
    for (int v : G.at(u)) {
      if (ord.at(v) < 0) {
        dfs(v, tm);
        low.at(u) = min(low.at(u), low.at(v));
      } else if (cmp.at(v) < 0) {
        low.at(u) = min(low.at(u), ord.at(v));
      }
    }
    if (ord.at(u) == low.at(u)) {
      R.push_back(vector<int>{});
      while (true) {
        const int v = st.top();
        st.pop();
        cmp.at(v) = cnt;
        R.back().push_back(v);
        if (v == u) break;
      }
      cnt++;
    }
  }

public:
  vector<vector<int>> graph;
  vector<int> cmp;
  int cnt;
  SCC(const int n) : N(n), G(n), ord(n, -1), low(n), cmp(n, -1), cnt(0) {}
  void add(const int from, const int to) { G.at(from).push_back(to); }
  vector<vector<int>> solve() {
    int tm = 0;
    for (int i = 0; i < N; i++) {
      if (ord.at(i) < 0) dfs(i, tm);
    }
    for (int i = 0; i < N; i++) cmp.at(i) = cnt - 1 - cmp.at(i);
    reverse(R.begin(), R.end());
    return R;
  }
  vector<vector<int>> build() {
    graph.resize(cnt);
    for (int i = 0; i < N; i++) {
      for (int j : G.at(i)) {
        if (cmp.at(i) != cmp.at(j)) {
          graph.at(cmp.at(i)).push_back(cmp.at(j));
        }
      }
    }
    return graph;
  }
};

signed main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  SCC SC(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    SC.add(a, b);
  }

  auto G = SC.solve();
  cout << G.size() << "\n";
  for (int i = 0, h = G.size(); i < h; i++) {
    cout << G.at(i).size();
    for (int j = 0, w = G.at(i).size(); j < w; j++) {
      cout << " " << G.at(i).at(j);
    }
    cout << "\n";
  }
}