← 返回题目列表

AtCoder · abc223_d

G. 限制排列

中文机器翻译题面 查看原题

分数: 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 满足条件。