题目描述

给定一个序列 $P$，其中 $P$ 是由 $(1, 2, \\dots, N)$ 的排列组合构成，并满足以下条件，找到字典序最小的序列。

• 对于每个 $i = 1, \\dots, M$，$A_i$ 在序列 $P$ 中出现在 $B_i$ 之前。

如果不存在这样的 $P$，则输出 -1。

约束条件

• $2 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq M \\leq 2 \\times 10^5$
• $1 \\leq A_i, B_i \\leq N$
• $A_i \\neq B_i$
• 输入中的所有值都是整数。

输入

从标准输入读入输入数据，数据格式如下:

$N$ $M$ $A_1$ $B_1$ $\\vdots$ $A_M$ $B_M$

输出

打印答案。

示例输入 1

4 3
2 1
3 4
2 4

示例输出 1

2 1 3 4

满足条件的五个序列 $P$ 为：$(2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1)$。其中字典序最小的序列为 $(2, 1, 3, 4)$。

示例输入 2

2 3
1 2
1 2
2 1

示例输出 2

-1

没有满足条件的序列 $P$。