#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность
color[v] = 1;
for (size_t i = 0; i < graph[v].size(); ++i) {
int to = graph[v][i];
if (color[to] == 0) { //если в вершину не входили ни разу
if (cyclic (to, cycle_st, graph, color)) return true;
}
else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл
cycle_st = to; // и меняем значение индикатора
return true;
}
}
color[v] = 2; //указываем, что в вершину больше ни разу входить не будем
return false;
}
void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
used[v] = true; //указываем, что использовали данную вершину
for (int i=0; i < graph[v].size(); i++) {
int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v
if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё
dfs (to, graph, used, answer);
}
answer.push_back (v+1); // заносим вершину в вектор, хранящий результат
}
void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована
used[i] = false;
for (int i = 0; i < n; i++)
if (!used[i]) //если в ходе предыдущий операций вершина не использовалась
dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину
reverse (answer.begin(), answer.end());
}
int main() {
int n, m; // число вершин и ребер
cin >> n >> m;
int a, b;
vector <int> graph[100001]; // граф
vector <bool> used (n);
vector<int> answer;
vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.
int cycle_st = -1;
for (int i = 0; i < m; i++){
cin >> a >> b;
graph[a-1].push_back(b-1);
}
for (int i = 0; i < n; i++){
if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность
break;
}
if (cycle_st != -1){
cout << "-1";
}
else{
topological_sort(n, graph, used, answer);
for (int i = 0; i < answer.size(); i++)
{
cout << answer[i] << " ";
}
cout << endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpib29sIGN5Y2xpYyAoaW50IHYsIGludCAmY3ljbGVfc3QsIHZlY3RvciA8aW50PiAqZ3JhcGgsIHZlY3RvciA8aW50PiAmY29sb3IgKSB7IC8v0L/RgNC+0LLQtdGA0LrQsCDQs9GA0LDRhNCwINC90LAg0YbQuNC60LvQuNGH0L3QvtGB0YLRjAoJY29sb3Jbdl0gPSAxOwoJZm9yIChzaXplX3QgaSA9IDA7IGkgPCBncmFwaFt2XS5zaXplKCk7ICsraSkgewoJCWludCB0byA9IGdyYXBoW3ZdW2ldOwoJCWlmIChjb2xvclt0b10gPT0gMCkgeyAvL9C10YHQu9C4INCyINCy0LXRgNGI0LjQvdGDINC90LUg0LLRhdC+0LTQuNC70Lgg0L3QuCDRgNCw0LfRgwoJCQlpZiAoY3ljbGljICh0bywgY3ljbGVfc3QsIGdyYXBoLCAgY29sb3IpKSAgcmV0dXJuIHRydWU7CgkJfQoJCWVsc2UgaWYgKGNvbG9yW3RvXSA9PSAxKSB7IC8v0LXRgdC70Lgg0LIg0YPQutCw0LfQsNC90L3Rg9GOINCy0LXRgNGI0LjQvdGDINGA0LDQvdC10LUg0LLRhdC+0LTQuNC70LgsINGC0L4g0LfQvdCw0YfQuNGCLCDRh9GC0L4g0L3QsNC50LTQtdC9INGG0LjQutC7CgkJCWN5Y2xlX3N0ID0gdG87IC8vINC4INC80LXQvdGP0LXQvCDQt9C90LDRh9C10L3QuNC1INC40L3QtNC40LrQsNGC0L7RgNCwIAoJCQlyZXR1cm4gdHJ1ZTsgCgkJfQoJfQoJY29sb3Jbdl0gPSAyOyAvL9GD0LrQsNC30YvQstCw0LXQvCwg0YfRgtC+INCyINCy0LXRgNGI0LjQvdGDINCx0L7Qu9GM0YjQtSDQvdC4INGA0LDQt9GDINCy0YXQvtC00LjRgtGMINC90LUg0LHRg9C00LXQvAoJcmV0dXJuIGZhbHNlOwp9CnZvaWQgZGZzIChpbnQgdiwgdmVjdG9yIDxpbnQ+ICpncmFwaCwgdmVjdG9yPGJvb2w+ICZ1c2VkLCB2ZWN0b3IgPGludD4gJmFuc3dlcikgewoJdXNlZFt2XSA9IHRydWU7IC8v0YPQutCw0LfRi9Cy0LDQtdC8LCDRh9GC0L4g0LjRgdC/0L7Qu9GM0LfQvtCy0LDQu9C4INC00LDQvdC90YPRjiDQstC10YDRiNC40L3RgwoJZm9yIChpbnQgaT0wOyBpIDwgZ3JhcGhbdl0uc2l6ZSgpOyBpKyspIHsKCQlpbnQgdG8gPSBncmFwaFt2XVtpXTsgLy/Qv9C+INGB0L/QuNGB0LrRgyDQv9GA0L7RhdC+0LTQuNC8INC/0L4g0LLRgdC10Lwg0LLQtdGA0YjQuNC90LDQvCwg0Log0LrQvtGC0L7RgNGL0Lwg0LzQvtC20L3QviDQv9GA0L7QudGC0Lgg0L7RgiDQstC10YDRiNC40L3RiyB2CgkJaWYgKCF1c2VkW3RvXSkvL9C4INC10YHQu9C4INCy0LXRgNGI0LjQvdGDINC90LUg0YDQsNGB0YHQvNCw0YLRgNC40LLQsNC70LgsINGC0L4g0L/RgNC40LzQtdC90Y/QtdC8INCw0LvQs9C+0YDQuNGC0Lwg0L/QvtC40YHQutCwINCyINCz0LvRg9Cx0LjQvdGDINC00LvRjyDQvdC10ZEKCQkJZGZzICh0bywgZ3JhcGgsIHVzZWQsIGFuc3dlcik7Cgl9CglhbnN3ZXIucHVzaF9iYWNrICh2KzEpOyAvLyDQt9Cw0L3QvtGB0LjQvCDQstC10YDRiNC40L3RgyDQsiDQstC10LrRgtC+0YAsINGF0YDQsNC90Y/RidC40Lkg0YDQtdC30YPQu9GM0YLQsNGCCn0KIAp2b2lkIHRvcG9sb2dpY2FsX3NvcnQoaW50IG4sIHZlY3RvciA8aW50PiAqZ3JhcGgsIHZlY3Rvcjxib29sPiAmdXNlZCwgdmVjdG9yIDxpbnQ+ICZhbnN3ZXIpIHsKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSAvL9GD0LrQsNC30YvQstCw0LXQvCwg0YfRgtC+INC90Lgg0L7QtNC90LAg0LLQtdGA0YjQuNC90LAg0L3QtSDQsdGL0LvQsCDQuNGB0L/QvtC70YzQt9C+0LLQsNC90LAKCQl1c2VkW2ldID0gZmFsc2U7Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKCQlpZiAoIXVzZWRbaV0pIC8v0LXRgdC70Lgg0LIg0YXQvtC00LUg0L/RgNC10LTRi9C00YPRidC40Lkg0L7Qv9C10YDQsNGG0LjQuSDQstC10YDRiNC40L3QsCDQvdC1INC40YHQv9C+0LvRjNC30L7QstCw0LvQsNGB0YwKCQkJZGZzIChpLCBncmFwaCwgdXNlZCwgYW5zd2VyKTsgLy8g0YLQviDQstGL0LfRi9Cy0LDQtdC8INC00LvRjyDQvdC10ZEg0LDQu9Cz0L7RgNC40YLQvCDQv9C+0LjRgdC60LAg0LIg0LPQu9GD0LHQuNC90YMKCXJldmVyc2UgKGFuc3dlci5iZWdpbigpLCBhbnN3ZXIuZW5kKCkpOwp9CgppbnQgbWFpbigpIHsKCWludCBuLCBtOyAvLyDRh9C40YHQu9C+INCy0LXRgNGI0LjQvSDQuCDRgNC10LHQtdGACgljaW4gPj4gbiA+PiBtOwoJaW50IGEsIGI7Cgl2ZWN0b3IgPGludD4gZ3JhcGhbMTAwMDAxXTsgLy8g0LPRgNCw0YQKCXZlY3RvciA8Ym9vbD4gdXNlZCAobik7Cgl2ZWN0b3I8aW50PiBhbnN3ZXI7Cgl2ZWN0b3I8aW50PiBjb2xvciAobiwwKTsgLy/QvNCw0YHRgdC40LIsINGF0YDQsNC90Y/RidC40Lkg0LrQvtC7LdCy0L4g0L/QvtGB0LXRidC10L3QuNC5INC00LvRjyDQtNCw0L3QvdC+0Lkg0LLQtdGA0YjQuNC90YsuCglpbnQgY3ljbGVfc3QgPSAtMTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbTsgaSsrKXsKCQkJY2luID4+IGEgPj4gYjsKCQkJZ3JhcGhbYS0xXS5wdXNoX2JhY2soYi0xKTsKCQl9Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKyl7CgkJaWYgKGN5Y2xpYyhpLCBjeWNsZV9zdCwgZ3JhcGgsIGNvbG9yKSkgLy/Qv9GA0L7QstC10YDQutCwINCz0YDQsNGE0LAg0L3QsCDQsNGG0LjQutC70LjRh9C90L7RgdGC0YwKCQkJYnJlYWs7Cgl9CglpZiAoY3ljbGVfc3QgIT0gLTEpeyAKCQljb3V0IDw8ICItMSI7Cgl9CgllbHNlewoJCXRvcG9sb2dpY2FsX3NvcnQobiwgZ3JhcGgsIHVzZWQsIGFuc3dlcik7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBhbnN3ZXIuc2l6ZSgpOyBpKyspCgkJewoJCQljb3V0IDw8IGFuc3dlcltpXSA8PCAiICI7IAoJCX0KCQljb3V0IDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==