题目
Problem Statement
You are given positive integers ( N ) and ( M ). For each ( j = 1,2,\dots,M ), you are given a pair of integers ( (L_j, R_j) ) satisfying ( 1 \le L_j \le R_j \le N ).
Consider a length-( N ) positive integer sequence ( A = (A_1, A_2, \dots, A_N) ) satisfying the following condition for all ( j = 1,2,\dots,M ):
( A_{L_j}, A_{L_j+1}, \dots, 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, \dots, A_N) ).
( T ) test cases are given; solve each of them.
Constraints
* ( 1 \le T \le 10^5 )
* ( 1 \le N \le 2 \times 10^5 )
* ( 1 \le M \le 2 \times 10^5 )
* ( 1 \le L_j \le R_j \le N ) (for all ( j ))
* 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:
Each test case is given in the following format:
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, \dots, A_N) ).
If multiple such ( A ) exist, any of them will be accepted.
Sample Input 1
Sample Output 1
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, \dots, 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, \dots, A_N) = 3 ), which is the minimum value for a positive integer sequence satisfying the condition.
题目翻译
A - 彩色区间 /
时间限制：2 秒 / 内存限制：1024 MiB
问题描述
给定正整数 ( N ) 和 ( M )。对于每个 ( j = 1, 2, \dots, M )，给出一个整数对 ( (L_j, R_j) )，满足 ( 1 \le L_j \le R_j \le N )。
考虑一个长度为 ( N ) 的正整数序列 ( A = (A_1, A_2, \dots, A_N) )，满足以下条件：
对所有 ( j = 1, 2, \dots, M )，
( A_{L_j}, A_{L_j+1}, \dots, A_{R_j} ) 互不相同。
可以证明，这样的正整数序列 ( A ) 总是存在。在所有满足条件的正整数序列 ( A ) 中，输出一个使得 ( \max(A_1, A_2, \dots, A_N) ) 最小的序列。
共有 ( T ) 个测试用例，请分别求解。
约束条件
* ( 1 \le T \le 10^5 )
* ( 1 \le N \le 2 \times 10^5 )
* ( 1 \le M \le 2 \times 10^5 )
* ( 1 \le L_j \le R_j \le N )（对所有 ( j )）
* 所有输入均为整数
* 所有测试用例的 ( N ) 之和不超过 ( 2 \times 10^5 )
* 所有测试用例的 ( M ) 之和不超过 ( 2 \times 10^5 )
输入格式
输入从标准输入中按以下格式给出：
每个测试用例的格式如下：
输出格式
每个测试用例输出一行。对于每个测试用例，输出满足条件且使得 ( \max(A_1, A_2, \dots, A_N) ) 最小的正整数序列 ( A )，元素之间用空格分隔。
如果存在多个这样的 ( A )，输出任意一个均可。
样例输入1
样例输出1
对于第一个测试用例，输出序列可以验证满足条件：
( A_1, A_2, A_3, A_4, A_5 ) 为 1,2,3,4,5，全部互不相同。
此时 ( \max(A_1, \dots, A_N) = 5 )，这是满足条件的正整数序列中能达到的最小值。
对于第二个测试用例，输出序列可以验证满足条件：
* ( A_1, A_2 ) 为 3,1，互不相同。
* ( A_2, A_3 ) 为 1,2，互不相同。
* ( A_3, A_4, A_5 ) 为 2,1,3，互不相同。
此时 ( \max(A_1, \dots, A_N) = 3 )，这是满足条件的正整数序列中能达到的最小值。
本蒟蒻代码:
问了deepseek根本找不到错.....
