#include <fstream>
#include <list>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
class Graf
{
int nrNoduri;
int nrMuchii;
bool orientat;
vector<vector<int>> listaAdiacenta;
public:
Graf(bool o)
{
nrNoduri = 0;
nrMuchii = 0;
orientat = o;
}
Graf(int n, int m, bool o)
{
nrNoduri = n;
nrMuchii = m;
orientat = o;
}
void citireGraf()
{
int x, y;
vector<int> v;
for (int i = 0; i < nrMuchii; i++)
listaAdiacenta.push_back(v);
if (orientat)
{
for (int i = 0; i < nrMuchii; i++)
{
fin >> x >> y;
listaAdiacenta[x].push_back(y);
}
}
else
{
for (int i = 0; i < nrMuchii; i++)
{
fin >> x >> y;
listaAdiacenta[x].push_back(y);
listaAdiacenta[y].push_back(x);
}
}
}
void afisareGraf()
{
fout << "Lista de adiacenta asociata grafului <G>:\n\n\n";
for (int i = 1; i <= nrNoduri; i++)
{
if (listaAdiacenta[i].size() > 0)
{
fout << i << " : ";
for (int x : listaAdiacenta[i])
fout << x << " ";
fout << "\n\n";
}
}
}
vector<vector<int>> componenteConexe()
{
vector<vector<int>> listaCC;
vector<int> componentaConexa;
vector<bool> vizitat(nrNoduri + 1, false);
for (int i = 1; i <= nrNoduri; i++)
if (!vizitat[i])
{
DFS(i, componentaConexa, vizitat);
listaCC.push_back(componentaConexa);
componentaConexa.clear();
}
return listaCC;
}
vector<vector<int>> componenteTareConexe()
{
vector<vector<int>> listaCTC;
vector<int> discOrder(nrNoduri + 1, 0); // nodul x este al discOrder[x]-lea nod obtinut din parcurgerea DFS
vector<int> lowLink(nrNoduri + 1, 0); // lowLink[x] = min(lowLink[x], discOrder[y]), cu Y conectat la X
vector<bool> onStack(nrNoduri + 1, false);
stack<int> stack; // stiva care valideaza apartenenta unui nod la o componenta conexa
for (int i = 1; i <= nrNoduri; i++)
if (discOrder[i] == 0)
TareConexDFS(i, listaCTC, discOrder, lowLink, stack, onStack);
return listaCTC;
}
void distanteBFS(int nodS)
{
vector<bool> vizitat(nrNoduri + 1, false);
vector<int> distanta(nrNoduri + 1, -1);
BFS(nodS, vizitat, distanta);
for (int i = 1; i <= nrNoduri; i++)
fout << distanta[i] << " ";
}
private:
void DFS(int nodS, vector<int>& componentaConexa, vector<bool>& vizitat)
{
vizitat[nodS] = true;
componentaConexa.push_back(nodS);
for (auto vecin : listaAdiacenta[nodS])
if (!vizitat[vecin])
DFS(vecin, componentaConexa, vizitat);
}
void BFS(int nodS, vector<bool>& vizitat, vector<int>& distanta)
{
queue<int> queue;
queue.push(nodS);
vizitat[nodS] = true;
distanta[nodS] = 0;
while (!queue.empty())
{
int nodCurent = queue.front();
//fout << nodCurent << " ";
queue.pop();
for (auto vecin : listaAdiacenta[nodCurent])
if (!vizitat[vecin])
{
queue.push(vecin);
vizitat[vecin] = true;
distanta[vecin] = distanta[nodCurent] + 1;
}
}
}
void TareConexDFS(int nodS, vector<vector<int>>& listaCTC, vector<int>& discOrder, vector<int>& lowLink, stack<int>& stack, vector<bool>& onStack)
{
static int idCurent = 1;
discOrder[nodS] = lowLink[nodS] = idCurent++;
stack.push(nodS);
onStack[nodS] = true;
for (auto vecin : listaAdiacenta[nodS])
{
if (discOrder[vecin] == 0) // daca nodul nu a fost explorat, pornim DFS din el, iar la revenirea din recursie, il incadram intr-o componenta conexa
{
TareConexDFS(vecin, listaCTC, discOrder, lowLink, stack, onStack);
lowLink[nodS] = min(lowLink[nodS], lowLink[vecin]);
}
else // daca nodul a fost explorat si se afla pe stiva de validare, il incadram intr-o componenta conexa
if (onStack[vecin])
lowLink[nodS] = min(lowLink[nodS], discOrder[vecin]);
}
// daca ID - ul nodului corespunde cu lowLink - value - ul sau, inseamna ca nodul este radacina componentei sale conexe,
if (lowLink[nodS] == discOrder[nodS]) //si putem scoate de pe stiva toate nodurile pana la nodS, deoarece am terminat de explorat componenta respectiva
{
vector<int> componentaConexa;
int top;
do
{
top = stack.top();
stack.pop();
onStack[top] = false;
componentaConexa.push_back(top);
} while (nodS != top);
listaCTC.push_back(componentaConexa);
}
}
};
int main()
{
int n, m, s;
fin >> n >> m;
Graf G(n, m, true);
G.citireGraf();
vector<vector<int>> CTC = G.componenteTareConexe();
fout << CTC.size() << "\n";
for (int i = 0; i < CTC.size(); i++)
{
for (auto x : CTC[i])
fout << x << " ";
fout << "\n";
}
}