/ 
Time Limit: 2 sec / Memory Limit: 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.