← 返回题目列表

Codeforces · 412/D

D. 颁奖

中文机器翻译题面 查看原题

R1 公司的员工经常在一起度过时光:他们看足球,他们去露营,他们解决比赛。所以,有时有人为别人付钱也没什么大不了的。

今天是发放金钱奖励的日子。 R1公司CEO将一一邀请员工到他的办公室,奖励每一位员工这个月的辛勤工作。首席执行官知道谁欠谁的钱。而且他也明白,如果他邀请x人到他的办公室接受奖励,然后立即邀请借给x人一些钱的y人,那么他们就可以见面。当然,在这种情况下,x人从全新的金钱奖励中获得的快乐就会少很多。因此,R1 CEO 决定按照这样的顺序邀请员工,以确保任何一对相继邀请的员工都不会出现上述情况。

然而,公司员工很多,CEO的时间并不多。因此,任务已分配给您。考虑到所有员工之间的债务关系,确定应按什么顺序邀请他们到 R1 公司 CEO 的办公室,或者确定所描述的顺序不存在。

输入

第一行包含空格分隔的整数 n 和 m $$(2\leq n\leq3\cdot10^{4};1\leq m\leq min(10^{5},\frac{n(n-1)}{2}))$$ — R1 中的员工数量和债务关系数量。接下来的 m 行每行包含两个空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi),这些整数表示编号 ai 的人欠编号 bi 的人钱。假设所有员工的编号为 1 到 n。

保证每对人 p, q 在输入数据中最多被提及一次。特别是,输入数据不会同时包含对 p, q 和 q, p。

输出

如果所描述的订单不存在,则打印 -1。否则,打印 n 个不同整数的排列。第一个数字应该表示第一个去首席执行官办公室的人的号码,第二个数字表示第二个去的人,依此类推。

如果有多个正确订单,您可以打印其中任何一个。

示例

输入 #1

2 1
1 2

输出 #1

2 1

输入 #2

3 3
1 2
2 3
3 1

输出 #2

2 1 3