生日宴会

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 87 总提交人数: 106

题目

知识点:拓扑排序,优先队列

贝克兰德的富商道恩.唐泰斯将要举办他的生日宴会,他将要邀请n个客人。现在他面临一个问题,安排客人的到场顺序。

在贝克兰德的社交礼仪中,一场宴会的客人总是一个接一个地到达,也就是说,没有两个客人可以在同一时间到达。到达顺序也有一定的限制,大佬应该在小弟全部到场后再到,丈夫应该在妻子之前入场等等。

满足礼仪的顺序有多种,但是因为不同的客人,道恩对他们的熟悉度程度不同,他想要在满足礼仪的情况下,使得他熟悉的人先到场。

现在,道恩对客人按照熟悉程度进行编号1-n,其中1号他最熟悉。然后客人之间有m个到场顺序限制。现在请你生成一个排序,使得在满足到场限制的条件下,使得1号尽可能早的入场,然后2号,3号……以此类推

输入

第一行两个正整数n,m($1\le n\le 10^5,0\le m\le 2\times10^5$)

接下来m行,每行两个整数x,y,表示x应该比y先到 ($1\le x,y\le n$)

输出

一行,n个人的排序,保证有解

输入样例

3 1
3 1

输出样例

3 1 2 

输入样例

5 6
2 1
5 2
4 1
5 4
3 1
5 3

输出样例

5 2 3 4 1 

相关推荐