#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <stack>

//std::ifstream f("graful.txt");
//std::ofstream g("graful.out");
std::ifstream f("ctc.in");
std::ofstream g("ctc.out");


int start = 0, contor;   // contorul il vom folosi in mai multe probleme;  start va aparea eventual ca nod de start

typedef std::stack< std::pair <int, int > > stackpair;
typedef std::unordered_set< int > multime;
typedef std::vector< std::vector < int > > vector_vectori;

class graf
{
	int nrvf, nrmuchii;
	std::vector<int>* vecini;

public:
	graf(bool orientat);

	int get_nrvf() { return nrvf; }
	void make_edgeList(vector_vectori& solution);
	void verifvecini();

	void BFS();
	void DFS(int nod, bool* viz);
	void cadruDFS();
	void biconexe(int nod, int tata, bool* viz, multime* wayback, stackpair& muchiiviz, vector_vectori& comp_biconexe);
	void cadru_biconexe();
	void tareconexe(int nod, int& freeorder, int* order, int* leastbackorder, bool* pestiva, std::stack<int>& noduriviz, vector_vectori& comp_tareconexe);
	void cadru_tareconexe();
	void mCrits(int nod, int tata, bool* viz, multime* wayback, stackpair& muchiiviz, vector_vectori& connections, vector_vectori& solutia);
	vector_vectori criticalConnections(int n, vector_vectori& connections);

	~graf()
	{
		delete []vecini;
	}
};

graf::graf(bool orientat)
{
	f >> nrvf >> nrmuchii;
	if(start == 1)	// daca avem de citit un nod de start...
		f >> start;

	vecini = new std::vector<int>[nrvf + 1];
	if (orientat == true)
		for (int i = 0; i < nrmuchii; i++)
		{
			int x, y;
			f >> x >> y;
			vecini[x].push_back(y);
		}
	else
		for (int i = 0; i < nrmuchii; i++)
		{
			int x, y;
			f >> x >> y;
			vecini[x].push_back(y);
			vecini[y].push_back(x);
		}
}

void graf::verifvecini()
{
	for (int i = 1; i <= nrvf; i++)
	{
		std::cout << "\n  vecinii lui " << i << " :  ";
		for (unsigned int j = 0; j < vecini[i].size(); j++)
			std::cout << vecini[i][j] << " ";
	}
}

void graf::BFS()
{
	int* dist = new int[nrvf + 1]{ 0 };	// initializam distantele cu 0 (le decrementam ulterior)
	std::queue <int> qBFS;	  // coada pt BFS
	qBFS.push(start);
	dist[start] = 1;

	while (!qBFS.empty())
	{
		const int nod = qBFS.front();
		for (unsigned int i = 0; i < vecini[nod].size(); i++)
		{
			const int nod_urm = vecini[nod][i];
			if (dist[nod_urm] == 0)
			{
				qBFS.push(nod_urm);
				dist[nod_urm] = dist[nod] + 1;
			}
		}

		qBFS.pop();
	}

	for (int i = 1; i <= nrvf; i++)
		g << dist[i] - 1 << " ";

	delete [] dist;
}

void graf::DFS(int nod, bool* viz)
{
	viz[nod] = true;
	for (unsigned int i = 0; i < vecini[nod].size(); i++)
	{
		const int nod_urm = vecini[nod][i];
		if (!viz[nod_urm])
			DFS(nod_urm, viz);
	}
}

void graf::cadruDFS()
{
	contor = 0;
	bool* viz = new bool[nrvf + 1]{ 0 };
	for (int i = 1; i <= nrvf; i++)
		if( ! viz[i] )
		{
			contor++;
			DFS(i, viz);
		}
	g << contor;
	delete[]viz;
}

void graf::biconexe(int nod, int tata, bool* viz, multime* wayback, stackpair& muchiiviz, vector_vectori& comp_biconexe)
{
	viz[nod] = true;

	for (unsigned int i = 0; i < vecini[nod].size(); i++)
	{
		const int nod_urm = vecini[nod][i];

		if (viz[nod_urm]) 
		{
			if (nod_urm != tata and nod_urm != nod) 
			{
				wayback->insert(nod_urm);
				for(unsigned int i = 0; i < vecini[nod_urm].size(); i ++ )
					if (vecini[nod_urm][i] == nod)
					{
						vecini[nod_urm][i] = nod_urm;
						break;
					}
			}
		}
		else
		{
			muchiiviz.push({ nod, nod_urm });
			multime* wayback_fiu = new multime;
			biconexe(nod_urm, nod, viz, wayback_fiu, muchiiviz, comp_biconexe);
			
			wayback_fiu->erase(nod);
			if (wayback_fiu->size() == 0)
			{
				contor++;
				std::vector< int > aux;
				comp_biconexe.push_back(aux);
				while (muchiiviz.top().first != nod)
				{
					comp_biconexe.back().push_back(muchiiviz.top().second);
					muchiiviz.pop();
				}
				comp_biconexe.back().push_back(muchiiviz.top().second);
				comp_biconexe.back().push_back(muchiiviz.top().first);
				muchiiviz.pop();
			}
			else
				wayback->insert(wayback_fiu->begin(), wayback_fiu->end());

			delete wayback_fiu;
		}
	}
}

void graf::cadru_biconexe()
{
	contor = 0;
	vector_vectori comp_biconexe;		// solutia, de forma unui vector cu alti vectori ce reprezinta componentele biconexe
	bool* viz = new bool[nrvf + 1]{ 0 };	// nodurile vizitate deja
	stackpair muchiiviz;							// stiva de muchii vizitate
	multime* setgol = new multime;		// un set "wayback" pe care il pasez fiului pentru a-mi returna caile de intoarcere disponibile
	biconexe(1, -1, viz, setgol, muchiiviz, comp_biconexe);
	delete setgol;
	delete []viz;

	g << contor << "\n";
	for (unsigned int i = 0; i < comp_biconexe.size(); i++)
	{
		for (unsigned int j = 0; j < comp_biconexe[i].size(); j++) {
			g << comp_biconexe[i][j] << " ";
		}
		g << "\n";
	}
}

void graf::tareconexe(int nod, int& freeorder, int* order, int* leastbackorder, bool* pestiva, std::stack<int>& noduriviz, vector_vectori& comp_tareconexe)
{
	order[nod] = freeorder;
	leastbackorder[nod] = freeorder;
	freeorder++;
	noduriviz.push(nod);
	pestiva[nod] = true;

	for (unsigned int i = 0; i < vecini[nod].size(); i++)
	{
		const int nod_urm = vecini[nod][i];

		if (order[nod_urm] == 0)			// nevizitat
		{
			tareconexe(nod_urm, freeorder, order, leastbackorder, pestiva, noduriviz, comp_tareconexe);
			leastbackorder[nod] = std::min( leastbackorder[nod], leastbackorder[nod_urm] );
		}
		else if (pestiva[nod_urm])		// vizitat, dar inca pe stiva
				leastbackorder[nod] = std::min( leastbackorder[nod], order[nod_urm] );
	}

	if (leastbackorder[nod] == order[nod])   //  nodul nu se poate intoarce mai sus de el
	{ 
		contor++;
		std::vector< int > aux;
		comp_tareconexe.push_back(aux);

		int varf = noduriviz.top();
		while (varf != nod)
		{
			noduriviz.pop();
			pestiva[varf] = false;
			comp_tareconexe.back().push_back(varf);

			varf = noduriviz.top();
		}
		noduriviz.pop();
		pestiva[varf] = false;
		comp_tareconexe.back().push_back(varf);
	}
}

void graf::cadru_tareconexe()
{
	contor = 0;
	vector_vectori comp_tareconexe;				// solutia, de forma unui vector cu alti vectori ce reprezinta componentele tareconexe
	std::stack<int> noduriviz;								// stiva de noduri vizitate
	bool* pestiva = new bool[nrvf + 1]{ 0 };
	int* order = new int[nrvf + 1]{ 0 };				// ordinea intrarii pe stiva a nodurilor
	int freeorder = 1;
	int* leastbackorder = new int[nrvf + 1]{ 0 };		// cel mai mic ordin accesibil din urma, de pe stiva

	for (int i = 1; i <= nrvf; i++)
		if (order[i] == 0)		//  nod nevizitat 
			tareconexe(i, freeorder, order, leastbackorder, pestiva, noduriviz, comp_tareconexe);

	g << contor << "\n";
	for (unsigned int i = 0; i < comp_tareconexe.size(); i++)
	{
		for (unsigned int j = 0; j < comp_tareconexe[i].size(); j++)
			g << comp_tareconexe[i][j] << " ";
		g << "\n";
	}

	delete[] leastbackorder, order, pestiva;
}

void graf::make_edgeList(vector_vectori& solution)
{
	std::vector< int > aux;
	solution.push_back(aux);
	for (int i = 1; i <= nrvf; i++)
	{
		std::vector< int > aux;
		solution.push_back(aux);
		for (unsigned int j = 0; j < vecini[i].size(); j++)
			solution.back().push_back(vecini[i][j]);
	}
}

void graf::mCrits(int nod, int tata, bool* viz, multime* wayback, stackpair& muchiiviz, vector_vectori& connections, vector_vectori& solutia)
{
	viz[nod] = true;
	for (unsigned int i = 0; i < connections[nod].size(); i++)
	{
		const int nod_urm = connections[nod][i];
		if (viz[nod_urm])
		{
			if (nod_urm != tata and nod_urm != nod)
			{
				wayback->insert(nod_urm);
				for (unsigned int i = 0; i < connections[nod_urm].size(); i++)
					if (connections[nod_urm][i] == nod)
					{
						connections[nod_urm][i] = nod_urm;
						break;
					}
			}
		}
		else
		{
			muchiiviz.push({ nod, nod_urm });
			multime* wayback_fiu = new multime;
			mCrits(nod_urm, nod, viz, wayback_fiu, muchiiviz, connections, solutia);

			if (wayback_fiu->size() == 0)
			{
				std::vector< int > aux;
				solutia.push_back(aux);
				while (muchiiviz.top().first != nod)
					muchiiviz.pop();

				solutia.back().push_back(muchiiviz.top().first);
				solutia.back().push_back(muchiiviz.top().second);
				muchiiviz.pop();
			}
			else
			{
				wayback_fiu->erase(nod);
				wayback->insert(wayback_fiu->begin(), wayback_fiu->end());
			}

			delete wayback_fiu;
		}
	}
}
std::vector< std::vector< int > > graf::criticalConnections(int n, vector_vectori& connections)
{
	vector_vectori solutia;		// solutia, de forma unui vector cu alti vectori ce reprezinta muchiile critice
	bool* viz = new bool[nrvf + 1]{ 0 };	// nodurile vizitate deja
	stackpair muchiiviz;							// stiva de muchii vizitate
	multime* setgol = new multime;		// un set "wayback" pe care il pasez fiului pentru a-mi returna caile de intoarcere disponibile
	mCrits(1, -1, viz, setgol, muchiiviz, connections, solutia);
	delete setgol, viz;

	return solutia;
}

int main()
{
	start = 0;		// afirmam daca citim si un nod de start;
	//graf g(false);
	//g.cadru_biconexe();
	
	//// muchii critice:
	//vector_vectori* connections = new vector_vectori;
	//g.make_edgeList(*connections);
	//vector_vectori vector_afisare = g.criticalConnections(g.get_nrvf(), *connections);
	//for (int i = 0; i < vector_afisare.size(); i++)
	//	std::cout << vector_afisare[i][0] << " " << vector_afisare[i][1] << "\n";
	//delete connections;

	graf g(true);
	g.cadru_tareconexe();

	return 0;
}