分数: 300 点
问题陈述
给你正整数 N 和 M。对于每个 j = 1, 2, \ldots, M,给你一对整数 (L_j, R_j) 满意 1\leq L_j\leq R_j\leq N.
考虑长度-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).
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
输出
每个测试用例输出一行。对于每个测试用例,输出正整数序列的以空格分隔的元素 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
对于第一个测试用例,可以验证输出是否满足以下条件:
- A_1, A_2, A_3, A_4, A_5 是 1, 2, 3, 4, 5,它们都是不同的。
在这种情况下, \max(A_1, A_2, \ldots, 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, A_2, \ldots, A_N) = 3,这是满足条件的正整数序列的最小值。