#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <utility>
#include <vector>
//using int = unsigned int;
class Graf {
public:
std::vector<std::vector<int>> listaDeAdiacenta;
std::vector<int> gradeInterioare;
Graf(std::vector<std::pair<int, int>> const &muchii,
const int numarMuchii) {
listaDeAdiacenta.resize(numarMuchii + 1);
gradeInterioare = std::vector<int>{0};
gradeInterioare.resize(numarMuchii + 1);
std::fill(gradeInterioare.begin(), gradeInterioare.end(), 0);
for (auto &muchie : muchii) {
listaDeAdiacenta[muchie.first].push_back(muchie.second);
gradeInterioare[muchie.second]++;
}
}
void sortareTopologica(const int numarMuchii,
std::vector<int> &listaFinala) {
std::vector<int> gradeInt = gradeInterioare;
std::vector<int> S {0};
for (int muchie = 0; muchie < numarMuchii; muchie++) {
if (gradeInt[muchie] != 0)
S.push_back(muchie);
}
while (!S.empty()) {
int nodCoada = S.back();
S.pop_back();
listaFinala.push_back(nodCoada);
for (auto it = this->listaDeAdiacenta[nodCoada].begin();
it != this->listaDeAdiacenta[nodCoada].end(); it++) {
gradeInt[*it] -= 1;
if (gradeInt[*it] != 0)
S.push_back(*it);
}
}
}
};
int main() {
std::ifstream inFile;
inFile.open("sortaret.in", std::ios::in);
if (inFile.is_open()) {
int N, M;
inFile >> N >> M;
std::vector<std::pair<int, int>> muchii;
for (size_t arc = 0; arc < M; arc++) {
int x, y;
inFile >> x >> y;
muchii.push_back(std::make_pair(x - 1, y - 1));
}
Graf graf(muchii, N);
std::vector<int> listaFinala;
std::ofstream outFile;
outFile.open("sortaret.out", std::ios::out);
if (outFile.is_open()) {
graf.sortareTopologica(N, listaFinala);
std::reverse(listaFinala.begin(), listaFinala.end());
for (auto nod : listaFinala)
outFile << nod + 1 << " ";
outFile.close();
} else {
std::cout << "Nu s-a putut scrie in fisier!" << std::endl;
}
} else {
std::cout << "Nu am putut deschide fisierul!" << std::endl;
}
inFile.close();
return 0;
}