受限排列

题目描述

在所有满足以下条件的 $(1, 2, \dots, N)$ 的排列 $P$ 中，找出字典序最小的排列。

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

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

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出答案。

样例

4 3
2 1
3 4
2 4

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 3
1 2
1 2
2 1

-1

不存在满足条件的排列 $P$。

数据范围

• $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$
• 输入中的所有数值均为整数。