#line 1 "verify/yosupo/graph/strongly-connected-component/scc.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#line 2 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;
using i128 = __int128_t;
using u32 = uint32_t;
using u64 = uint64_t;
template<class T>
using PQ = priority_queue<T,vector<T>,greater<T>>;
const int INF=INT_MAX/2;
const ll LINF=LLONG_MAX/4;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define SZ(a) (int)(a.size())
#define SORT(a) sort(ALL(a))
#define RSORT(a) sort(RALL(a))
#define REV(a) reverse(ALL(a))
#define UNI(a) a.erase(unique(ALL(a)),a.end())
#define LB(a,x) (int)(lower_bound(ALL(a),x)-a.begin())
#define UB(a,x) (int)(upper_bound(ALL(a),x)-a.begin())
#define FIND(a,x) (int)(find(ALL(a),x)-a.begin())
#define COUNT(a,x) (int)count(ALL(a),x)
#define MIN(a) *min_element(ALL(a))
#define MAX(a) *max_element(ALL(a))
template<class T,class U>
bool chmin(T &a,U b){return b<a?a=b,1:0;}
template<class T,class U>
bool chmax(T &a,U b){return a<b?a=b,1:0;}
template<class T>
T floor(T a,T b){return a/b-((a^b)<0&&a%b);}
template<class T>
T ceil(T a,T b){return a/b+((a^b)>=0&&a%b);}
int popcnt(ll x){return __builtin_popcountll(x);}
int topbit(ll x){return x==0?-1:63-__builtin_clzll(x);}
int lowbit(ll x){return x==0?-1:__builtin_ctzll(x);}
template<class T,class U>
T SUM(const U &a){return accumulate(ALL(a),T{});}
template<class T>
vector<int> argsort(const vector<T> &a){
vector<int> p(SZ(a));
iota(ALL(p),0);
stable_sort(ALL(p),[&](int i,int j){return a[i]<a[j];});
return p;
}
template<class T,size_t D=0>
struct VecBuilder{
array<size_t,D> d;
VecBuilder<T,D+1> operator[](size_t n)const{
VecBuilder<T,D+1> res{};
for(size_t i=0;i<D;i++)res.d[i]=d[i];
res.d[D]=n;
return res;
}
template<size_t I=0>
auto build(const T &x)const{
if constexpr(I+1==D)return vector<T>(d[I],x);
else return vector<decltype(build<I+1>(x))>(d[I],build<I+1>(x));
}
auto operator()(const T &x=T())const{
static_assert(D>0);
return build(x);
}
};
template<class T>
inline constexpr VecBuilder<T> VEC{};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "graph/graph-base.hpp"
/**
* Author: Teetat T.
* Date: 2024-06-15
* Description: Graph Base
*/
template<class T>
struct Edge{
int from,to,id;
T cost;
Edge(int _from,int _to,T _cost,int _id):from(_from),to(_to),cost(_cost),id(_id){}
operator int()const{return to;}
};
template<class T=void,bool directed=false>
struct Graph{
static constexpr bool is_directed=directed;
static constexpr bool is_weighted=!is_same<T,void>::value;
using cost_type = std::conditional_t<is_weighted,T,int>;
using edge_type = Edge<cost_type>;
int n,m;
vector<edge_type> edges;
vector<vector<edge_type>> g;
vector<int> _deg,_indeg,_outdeg;
Graph():n(0),m(0){}
Graph(int _n):n(_n),m(0),g(_n){}
vector<edge_type> &operator[](int u){return g[u];}
void add_edge(int from,int to,cost_type cost=1,int id=-1){
assert(0<=from&&from<n&&0<=to&&to<n);
if(id==-1)id=m;
edges.emplace_back(edge_type(from,to,cost,id));
g[from].emplace_back(edge_type(from,to,cost,id));
if(!is_directed)g[to].emplace_back(edge_type(to,from,cost,id));
m++;
}
void calc_deg(){
_deg.assign(n,0);
for(auto &e:edges)_deg[e.from]++,_deg[e.to]++;
}
void calc_inout_deg(){
_indeg.assign(n,0);
_outdeg.assign(n,0);
for(auto &e:edges)_outdeg[e.from]++,_indeg[e.to]++;
}
const vector<int> °_array(){
if(_deg.empty())calc_deg();
return _deg;
}
const vector<int> &indeg_array(){
if(_indeg.empty())calc_inout_deg();
return _indeg;
}
const vector<int> &outdeg_array(){
if(_outdeg.empty())calc_inout_deg();
return _outdeg;
}
int deg(int u){return deg_array()[u];}
int indeg(int u){return indeg_array()[u];}
int outdeg(int u){return outdeg_array()[u];}
Graph reverse(){
assert(is_directed);
Graph res(n);
for(auto &e:edges)res.add_edge(e.to,e.from,e.cost,e.id);
return res;
}
};
template<class T=void,bool directed=false>
Graph<T,directed> read_graph(int n,int m,int offset=1){
using G = Graph<T,directed>;
G g(n);
for(int i=0;i<m;i++){
int u,v;
cin >> u >> v;
u-=offset,v-=offset;
if(g.is_weighted){
typename G::cost_type w;
cin >> w;
g.add_edge(u,v,w);
}else{
g.add_edge(u,v);
}
}
return g;
}
template<class T=void,bool directed=false>
Graph<T,directed> read_tree(int n,int offset=1){
return read_graph<T,directed>(n,n-1,offset);
}
#line 2 "graph/strongly-connected-component.hpp"
/**
* Author: Teetat T.
* Date: 2024-06-28
* Description: Strongly Connected Component.
*/
template<class G>
pair<int,vector<int>> strongly_connected_component(G &g){
static_assert(G::is_directed);
int n=g.n;
vector<int> disc(n,-1),low(n),scc(n,-1);
stack<int> st;
vector<bool> in_st(n);
int t=0,scc_cnt=0;
function<void(int,int)> dfs=[&](int u,int p){
disc[u]=low[u]=t++;
st.emplace(u);
in_st[u]=true;
for(int v:g[u]){
if(disc[v]==-1){
dfs(v,u);
low[u]=min(low[u],low[v]);
}else if(in_st[v]){
low[u]=min(low[u],disc[v]);
}
}
if(disc[u]==low[u]){
while(true){
int v=st.top();
st.pop();
in_st[v]=false;
scc[v]=scc_cnt;
if(v==u)break;
}
scc_cnt++;
}
};
for(int i=0;i<n;i++)if(disc[i]==-1)dfs(i,-1);
return {scc_cnt,scc};
}
#line 5 "verify/yosupo/graph/strongly-connected-component/scc.test.cpp"
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n,m;
cin >> n >> m;
Graph g=read_graph<void,true>(n,m,0);
auto [k,scc]=strongly_connected_component(g);
vector<vector<int>> ans(k);
for(int i=0;i<n;i++)ans[scc[i]].emplace_back(i);
reverse(ans.begin(),ans.end());
cout << k << "\n";
for(auto &v:ans){
cout << v.size();
for(auto x:v)cout << " " << x;
cout << "\n";
}
}
verify/yosupo/graph/strongly-connected-component/scc.test.cpp