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$。

3 2
3 1
2 3

Yes
3 1 2

3 2
3 1
3 2

No

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

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$。我们可以唯一确定 $A=(3,1,2)$。
两个序列 $(2,3,1)$ 和 $(3,2,1)$ 都可能是 $A$。

标签: AtCoder|abc291E

来源

AtCoder|abc291E