B - Range Record 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 1100 点

問題文

整数 N,M と，整数の 3 つ組 (L_i,R_i,C_i) が M 組与えられます．ここで，1 \leq L_i < R_i \leq N であり，組 (L_i,R_i) は互いに異なります．

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) であって，次の M 個の条件をすべて満たすものが存在するか判定してください．また存在する場合は，そのような順列を 1 つ求めてください．

  • i 番目の条件: L_i \leq j \leq R_i かつ \max(P_{L_i},P_{L_i+1},\ldots,P_j)=P_j を満たす整数 j の個数が，ちょうど C_i 個である．

1 つの入力につき，T ケースを解いてください．

制約

  • 1 \leq T \leq 125000
  • 2 \leq N \leq 100
  • 1 \leq M \leq \dfrac{N(N-1)}{2}
  • 1 \leq L_i \lt R_i \leq N (1 \leq i \leq M)
  • (L_i,R_i) \neq (L_j,R_j) (1 \leq i \lt j \leq M)
  • 1 \leq C_i \leq R_i-L_i+1 (1 \leq i \leq M)
  • T ケースにわたる N^3 の総和は 10^6 以下である．
  • 入力される数値はすべて整数である．

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる．

N M
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_M R_M C_M

出力

各テストケースについて，条件を満たす順列が存在する場合は，1 行目に Yes を出力し，2 行目に条件を満たす順列 P を空白区切りで出力せよ．条件を満たす順列が複数存在する場合は，どれを出力してもよい．

存在しない場合は No を 1 行に出力せよ．

入力例 1

8
4 3
1 4 2
2 4 1
3 4 2
3 3
1 2 2
2 3 2
1 3 2
2 1
1 2 1
2 1
1 2 2
6 5
1 6 3
2 5 3
3 6 2
4 6 1
5 6 2
5 10
1 2 2
1 3 2
1 4 2
1 5 2
2 3 1
2 4 1
2 5 1
3 4 2
3 5 2
4 5 1
3 2
1 3 3
2 3 1
3 2
1 2 1
1 3 2

出力例 1

Yes
2 4 1 3
No
Yes
2 1
Yes
1 2
Yes
2 1 4 6 3 5
Yes
2 5 1 4 3
No
Yes
2 1 3

1 番目のテストケースでは，例えば P=(2,4,1,3) が条件を満たします． 区間 [1,4] では j=1,2，区間 [2,4] では j=2，区間 [3,4] では j=3,4 がそれぞれ条件を満たします．

2 番目のテストケースでは，最初の 2 つの条件から P_1 \lt P_2 \lt P_3 が必要です．このとき区間 [1,3] で条件を満たす j の個数は 3 個となり，3 つ目の条件を満たさないので，そのような順列は存在しません．

Score : 1100 points

Problem Statement

You are given integers N,M and M triples of integers (L_i,R_i,C_i). Here, 1 \leq L_i < R_i \leq N, and the pairs (L_i,R_i) are pairwise distinct.

Determine whether there exists a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) that satisfies all of the following M conditions. If one exists, find one such permutation.

  • The i-th condition: the number of integers j such that L_i \leq j \leq R_i and \max(P_{L_i},P_{L_i+1},\ldots,P_j)=P_j is exactly C_i.

You are given T test cases; solve each of them.

Constraints

  • 1 \leq T \leq 125000
  • 2 \leq N \leq 100
  • 1 \leq M \leq \dfrac{N(N-1)}{2}
  • 1 \leq L_i \lt R_i \leq N (1 \leq i \leq M)
  • (L_i,R_i) \neq (L_j,R_j) (1 \leq i \lt j \leq M)
  • 1 \leq C_i \leq R_i-L_i+1 (1 \leq i \leq M)
  • The sum of N^3 over all test cases in a single input is at most 10^6.
  • All input values are integers.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N M
L_1 R_1 C_1
L_2 R_2 C_2
\vdots
L_M R_M C_M

Output

For each test case, if a permutation satisfying the conditions exists, output Yes on the first line and the elements of such a permutation P, separated by spaces, on the second line. If there are multiple such permutations, any of them will be accepted.

If no such permutation exists, output No on a single line.

Sample Input 1

8
4 3
1 4 2
2 4 1
3 4 2
3 3
1 2 2
2 3 2
1 3 2
2 1
1 2 1
2 1
1 2 2
6 5
1 6 3
2 5 3
3 6 2
4 6 1
5 6 2
5 10
1 2 2
1 3 2
1 4 2
1 5 2
2 3 1
2 4 1
2 5 1
3 4 2
3 5 2
4 5 1
3 2
1 3 3
2 3 1
3 2
1 2 1
1 3 2

Sample Output 1

Yes
2 4 1 3
No
Yes
2 1
Yes
1 2
Yes
2 1 4 6 3 5
Yes
2 5 1 4 3
No
Yes
2 1 3

In the first test case, for example, P=(2,4,1,3) satisfies the conditions. The integers j counted in each condition are j=1,2 for the interval [1,4], j=2 for the interval [2,4], and j=3,4 for the interval [3,4].

In the second test case, the first two conditions require P_1 \lt P_2 \lt P_3. Then, the number of integers j counted for the interval [1,3] is 3, which violates the third condition, so no such permutation exists.