Score : $500$ points

问题描述

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

虽然你并不知道序列 $A$，但你知道对于 $M$ 对整数 $(X_i,Y_i)$，有 $A_{X_i}<A_{Y_i}$ 成立。

能否唯一确定序列 $A$？如果可以，请找出序列 $A$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a length-$N$ sequence $A=(A_1,\ldots,A_N)$ that is a permutation of $1,\ldots,N$.

While you do not know $A$, you know that $A_{X_i}<A_{Y_i}$ for $M$ pairs of integers $(X_i,Y_i)$.

Can $A$ be uniquely determined? If it is possible, find $A$.

Constraints

• $2 \leq N \leq 2\times 10^5$
• $1 \leq M \leq 2\times 10^5$
• $1\leq X_i,Y_i \leq N$
• All values in the input are integers.
• There is an $A$ consistent with the input.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$X_1$ $Y_1$

$\vdots$

$X_M$ $Y_M$

Output

If $A$ can be uniquely determined, print Yes in the first line. Then, print $A_1,\ldots,A_N$ in the second line, separated by spaces.

If $A$ cannot be uniquely determined, just print No.

Sample Input 1

3 2
3 1
2 3

Sample Output 1

Yes
3 1 2

We can uniquely determine that $A=(3,1,2)$.

Sample Input 2

3 2
3 1
3 2

Sample Output 2

No

Two sequences $(2,3,1)$ and $(3,2,1)$ can be $A$.

Sample Input 3

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

Sample Output 3

Yes
1 2 3 4

update @ 2024/3/10 12:09:00