11552: 【原1552】晓敏的全序集

题目

题目描述

author: yzh119 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1552

Description

晓敏定义了一个\(n\)个数上的全序，和\(q\)个关于这个全序的信息:i j代表\(i<j\)。

晓敏希望能得到一个可能的全序，如果有多个可能的全序，晓敏喜欢字典序（正常的字典序）最小的那个。

如果不存在可能的全序，那么输出第几个条件开始就出现了矛盾。

Input Format

第一行两个整数\(n\)和\(q\)。

第二行\(n\)个数代表这\(n\)个整数。

第三行到第\(q + 2\)行，每行两个整数i j代表\(i<j\)。

Output Format

共一行，一个整数\(k\)，代表从第\(k\)个条件开始出现了矛盾，或者\(n\)个整数，代表这个全序下这\(n\)个整数从小到大排列的结果。

Sample Input

5 8
1 2 3 4 5
1 3
2 4
3 5
5 4
3 2
1 5
2 1
3 4

Sample Output

7

Sample Input

4 3
1 9 2 6
9 2
2 1
1 6

Sample Output

9 2 1 6

Limits

对于\(80\%\)的数据，这\(n\)个数为\(1,2,\cdots, n\)。

对于\(80\%\)的数据，不存在可能的全序。

对于\(100\%\)的数据，\(n\leq 10^5, q\leq 2 * 10^5\)。

对于\(30\%\)的数据，\(n\leq 5000, q\leq 5000\)。

所有的数均不超过int范围。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！