#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
#include <iterator>
#include <cstdlib>

#define MAX 1000

using namespace std;

class Graph {

private:
	vector<int> *adjList;
	int nr_noduri;
	int nr_conexe;
public:
	Graph(int nr_noduri) {

		this->nr_noduri = nr_noduri;
		adjList = new vector<int>[nr_noduri + 2];
		nr_conexe = 0;
	}
	~Graph() {
		delete[] adjList;
	}

	void addEdge(int u, int v) {

		adjList[u].push_back(v);
	}

	void DFS_iterative(int root_node) {

		bool *visited = new bool[MAX];
		
		for(int i = 0; i < nr_noduri; i++) {
			visited[i] = false;
		}
		visited[root_node] = true;
		stack<int> S;
		S.push(root_node);
		int node;
		vector<int>::iterator it;

		cout << "DFS: ";
		while(!S.empty()) {
		    
			node = S.top();
			S.pop();
			nr_conexe++;
			cout << node << " ";
			if(visited[node] == false) {
				visited[node] = true;
			}
				for(it = adjList[node].begin(); it != adjList[node].end(); ++it) {
					S.push(*it);
				}
	
		cout << endl;
			
			}
	}

	int getNrConexe() {
		return this->nr_conexe;
	}
	
};


int main(int argc, char const *argv[])
{
	FILE *f, *fwr;

	fwr = fopen("dfs.out", "w");

	if((f = fopen("dfs.in", "r")) == NULL) {
		fprintf(stderr, "Can't open file\n");
		return 0;
	}

	int N, M, x ,y, root_node;

	fscanf(f, "%d %d", &N, &M);

	Graph g(N);

	for(int i = 0; i < M; i++) {

		fscanf(f, "%d %d", &x, &y);
		g.addEdge(x,y);
	}
	root_node = 1;
	g.DFS_iterative(root_node);

	printf("Nr de componente conexe: %d\n", g.getNrConexe() );
	fprintf(fwr, "%d", g.getNrConexe());
	fclose(f);
	fclose(fwr);

	return 0;
}