#include <iostream>
#include <vector>
#include <list>
using namespace std;

// predstavimao granu grafa
struct Edge {
	int src, dest;
};

// klasa kojom predsavljamo graf
class Graph
{
public:

	// listu susedstva realizujemo kao vektor vektora
	vector<vector<int>> adjList;

	// belezimo ulazne stepene cvorova u vektoru
	vector<int> indegree;

	// konstruktor grafa
	Graph(vector<Edge> const &edges, int N)
	{
		// priprema liste susedstva za prijem  N elemenata koji su  vector<int>
		adjList.resize(N);

		// priprema za cuvanje ulaznih stepena za N cvorova
		indegree.resize(N);

		// dodajemo grane DAG-u
		for (auto &edge: edges) {
			adjList[edge.src].push_back(edge.dest);

			// uvecavamo ulazni stepeb cvora za  1
			indegree[edge.dest]++;
		}
	}
};

// stampanje rezultata, tj elemenata iz  std::list
void printPath(list<int> list)		// bez referenci, nije  const, jer se menja u metodi
{
	while (!list.empty()) {
		cout << list.front() << ' ';
		list.pop_front();
	}
	cout << endl;
}

// rekurzivna funkcija koja za dati DAG nalazi sva topoloska uredjenja
void findAllTopologicalOrders(Graph &graph, auto &path, auto &discovered, int N)
{
	// za svaki cvor
	for (int v = 0; v < N; v++)
	{
		// obradjujemo samo cvor v ciji je ulazni steoen 0
		// i koji nije jos numerisan u top.sortu
		if (graph.indegree[v] == 0 && !discovered[v])
		{
			// za svaki cvor  u koji je sused cvora  v, smanjujemo ulazni stepen za 1
			for (int u: graph.adjList[v]) {
				graph.indegree[u]--;
			}

			// ukljuci tekuci cvor u top.redosled i obelezi da je numerisan u top.sort-u
			path.push_back(v);
			discovered[v] = true;

			// rekurzivni poziv
			findAllTopologicalOrders(graph, path, discovered, N);

			// backtrack: za tekuci cvor v, resetujemo ulazne stepene suseda
			for (int u: graph.adjList[v]) {
				graph.indegree[u]++;
			}

			// backtrack: ukolimo tekuci cvor v iz putanje
			// i oznacimo da nije numerisan u top.sort-u
			path.pop_back();
			discovered[v] = false;
		}
	}

	// stampamo topoloski redosled ako je u konacno resenje tj. putanju
	// uvrsteno svih N cvorova
	if (path.size() == N) {
		printPath(path);
	}
}

// stampati sva topoloska uredjenja za dati  DAG
void printAllTopologicalOrders(Graph &graph)
{
	// N: koliko ima cvorova u grafu
	int N = graph.adjList.size();

	// pomocni vektor bool vrednosti koji evidentira da li je cvoru dodeljena
	// numeracija u top.sortiranju
	vector<bool> discovered(N);

	// lista koja cuva topolosko uredjenje
	list<int> path;

	// poziv rekurzivne metode koja nalazi sva topoloska uredjenja i stampa ih
	findAllTopologicalOrders(graph, path, discovered, N);
}

int main()
{
	// vektor grana
	vector<Edge> edges =
	{
		{0, 6}, {1, 2}, {1, 4}, {1, 6}, {3, 0},
		{3, 4}, {5, 1}, {7, 0}, {7, 1}
	};

	// broj cvorova u grafu
	int N = 8;

	// konstruktor grafa za dati vektor grana i dati broj cvorova
	Graph graph(edges, N);

	// stampanje svih topoloskih redosleda
	printAllTopologicalOrders(graph);

	return 0;
}