分数: 400 点
问题陈述
在序列中 P 是以下排列 (1, 2, \dots, N) 并满足以下条件,找到字典顺序最小的序列。
- 对于每个 i = 1, \dots, M, A_i 出现早于 B_i in P.
如果没有这样的 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 满足条件。