#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<stack>
#include<algorithm>
#include<set>
using namespace std;
struct muchieCost {
int x, y, cost;
bool operator< (muchieCost other) {
return cost < other.cost;
}
};
struct muchieCapacitate {
int x, y, capacitate;
};
class DisjointSet {
int n;
vector<int> r;
public:
DisjointSet(int n);
void merge(int x, int y);
bool find(int x, int y);
private:
int root(int x);
void mergeRoot(int x, int y);
};
DisjointSet::DisjointSet(int n) {
this->n = n;
r.resize(n + 1);
for (int i = 1; i <= n; i++) {
r[i] = -1;
}
}
void DisjointSet :: merge(int x, int y) {
int rootx = root(x);
int rooty = root(y);
if (rootx != rooty) {
if (r[rootx] < r[rooty]) {
mergeRoot(rootx, rooty);
}
else {
mergeRoot(rooty, rootx);
}
}
}
bool DisjointSet::find(int x, int y) {
return root(x) == root(y);
}
int DisjointSet::root(int x) {
while (r[x] > 0) {
x = r[x];
}
return x;
}
void DisjointSet :: mergeRoot(int x, int y) {
r[x] += r[y];
r[y] = x;
}
class Graf {
int n;
int m;
vector< vector<int> > vecini;
vector< vector< pair<int, int> > > veciniCost;
vector<muchieCost> muchiiCost;
vector<muchieCapacitate> muchiiCapacitate;
vector< vector<int> > adiacenta;
public:
Graf(int n);
Graf(int n, int m, pair<int, int> muchii[], bool directed);
Graf(int n, vector< vector<int> > muchii, bool directed);
Graf(int n, int m, muchieCost muchii[], bool directed);
Graf(int n, vector< vector<int> > adiacenta);
Graf(int n, int m, muchieCapacitate muchii[]);
void adaugaMuchie(int x, int y, bool orientata);
int nrComponenteConexe();
vector<int> bfs(int srs);
vector<int> sortareTopologica();
vector< vector<int> > componenteTareConexe();
vector< vector<int> > componenteBiconexe();
vector< vector<int> > muchiiCritice();
int arborePartialMinim(vector< pair<int, int> > &muchiiArbore);
vector<int> dijkstra(int sursa);
bool bellmanFord(int sursa, vector<int> &distanta);
int diametruArbore();
vector< vector<int> > royFloyd();
int fluxMaxim(const int sursa, const int destinatie);
private:
void dfs(int nod, vector<bool> &viz);
void dfsSortare(int nod, vector<int> &noduriSortate, vector<bool> &viz);
void dfsTareConexe(int nod, vector<int> &level, vector<int> &low, stack<int> &s, vector<bool> &inStack,
vector< vector<int> > &componente, int &cnt, vector<bool> &viz);
void dfsBiconexe(int nod, int tata, vector<int> &level, vector<int> &low, stack<int> &s,
vector< vector<int> > &componente, vector<bool> &viz);
bool bfsFlux(const int sursa, const int destinatie, vector< vector<int> > &flux, vector< vector<int> > &capacitate,
vector<int> &tata, vector<bool> &vizitat);
};
Graf :: Graf(int n) {
vecini.resize(n + 1);
this->n = n;
this->m = 0;
}
Graf :: Graf(int n, int m, pair<int, int> muchii[], bool directed) {
this->n = n;
this->m = m;
vecini.resize(n + 1);
for (int i = 1; i <= m; i++) {
vecini[ muchii[i].first ].push_back(muchii[i].second);
if (!directed) {
vecini[ muchii[i].second ].push_back(muchii[i].first);
}
}
}
Graf :: Graf(int n, vector< vector<int> > muchii, bool directed) {
this->n = n;
this->m = muchii.size();
vecini.resize(n + 1);
for (int i = 0; i < muchii.size(); i++) {
vecini[ muchii[i][0] ].push_back(muchii[i][1]);
if (!directed) {
vecini[ muchii[i][1] ].push_back(muchii[i][0]);
}
}
}
Graf :: Graf(int n, int m, muchieCost muchii[], bool directed) {
this->n = n;
this->m = m;
veciniCost.resize(n + 1);
for (int i = 1; i <= m; i++) {
veciniCost[ muchii[i].x ].push_back(make_pair(muchii[i].y, muchii[i].cost));
if (!directed) {
veciniCost[ muchii[i].y ].push_back(make_pair(muchii[i].x, muchii[i].cost));
muchiiCost.push_back(muchii[i]);
}
}
}
Graf :: Graf(int n, int m, muchieCapacitate muchii[]) {
this->n = n;
this->m = m;
vecini.resize(n + 1);
for (int i = 1; i <= m; i++) {
muchiiCapacitate.push_back(muchii[i]);
vecini[ muchii[i].x ].push_back(muchii[i].y);
vecini[ muchii[i].y ].push_back(muchii[i].x);
}
}
Graf :: Graf (int n, vector< vector<int> > adiacenta) {
this->n = n;
this->adiacenta.resize(n + 1);
for (int i = 1; i <= n; i++) {
this->adiacenta[i].resize(n + 1);
for (int j = 1; j <= n; j++) {
this->adiacenta[i][j] = adiacenta[i][j];
}
}
}
void Graf :: adaugaMuchie(int x, int y, bool orientata) {
vecini[x].push_back(y);
if (!orientata) {
vecini[y].push_back(x);
}
}
int Graf :: nrComponenteConexe() {
vector<bool> viz;
viz.resize(n + 1);
int nr = 0;
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
nr++;
dfs(i, viz);
}
}
return nr;
}
void Graf :: dfs(int nod, vector<bool> &viz) {
viz[nod] = true;
for (int i = 0; i < vecini[nod].size(); i++) {
if (!viz[ vecini[nod][i] ]) {
dfs(vecini[nod][i], viz);
}
}
}
vector<int> Graf :: bfs(int srs) {
vector<int> dist;
dist.resize(n + 1);
for (int i = 1; i <= n; i++) {
dist[i] = -1;
}
queue<int> q;
q.push(srs);
dist[srs] = 0;
while (!q.empty()) {
int nod = q.front();
for (int i = 0; i < vecini[nod].size(); i++) {
int vecin = vecini[nod][i];
if (dist[vecin] == -1) {
dist[vecin] = dist[nod] + 1;
q.push(vecin);
}
}
q.pop();
}
return dist;
}
vector<int> Graf :: sortareTopologica() {
vector<int> noduriSortate;
vector<bool> viz;
viz.resize(n + 1);
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
dfsSortare(i, noduriSortate, viz);
}
}
for (int i = 0; i < n / 2; i++) {
swap(noduriSortate[i], noduriSortate[n - i - 1]);
}
return noduriSortate;
}
void Graf :: dfsSortare(int nod, vector<int> &noduriSortate, vector<bool> &viz) {
viz[nod] = true;
for (int i = 0; i < vecini[nod].size(); i++) {
int vecin = vecini[nod][i];
if (!viz[vecin]) {
dfsSortare(vecin, noduriSortate, viz);
}
}
noduriSortate.push_back(nod);
}
vector< vector<int> > Graf :: componenteTareConexe() {
vector<int> level, low;
vector<bool> inStack, viz;
level.resize(n + 1);
low.resize(n + 1);
inStack.resize(n + 1);
viz.resize(n + 1);
int cnt = 0;
vector< vector<int> > componente;
stack<int> s;
for (int i = 1; i <= n; i++) {
if (!viz[i]) {
dfsTareConexe(i, level, low, s, inStack, componente, cnt, viz);
}
}
return componente;
}
void Graf :: dfsTareConexe(int nod, vector<int> &level, vector<int> &low, stack<int> &s,
vector<bool> &inStack, vector< vector<int> > &componente, int &cnt, vector<bool> &viz) {
viz[nod] = true;
cnt++;
level[nod] = low[nod] = cnt;
s.push(nod);
inStack[nod] = true;
for (int i = 0; i < vecini[nod].size(); i++) {
int vecin = vecini[nod][i];
if (!viz[vecin]) {
dfsTareConexe(vecin, level, low, s, inStack, componente, cnt, viz);
}
if (inStack[vecin]) {
low[nod] = min(low[nod], low[vecin]);
}
}
if (low[nod] == level[nod]) {
vector<int> noduriComponenta;
int nodComponenta;
do {
nodComponenta = s.top();
inStack[nodComponenta] = 0;
s.pop();
noduriComponenta.push_back(nodComponenta);
} while (nodComponenta != nod);
componente.push_back(noduriComponenta);
}
}
vector< vector<int> > Graf :: componenteBiconexe() {
vector<int> level, low;
vector<bool> viz;
level.resize(n + 1);
low.resize(n + 1);
viz.resize(n + 1);
vector< vector<int> > componente;
stack<int> s;
dfsBiconexe(1, 0, level, low, s, componente, viz);
return componente;
}
vector< vector<int> > Graf :: muchiiCritice() {
vector<int> level, low;
vector<bool> viz;
level.resize(n + 1);
low.resize(n + 1);
viz.resize(n + 1);
vector< vector<int> > componente, critice;
stack<int> s;
dfsBiconexe(1, 0, level, low, s, componente, viz);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < vecini[i].size(); j++) {
if (low[ vecini[i][j] ] > level[i]) {
vector<int> muchie;
muchie.push_back(i);
muchie.push_back(vecini[i][j]);
critice.push_back(muchie);
}
}
}
return critice;
}
void Graf:: dfsBiconexe(int nod, int tata, vector<int> &level, vector<int> &low, stack<int> &s,
vector< vector<int> > &componente, vector<bool> &viz) {
viz[nod] = 1;
level[nod] = low[nod] = level[tata] + 1;
s.push(nod);
for (int i = 0; i < vecini[nod].size(); i++) {
int vecin = vecini[nod][i];
if (vecin == tata) {
continue;
}
if (viz[vecin] == 1) {
low[nod] = min(low[nod], level[vecin]);
continue;
}
dfsBiconexe(vecin, nod, level, low, s, componente, viz);
low[nod] = min(low[nod], low[vecin]);
if (low[vecin] >= level[nod]) {
vector<int> componenta;
componenta.push_back(nod);
int nodComponenta;
do{
nodComponenta = s.top();
componenta.push_back(nodComponenta);
s.pop();
} while (nodComponenta != vecin);
componente.push_back(componenta);
}
}
}
int Graf :: arborePartialMinim(vector< pair<int, int> > &muchiiArbore) {
sort(muchiiCost.begin(), muchiiCost.end());
int suma = 0;
DisjointSet *disjointSet = new DisjointSet(n);
for (int i = 0; i < muchiiCost.size(); i++) {
if (!disjointSet->find(muchiiCost[i].x, muchiiCost[i].y)) {
disjointSet->merge(muchiiCost[i].x, muchiiCost[i].y);
suma += muchiiCost[i].cost;
muchiiArbore.push_back(make_pair(muchiiCost[i].x, muchiiCost[i].y));
}
}
return suma;
}
vector<int> Graf :: dijkstra(int sursa) {
vector<int> distanta;
distanta.resize(n + 1);
vector<bool> vizitat;
vizitat.resize(n + 1);
set< pair<int, int> > h;
const int inf = 2000000000;
for (int i = 1; i <= n; i++) {
distanta[i] = inf;
if (i == sursa) {
distanta[i] = 0;
}
h.insert(make_pair(distanta[i], i));
}
while (!h.empty() && h.begin()->first != inf) {
int nod = h.begin()->second;
h.erase(h.begin());
vizitat[nod] = true;
for (int i = 0; i < veciniCost[nod].size(); i++) {
int vecin = veciniCost[nod][i].first;
if (!vizitat[vecin] && distanta[vecin] > distanta[nod] + veciniCost[nod][i].second) {
h.erase(make_pair(distanta[vecin], vecin));
distanta[vecin] = distanta[nod] + veciniCost[nod][i].second;
h.insert(make_pair(distanta[vecin], vecin));
}
}
}
for (int i = 1; i <= n; i++) {
if (distanta[i] == inf) {
distanta[i] = 0;
}
}
return distanta;
}
bool Graf :: bellmanFord(int sursa, vector<int> &distanta) {
vector<int> nrVizitat;
queue<int> coada;
vector<bool> inCoada;
distanta.resize(n + 1);
nrVizitat.resize(n + 1);
inCoada.resize(n + 1);
const int inf = 2000000000;
for (int i = 1; i <= n; i++) {
distanta[i] = inf;
}
distanta[sursa] = 0;
inCoada[sursa] = true;
coada.push(sursa);
while (!coada.empty()) {
int nod = coada.front();
coada.pop();
inCoada[nod] = false;
nrVizitat[nod] ++;
if (nrVizitat[nod] == n) {
return true;
}
for (int i = 0; i < veciniCost[nod].size(); i++) {
int vecin = veciniCost[nod][i].first;
if (distanta[vecin] > distanta[nod] + veciniCost[nod][i].second) {
distanta[vecin] = distanta[nod] + veciniCost[nod][i].second;
if (!inCoada[vecin]) {
inCoada[vecin] = true;
coada.push(vecin);
}
}
}
}
return false;
}
int Graf :: diametruArbore() {
vector<int> distanta = bfs(1);
int nodDepartat = 1;
for (int i = 2; i <= n; i++) {
if (distanta[i] > distanta[nodDepartat]) {
nodDepartat = i;
}
}
distanta = bfs(nodDepartat);
int diametru = 0;
for (int i = 1; i <= n; i++) {
diametru = max(diametru, distanta[i]);
}
return diametru + 1;
}
vector< vector<int> > Graf :: royFloyd() {
vector< vector<int> > distanta(n + 1);
for (int i = 1; i <= n; i++) {
distanta[i].resize(n + 1);
for (int j = 1; j <= n; j++) {
distanta[i][j] = adiacenta[i][j];
}
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i != k && j != k && i != j && distanta[i][k] != 0 && distanta[k][j] != 0 &&
(distanta[i][k] + distanta[k][j] < distanta[i][j] || distanta[i][j] == 0)){
distanta[i][j] = distanta[i][k] + distanta[k][j];
}
}
}
}
return distanta;
}
bool Graf :: bfsFlux(const int sursa, const int destinatie, vector< vector<int> > &flux, vector< vector<int> > &capacitate,
vector<int> &tata, vector<bool> &vizitat) {
queue<int> coada;
vizitat.resize(n + 1);
tata.resize(n + 1);
for (int i = 1; i <= n; i++) {
vizitat[i] = false;
}
vizitat[sursa] = true;
coada.push(sursa);
tata[sursa] = 0;
while (!coada.empty()) {
int nod = coada.front();
coada.pop();
for(int i = 0; i < vecini[nod].size(); i++){
int vecin = vecini[nod][i];
if(!vizitat[vecin] && flux[nod][vecin] < capacitate[nod][vecin]){
vizitat[vecin] = true;
coada.push(vecin);
tata[vecin] = nod;
}
}
}
return vizitat[destinatie];
}
int Graf :: fluxMaxim(const int sursa, const int destinatie) {
vector< vector<int> > flux(n + 1), capacitate(n + 1);
vector<int> tata;
vector<bool> vizitat;
int total = 0;
for (int i = 1; i <= n; i++) {
flux[i].resize(n + 1);
capacitate[i].resize(n + 1);
}
for (int i = 0; i < muchiiCapacitate.size(); i++) {
capacitate[ muchiiCapacitate[i].x ][ muchiiCapacitate[i].y ] = muchiiCapacitate[i].capacitate;
}
while(bfsFlux(sursa, destinatie, flux, capacitate, tata, vizitat)){
for(int i = 0; i < vecini[destinatie].size(); i++){
int vecin = vecini[destinatie][i];
if(vizitat[vecin] && capacitate[vecin][n] > flux[vecin][n]){
int minim = capacitate[ vecin ][destinatie] - flux[ vecin ][destinatie];
int p = vecin;
while(tata[p] > 0){
minim = min(minim, capacitate[ tata[p] ][ p ] - flux[ tata[p] ][ p ]);
p = tata[p];
}
total += minim;
flux[vecin][destinatie] += minim;
flux[destinatie][vecin] -= minim;
p = vecin;
while(tata[p] > 0){
flux[ tata[p] ][p] += minim;
flux[ p][ tata[p] ] -= minim;
p = tata[p];
}
}
}
}
return total;
}
bool havelHakimi(int n, vector<int> g) {
int i, ii, k;
vector<int> fr, fr2;
fr.resize(n);
fr2.resize(n);
for (i = 1; i <= n; i++) {
if (g[i] < 0 || g[i] >= n) {
return false;
}
fr[ g[i] ]++;
}
for (ii = 1; ii <= n; ii++) {
for (i = n - 1; i >= 1; i--) {
if (fr[i] > 0) {
k = i;
break;
}
}
if (i == 0) {
return true;
}
fr[k]--;
for (; i >= 1; i--) {
if (fr[i] < k) {
k -= fr[i];
fr2[i - 1] = fr[i];
}
else {
fr2[i - 1] = k;
fr2[i] += fr[i] - k;
k = 0;
break;
}
}
for (i = i - 1; i >= 0; i--) {
fr2[i] += fr[i];
}
if (k > 0) {
return false;
}
for (i = 0; i < n; i++) {
fr[i] = fr2[i];
fr2[i] = 0;
}
}
}
int n, m;
pair<int, int> muchii[2000005];
ifstream fin ("ctc.in");
ofstream fout("ctc.out");
int main() {
fin>> n >> m;
for (int i = 1; i <= m; i++) {
fin>> muchii[i].first >> muchii[i].second;
}
Graf* graf = new Graf(n, m, muchii, true);
vector< vector<int> > componente = graf -> componenteTareConexe();
fout<< componente.size() <<"\n";
for (int i = 0; i < componente.size(); i++) {
for (int j = 0; j < componente[i].size(); j++) {
fout<< componente[i][j] <<" ";
}
fout<<"\n";
}
}