E - Find Permutation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

1,\ldots,N の並び替えである長さ N の数列 A=(A_1,\ldots,A_N) があります。

あなたは A を知りませんが、M 個の整数の組 (X_i,Y_i) について、A_{X_i}<A_{Y_i} が成り立つことを知っています。

A を一意に特定できるかどうか判定し、できるなら A を求めてください。

制約

  • 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 が存在する

入力

入力は以下の形式で標準入力から与えられる。

N M
X_1 Y_1
\vdots
X_M Y_M

出力

A を一意に特定できるとき、1行目に Yes と出力し、2行目に A_1,\ldots,A_N をこの順に空白区切りで出力せよ。

A を一意に特定できないとき、No とのみ出力せよ。

入力例 1

3 2
3 1
2 3

出力例 1

Yes
3 1 2

A=(3,1,2) であると一意に特定できます。

入力例 2

3 2
3 1
3 2

出力例 2

No

A として (2,3,1),(3,2,1) の 2 通りが考えられます。

入力例 3

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

出力例 3

Yes
1 2 3 4

Score : 500 points

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