AT_abc223_d [ABC223D] Restricted Permutation

题目描述

请在所有由 $(1, 2, \dots, N)$ 重新排列得到的数列 $P$ 中，找到满足以下条件的字典序最小的一个：

• 对于 $i = 1, \dots, M$，在 $P$ 中 $A_i$ 必须出现在 $B_i$ 之前。

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

输入格式

输入以如下格式从标准输入读入。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4 3
2 1
3 4
2 4

输出 #1

2 1 3 4

输入输出样例 #2

输入 #2

2 3
1 2
1 2
2 1

输出 #2

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

样例解释 1

满足条件的 $P$ 有 $(2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1)$ 共 $5$ 个。其中字典序最小的是 $(2, 1, 3, 4)$。

样例解释 2

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

由 ChatGPT 4.1 翻译