← 返回题目列表

AtCoder · arc222_a

A. 多彩间隔

中文机器翻译题面 查看原题

分数: 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,这是满足条件的正整数序列的最小值。