/*
 * PA 2010
 * Laborator 7 - Aplicatii DFS
 *
 * Determinarea componentelor tare conexe
 *
 */

#include <cstdio> // daca vreti sa folositi printf, scanf
#include <iostream>
#include <fstream>
#include <vector>               
#include <stack>

using namespace std;

#define min(a, b) ((a) < (b) ? (a) : (b))
 
enum culoare_t {ALB, GRI, NEGRU};
typedef vector<int> *graf_t; 
 
int n, m;
graf_t G; // lista de adiacents
stack<int> S;

// Pentru retinerea solutiei si afisarea ei la sfarsit
vector <vector<int> > sol;
vector<int> crtcomp;

// In plus pentru Kosaraju
culoare_t *cul;
graf_t GT; // Lista de adiacenta a grafului transpus

// In plus pentru Tarjan 
int index = 0;
int *idx, *lowlink;
bool *onstack;

void read_data(const char *filename)
{
	ifstream fin;
	int x, y;
	fin.open(filename);
	fin >> n >> m;
	G = new vector<int>[n];
	GT = new vector<int>[n]; // doar pentru Kosaraju
	for (int i = 0; i < m; i++) {
		fin >> x >> y;
		x--; y--; // indexare de la 0
		G[x].push_back(y);
		GT[y].push_back(x);
	}
}

/* Kosaraju */
void dfs(int v, graf_t lst)
{
	cul[v] = GRI;
	for (int i = 0; i < lst[v].size(); i++) {
		int u = lst[v][i];
    	if (cul[u] == ALB)
			dfs(u, lst);
	}
	cul[v] = NEGRU;
	S.push(v);
}                      

void dfsT(int v, graf_t lst)
{
	cul[v] = GRI;
for (v = 0; v < n; v++)
	// TODO: adaugare nod la noua componenta conexa (afisare)
	
	for (int i = 0; i < lst[v].size(); i++) {
		int u = lst[v][i];
    	if (cul[u] == ALB)
			dfsT(u, lst);
	}
	cul[v] = NEGRU;
}                      

void ctc_kosaraju()
{
	// Alocari memorie
	//cul = new culoar
	//lowlink[v] = min(lowlink[v], lowlink[u])e_t[n];

	// TODO

	// Dezalocari memorie
	delete[] cul;
}

/*tarjan(G, v)
  idx[v]      = index
  lowlink[v] = index
  index = index + 1
  push(S, v)
  pentru (v, u) din E
   daca (idx[u] nu e definit)
         tarjan(G, u)
         lowlink[v] = min(lowlink[v], lowlink[u])
    altfel daca (u e in S)
         lowlink[v] = min(lowlink[v], idx[u])
  daca (lowlink[v] == idx[v])
    // este v radacina unei CTC?
    print "O noua CTC: "
    repeat
      u = pop(S)
      print u
    until (u == v)*/

/* Tarjan */
void tarjan(int v) {
	// TODO
	vector<int>::iterator u;
	int uu;
	
	idx[v] = index;
	lowlink[v] = index;
	index++;
	onstack[v] = true;
	S.push(v);
	
	for (u = G[v].begin(); u != G[v].end(); ++u) {
		if (idx[*u] == -1) {
			tarjan(*u);
			lowlink[v] = min(lowlink[v], lowlink[*u]);
		}
		else if (onstack[*u]) {
			lowlink[v] = min(lowlink[v], idx[*u]);
		}
	}
	
	if (lowlink[v] == idx[v]) {
		sol.push_back(vector<int>());
		do {
			uu = S.top();
			S.pop();
			sol.back().push_back(uu);
		}
		while (uu != v);
	}
}

/*ctc_tarjan(G = (V, E))
  index = 0
  S = stiva vida
  pentru fiecare v din V
    daca (idx[v] nu e definit)      // nu a fost vizitat
      tarjan(G, v)*/

void ctc_tarjan()
{
	int v;

	// Alocari memorie
	idx = new int[n];
	lowlink = new int[n];
	onstack = new bool[n];

	// TODO
	index = 0;
	for (v = 0; v < n; v++) {
		idx[v] = -1;
		lowlink[v] = -1;
		onstack[v] = false;
	}
	
	for (v = 0; v < n; v++) {
		printf("%d ", onstack[v]);
		fflush(stdin);
		if (!onstack[v]) {
			tarjan(v);
		}
	}
	printf("\n");
	
	// Dezalocari memorie
	delete[] idx;
	delete[] lowlink;
	delete[] onstack;
}

// Afiseaza solutia daca a fost retinuta in "sol"
// (+ exemplu folosire iteratori)
void print_sol(const char *filename)
{
	ofstream fout;
	fout.open(filename);
	fout << sol.size() << endl;
	vector<vector<int> >::iterator s;
	for (s = sol.begin(); s != sol.end(); s++) {
		vector<int>::iterator v;
		for (v = s->begin(); v != s->end(); v++)
			fout << *v + 1 << " ";
		fout << endl;
	}
	fout.close();
}

void free_data()
{
	delete[] G;
	delete[] GT; // doar pentru Kosaraju
}

int main(int argc, char *argv[])
{   
    if (argc >= 2)
		read_data(argv[2]);
	else
		read_data("ctc.in");

	// TODO: implementare ctc_kosaraju sau ctc_tarjan
	// ctc_kosaraju();
	ctc_tarjan();
	
	if (argc >= 3)
		print_sol(argv[3]);
	else
		print_sol("ctc.out");

	free_data();

	return 0;
}