D - 限制排列

分数：$400$ 分

问题描述

在满足以下条件的排列 $P$ 中，找到字典序最小的序列。

• 对于每个 $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$

输出

输出答案。

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$。