// bibliotecile folosite
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
// fisierele din care citesc si scriu
ifstream fin("ctc.in");
ofstream fout("ctc.out");
// declar lista de adiacenta si lista inversa
vector<int> graf[100001]; // contine muchiile in directia originala
vector<int> invers[100001]; // contine muchiile in directia inversa
// vreau sa contorizez nodurile vizitate
bool vizitat[100001] = {};
// avem 3 vectori
vector<int> ordine; // rerine nodurile in ordinea terminarii primului dfs
vector<int> componenta; // retine nodurile componentei descoperite acum
vector<vector<int>> solutie; // retine toate componentele descoperite
// avem 2 functii dfs
// primul dfs("dfs1") doar parcurgem graful si retinem ordinea de terminare
void dfs1(int nod){
vizitat[nod] = true; // setez nodul ca vizitat
for(int vecin : graf[nod]){ // parcurg vecinii nodului
if(!vizitat[vecin]){ // daca vecinul nu a fost vizitat
dfs1(vecin); // il vizitez si pe el
}
}
ordine.push_back(nod); // adaug nodul dupa ce am terminat
}
// al doilea dfs("dfs2") parcurgem graful invers si retinem componentele
void dfs2(int nod){
vizitat[nod] = true; // setez nodul ca vizitat in a doua parcurgere
componenta.push_back(nod); // adaug nod in componenta curenta
for(int vecin : invers[nod]){ // exact ca la primul dfs
if(!vizitat[vecin]){ // doar ca parcurg graful invers
dfs2(vecin);
}
}
}
int main(){
// citesc numarul de noduri si muchii
int n, m;
fin >> n >> m;
// formez legarurile(lista de adiacenta pentru ambele grafuri)
for(int i = 0; i < m; i++){
int a, b;
fin >> a >> b;
graf[a].push_back(b);
invers[b].push_back(a);
}
// parcurg toate nodurile pentru a ma asigura ca vizitez intreg graful
for(int i = 1; i <= n; i++){
if(!vizitat[i]){
dfs1(i);
}
}
// resetez vectorul vizitat pentru al doilea dfs
for(int i = 1; i <= n; i ++){
vizitat[i] = false;
}
// parcurg vectorul in ordine inversa
for(int i = (int)ordine.size() - 1; i >= 0; i--){
int nod = ordine[i]; // retin nodul curent
if(!vizitat[nod]){ // daca nu a mai fost vizitat/ nu mai apare intr-o alta componenta
componenta.clear(); // construiesc o componenta noua
dfs2(nod); // si incep dfs-ul pe graful invers
// dupa ce se termina dfs-ul in solutie adaug componenta rezultat
solutie.push_back(componenta);
}
}
fout << solutie.size() << '\n'; // afisez nr de componente tare conexe
// si care sunt nodurile din fiecare componenta
for(auto comp : solutie){
for(int nod : comp){
fout << nod << " ";
}
fout << '\n';
}
return 0;
}