/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正整数 N, M が与えられます．各 j=1,2,\ldots,M に対して，1\leq L_j\leq R_j\leq N を満たす整数組 (L_j,R_j) が与えられます．
長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) であって，すべての j=1,2,\ldots,M に対して次の条件を満たすものを考えます．
- A_{L_j},A_{L_j+1},\ldots,A_{R_j} はすべて相異なる．
このような正整数列 A は必ず存在することが証明できます．条件を満たす正整数列 A のうち，\max(A_1,A_2,\ldots,A_N) の値が最小となるものを 1 つ出力してください．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 1\leq T\leq 10^5
- 1\leq N\leq 2\times 10^5
- 1\leq M\leq 2\times 10^5
- 1\leq L_j \leq R_j\leq N (1\leq j\leq M)
- 入力される値はすべて整数．
- すべてのテストケースにわたる N の総和は 2\times 10^5 以下．
- すべてのテストケースにわたる M の総和は 2\times 10^5 以下．
入力
入力は以下の形式で標準入力から与えられます．
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられます．
N M L_1 R_1 L_2 R_2 \vdots L_M R_M
出力
テストケースごとに 1 行出力してください．各テストケースについて，条件を満たす正整数列 A のうち，\max(A_1,A_2,\ldots,A_N) の値が最小となるものについて，その要素を空白区切りで出力してください．
A_1 A_2 \ldots A_N
そのような A が複数存在する場合には，そのどれを出力しても正解となります．
入力例 1
2 5 1 1 5 5 3 1 2 2 3 3 5
出力例 1
1 2 3 4 5 3 1 2 1 3
1 番目のテストケースについて，出力が条件を満たすことは，次のように確かめられます．
- A_1, A_2, A_3, A_4, A_5 は 1, 2, 3, 4, 5 であり，これらは相異なります．
この場合 \max(A_1,A_2,\ldots,A_N) = 5 であり，これが条件を満たす正整数列に対する最小値となります．
2 番目のテストケースについて，出力が条件を満たすことは，次のように確かめられます．
- A_1, A_2 は 3, 1 であり，これらは相異なります．
- A_2, A_3 は 1, 2 であり，これらは相異なります．
- A_3, A_4, A_5 は 2, 1, 3 であり，これらは相異なります．
この場合 \max(A_1,A_2,\ldots,A_N) = 3 であり，これが条件を満たす正整数列に対する最小値となります．
Score : 300 points
Problem Statement
You are given positive integers N and M. For each j = 1, 2, \ldots, M, you are given a pair of integers (L_j, R_j) satisfying 1\leq L_j\leq R_j\leq N.
Consider a length-N positive integer sequence A = (A_1, A_2, \ldots, A_N) satisfying the following condition for all j = 1, 2, \ldots, M:
- A_{L_j}, A_{L_j+1}, \ldots, A_{R_j} are all distinct.
It can be proved that such a positive integer sequence A always exists. Among all positive integer sequences A satisfying the condition, output one that minimizes the value of \max(A_1, A_2, \ldots, A_N).
T test cases are given; solve each of them.
Constraints
- 1\leq T\leq 10^5
- 1\leq N\leq 2\times 10^5
- 1\leq M\leq 2\times 10^5
- 1\leq L_j \leq R_j\leq N (1\leq j\leq M)
- All input values are integers.
- The sum of N over all test cases is at most 2\times 10^5.
- The sum of M over all test cases is at most 2\times 10^5.
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 L_2 R_2 \vdots L_M R_M
Output
Output one line per test case. For each test case, output the elements, space-separated, of a positive integer sequence A satisfying the condition that minimizes \max(A_1, A_2, \ldots, A_N).
A_1 A_2 \ldots A_N
If multiple such A exist, any of them will be accepted.
Sample Input 1
2 5 1 1 5 5 3 1 2 2 3 3 5
Sample Output 1
1 2 3 4 5 3 1 2 1 3
For the first test case, the output can be verified to satisfy the condition as follows:
- A_1, A_2, A_3, A_4, A_5 are 1, 2, 3, 4, 5, which are all distinct.
In this case, \max(A_1, A_2, \ldots, A_N) = 5, which is the minimum value for a positive integer sequence satisfying the condition.
For the second test case, the output can be verified to satisfy the condition as follows:
- A_1, A_2 are 3, 1, which are all distinct.
- A_2, A_3 are 1, 2, which are all distinct.
- A_3, A_4, A_5 are 2, 1, 3, which are all distinct.
In this case, \max(A_1, A_2, \ldots, A_N) = 3, which is the minimum value for a positive integer sequence satisfying the condition.