AT_abc291_e [ABC291E] Find Permutation

题目描述

有一个长度为 $N$ 的数列 $A=(A_1,\ldots,A_N)$，它是 $1,\ldots,N$ 的一个排列。

你并不知道 $A$ 的具体内容，但你知道 $M$ 个整数对 $(X_i,Y_i)$，满足 $A_{X_i} < A_{Y_i}$。

请判断是否能够唯一确定数列 $A$，如果可以，请输出 $A$。

输入格式

输入通过标准输入按以下格式给出。

$N$ $M$
$X_1$ $Y_1$
$\vdots$
$X_M$ $Y_M$

输出格式

如果能够唯一确定 $A$，第一行输出 Yes，第二行按顺序输出 $A_1,\ldots,A_N$，用空格分隔。

如果不能唯一确定 $A$，仅输出 No。

输入输出样例 #1

输入 #1

3 2
3 1
2 3

输出 #1

Yes
3 1 2

输入输出样例 #2

输入 #2

3 2
3 1
3 2

输出 #2

No

输入输出样例 #3

输入 #3

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

输出 #3

Yes
1 2 3 4

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq X_i, Y_i \leq N$
• 所有输入均为整数
• 保证存在至少一个不矛盾的 $A$

样例解释 1

可以唯一确定 $A=(3,1,2)$。

样例解释 2

$A$ 可能为 $(2,3,1)$ 或 $(3,2,1)$，有两种可能。

由 ChatGPT 4.1 翻译