/*
1. 拓扑排序是有图的宽搜很经典的一个应用
2. 一定是针对有向图来说的,拓扑图是指所有的边都是从前指向后的
3. 并非所有有向图都有拓扑序列, 有环的一定没有拓扑序列
4. 可以证明一个有向无环图(拓扑图), 一定存在拓扑序列,
或者说一个无环图,一定存在至少一个入度为0的点
证明:反证法
假设点数为n
随便挑一个点,由于这个点的入度不是0,就可以沿着这个点找到它的上一个点
同理, 也可以找到它的上一个点, 由于每一个点的入度都不是0,因而可以无穷无尽
地一直找下去,当我们找了n+1个点,由抽屉原理,必然存在两个点相同,那么必然存在一个环
抽屉原理
抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,
假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时
也被称为鸽巢原理。它是组合数学中一个重要的原理
5. 入度:一个点有几条边指向;出度:一个点有几条边出去
6. 求拓扑序列的方法
queue<---所有入度为0的店 (所有当前入度为0的点都是可以作为起点)
while(queue不空0){
t<---队头
枚举t的所有出边(eg:t-->j)
删掉t-->j, d[j]--;
if d[j]==0
queue<--- j
}
*/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int h[N],e[N], ne[N], idx; //数组模拟邻接表
int q[N], d[N]; //q数组模拟队列, d数组表示下标对应的点的入度大小
int n,m;
void add(int a,int b){
e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}
bool topsort(){
int hh=0, tt=-1;
for(int i=1;i<=n;i++){ //将所有入度为0的点加入队列中
if(!d[i])
q[++tt] = i;
}
while(hh<=tt){
int t = q[hh++];
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
d[j]--;
if(d[j]==0){
q[++tt] = j;
}
}
}
return tt==n-1;
}
int main(){
cin>>n>>m;
memset(h, -1,sizeof h);
int a, b;
for(int i=0;i<m;i++){
cin>>a>>b;
add(a, b);
d[b]++;
}
if(topsort()){
for(int i=0;i<n;i++) printf("%d ", q[i]); //q数组的数组元素顺序即为一种拓扑排序
}
else puts("-1");
return 0;
}