#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
// Deschidem fișierele de intrare și ieșire
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100005;
// g[u] = lista de adiacență a grafului orientat original (x -> y)
// gt[u] = lista de adiacență a grafului transpus / inversat (y -> x)
vector<int> g[NMAX], gt[NMAX];
// stiva = va reține nodurile în ordinea finalizării parcurgerii din primul DFS
// ctc = ctc[i] va conține toate nodurile din componenta tare conexă cu numărul i
vector<int> stiva, ctc[NMAX];
bool viz[NMAX]; // Vector de frecvență pentru a marca nodurile vizitate
int n, m, nr_ctc;
// --- PASUL 1: Primul DFS pe graful original ---
// Scopul este de a adăuga nodurile în "stivă" pe măsură ce terminăm de vizitat toți vecinii lor (postordine)
void dfs1(int u) {
viz[u] = true;
for (int v : g[u]) {
if (!viz[v]) {
dfs1(v);
}
}
stiva.push_back(u); // Adăugăm u în stivă DUPĂ ce am explorat toți vecinii
}
// --- PASUL 2: Al doilea DFS pe graful transpus ---
// Mergem înapoi pe muchiile inversate. Marchează nodurile din aceeași CTC ca nevizitate (viz[u] = false)
void dfs2(int u) {
viz[u] = false; // Demarcăm nodul ca să știm că l-am inclus deja într-o CTC
ctc[nr_ctc].push_back(u); // Adăugăm nodul în componenta curentă
for (int v : gt[u]) {
if (viz[v]) { // Dacă vecinul a fost vizitat în primul DFS și nu a fost procesat încă
dfs2(v);
}
}
}
int main() {
fin >> n >> m;
while (m--) {
int x, y;
fin >> x >> y;
g[x].push_back(y); // Muchia orientată originală: x -> y
gt[y].push_back(x); // Muchia inversată pentru graful transpus: y -> x
}
// 1. Rulăm DFS1 pe graful original pentru a umple stiva cu ordinea de terminare
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
dfs1(i);
}
}
// 2. Parcurgem stiva de la coadă la cap (de la nodul care s-a terminat ultimul)
for (int i = stiva.size() - 1; i >= 0; i--) {
int u = stiva[i];
// Dacă nodul u este încă vizitat (true), înseamnă că nu face parte din nicio CTC creată anterior
if (viz[u]) {
nr_ctc++; // Am găsit o nouă componentă tare conexă
dfs2(u); // Adunăm toate nodurile din această componentă folosind graful transpus
}
}
// 3. Afișăm numărul total de componente tare conexe
fout << nr_ctc << "\n";
// 4. Afișăm nodurile fiecărei componente
for (int i = 1; i <= nr_ctc; i++) {
for (int v : ctc[i]) {
fout << v << " ";
}
fout << "\n";
}
return 0;
}