生成排列(Generate Permutation)

题目描述

小 Z 想要生成一个 $1\sim n$ 的排列，这排列需要满足 $m$ 对限制，其中第 $i$ 对限制为 $[a_i,b_i]$，表示这个排列中 $a_i$ 必须要出现在 $b_i$ 的前面。

• 所谓 $1\sim n$ 的排列，就是 $(1,2,\cdots,n)$ 这些元素交换顺序组成的序列。

如果有多个满足条件的排列，找到字典序最小的；如果不存在满足要求的排列，输出 -1。

• 所谓字典序最小，就是排列中的第一个数要尽可能小，满足第一个数尽可能小的同时，在满足第二个数尽可能小，以此类推。

输入格式

第一行输入两个整数 $n$ 和 $m$。

接下来有 $m$ 行，每行都输入两个整数 $a_i$ 和 $b_i$ 表示一对限制。

输出格式

如果存在满足条件的排列，输出字典序最小的排列；如果不存在直接输出 -1。

样例输入 #1

4 3
2 1
3 4
2 4

样例输出 #1

2 1 3 4

样例输入 #2

2 3
1 2
1 2
2 1

样例输出 #2

-1

数据范围

【样例 1 解释】

满足条件的排列有 $(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 解释】

限制 $(1,2)$ 和 $(2,1)$ 相互矛盾，不存在这样的排列。

【数据范围】

$1\le n \le 2 \times 10^5,1\le m \le 2 \times 10^5,1\le a_i,b_i \le n,a_i \ne b_i$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接