E - lt and le Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

1 以上 N 以下の整数からなる長さ N の整数列 A であって、次の Q 個の条件をすべて満たすものが存在するか判定し、存在する場合 1 つ求めてください。

i 番目 (1\le i\le Q) の条件は整数の 3 つ組 (t _ i,u _ i,v _ i) で与えられ、以下のように定義されます。

  • t _ i=0 のとき、A _ {u _ i}\le A _ {v _ i}
  • t _ i=1 のとき、A _ {u _ i}\lt A _ {v _ i}

すべての条件を満たす列が複数存在するときは、どれを出力しても構いません。

制約

  • 1\le N\le2\times10 ^ 5
  • 1\le Q\le2\times10 ^ 5
  • t _ i\in\lbrace0,1\rbrace\ (1\le i\le Q)
  • 1\le u _ i\le N\ (1\le i\le Q)
  • 1\le v _ i\le N\ (1\le i\le Q)
  • 入力はすべて整数

入力

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

N Q
t _ 1 u _ 1 v _ 1
t _ 2 u _ 2 v _ 2
\vdots
t _ Q u _ Q v _ Q

出力

1 行目には、条件を満たす整数列が存在すれば Yes 、そうでなければ No を出力せよ。 1 行目に Yes を出力したとき、2 行目には条件を満たす整数列を 1 つ選び、その要素を空白を区切りとして出力せよ。 すべての条件を満たす列が複数存在するときは、どれを選んでも構わない。

入力例 1

7 8
0 1 4
0 2 6
0 3 2
1 3 5
0 4 1
0 4 3
1 5 7
0 6 7

出力例 1

Yes
1 4 2 1 3 5 6

A=(1,4,2,1,3,5,6) とすると、これは 1 以上 7 以下の整数からなる長さ 7 の整数列です。 ここで、例えば 1 番目の条件 A _ 1\le A _ 4 は 1\le 1 なので成り立っています。 他の 7 個の条件も成り立つため、A=(1,4,2,1,3,5,6) に対応する出力は正答とみなされます。

他にも、A=(1,1,1,1,2,2,3) や A=(3,5,4,3,6,7,7) なども条件を満たすため、これらを出力しても正答とみなされます。

入力例 2

1 1
1 1 1

出力例 2

No

A _ 1\lt A _ 1 が成り立つような整数列 A は存在しません。

入力例 3

15 20
0 9 8
1 6 1
0 6 8
0 11 1
0 4 2
1 11 12
0 4 14
1 10 1
0 12 12
1 7 12
1 13 1
1 5 9
1 10 14
1 14 1
1 8 12
0 10 12
1 4 15
1 3 9
0 5 14
0 10 2

出力例 3

Yes
15 14 10 7 6 5 4 12 11 3 2 13 1 9 8

Score : 475 points

Problem Statement

Determine whether there exists an integer sequence A of length N consisting of integers between 1 and N, inclusive, that satisfies all of the following Q conditions, and if it exists, find one.

The i-th condition (1\le i\le Q) is given by a triple of integers (t _ i,u _ i,v _ i), and is defined as follows.

  • If t _ i=0: A _ {u _ i}\le A _ {v _ i}
  • If t _ i=1: A _ {u _ i}\lt A _ {v _ i}

If there are multiple sequences satisfying all conditions, you may output any of them.

Constraints

  • 1\le N\le2\times10 ^ 5
  • 1\le Q\le2\times10 ^ 5
  • t _ i\in\lbrace0,1\rbrace\ (1\le i\le Q)
  • 1\le u _ i\le N\ (1\le i\le Q)
  • 1\le v _ i\le N\ (1\le i\le Q)
  • All input values are integers.

Input

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

N Q
t _ 1 u _ 1 v _ 1
t _ 2 u _ 2 v _ 2
\vdots
t _ Q u _ Q v _ Q

Output

On the first line, output Yes if an integer sequence satisfying the conditions exists, and No otherwise. If you output Yes on the first line, choose one integer sequence satisfying the conditions and output its elements, separated by spaces, on the second line. If there are multiple sequences satisfying all conditions, you may choose any of them.

Sample Input 1

7 8
0 1 4
0 2 6
0 3 2
1 3 5
0 4 1
0 4 3
1 5 7
0 6 7

Sample Output 1

Yes
1 4 2 1 3 5 6

Let A=(1,4,2,1,3,5,6); this is an integer sequence of length 7 consisting of integers between 1 and 7, inclusive. Here, for example, the first condition A _ 1\le A _ 4 holds since 1\le 1. The other seven conditions also hold, so the output corresponding to A=(1,4,2,1,3,5,6) is considered correct.

Additionally, A=(1,1,1,1,2,2,3), A=(3,5,4,3,6,7,7), and others also satisfy the conditions, so outputting these is also considered correct.

Sample Input 2

1 1
1 1 1

Sample Output 2

No

There is no integer sequence A such that A _ 1\lt A _ 1 holds.

Sample Input 3

15 20
0 9 8
1 6 1
0 6 8
0 11 1
0 4 2
1 11 12
0 4 14
1 10 1
0 12 12
1 7 12
1 13 1
1 5 9
1 10 14
1 14 1
1 8 12
0 10 12
1 4 15
1 3 9
0 5 14
0 10 2

Sample Output 3

Yes
15 14 10 7 6 5 4 12 11 3 2 13 1 9 8