← 返回题目列表

Codeforces · 2162/F

F. 美丽的间隔

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

给定一个整数 $$$n$$$ 和 $$$m$$$ 间隔。每个区间的形式为 $$$[l_i, r_i]$$$ 并满足 $$$1 \le l_i \le r_i \le n$$$。请注意,可能存在重复的间隔。

设 $$$p$$$ 为长度 $$$n$$$ 的排列,包含所有整数 $$$0,1,2,\dots,n-1$$$ 一次。

有一个多重集 $$$M$$$ 最初是空的。

对于每个区间 $$$[l_i, r_i]$$$:

  • 考虑子数组 $$$p[l_i \dots r_i]$$$,
  • 计算 $$$v_i = \operatorname{mex}$$$$$$^{\text{*}}$$$$$$(p[l_i \dots r_i])$$$,
  • 将 $$$v_i$$$ 插入 $$$M$$$ 中。

处理完所有区间后,$$$M$$$ 将等于 $$$\{v_1, v_2, \dots, v_m\}$$$。

你的任务是构造一个长度为 $$$n$$$ 的排列 $$$p$$$,包含所有整数 $$$0,1,2,\dots,n-1$$$ 一次,使得 $$$\operatorname{mex}(M)$$$ 为 最小化.

$$$^{\text{*}}$$$$$$\operatorname{mex}(a)$$$ 表示 $$$a$$$ 中整数的最小排除数 (MEX)。例如,$$$\operatorname{mex}([2,2,1])=0$$$,因为$$$0$$$不属于数组,$$$\operatorname{mex}([0,3,1,2])=4$$$,因为$$$0$$$、$$$1$$$、$$$2$$$和$$$3$$$出现在数组中,但$$$4$$$出现在数组中没有。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。每个测试用例的描述如下。

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 3000$$$, $$$1 \le m \le 3000$$$)。

接下来的 $$$m$$$ 行每行包含两个空格分隔的整数 $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$),每个表示一个区间。

保证所有测试用例的$$$n$$$总和不超过$$$3000$$$,所有测试用例的$$$m$$$总和不超过$$$3000$$$。

输出

对于每个测试用例,打印一个长度为 $$$n$$$ 的排列 $$$p$$$,其中包含所有整数 $$$0,1,2,\dots,n-1$$$ 一次,以使 $$$\operatorname{mex}(M)$$$ 最小化。

如果有多个答案,您可以打印其中任意一个。

示例

输入
复制

5
3 1
1 2
3 5
1 1
1 2
2 2
2 2
2 3
4 5
1 2
2 3
3 4
1 1
4 4
5 4
3 5
1 1
2 4
4 4
4 2
1 3
2 4

输出
复制

2 0 1
2 1 0
0 2 1 3
2 0 1 3 4
3 1 0 2

注意

对于第一个测试用例,如果我们选择构造 $$$p = [2, 0, 1]$$$,则 $$$M = \{\operatorname{mex}(2, 0)\} = \{1\}$$$。现在,$$$\operatorname{mex}(M) = 0$$$。

对于第三个测试用例,如果我们选择构造 $$$p = [0, 2, 1, 3]$$$,则 $$$M = \{\operatorname{mex}(0, 2), \operatorname{mex}(2, 1), \operatorname{mex}(1, 3), \operatorname{mex}(0), \operatorname{mex}(3)\} = \{1, 0, 0, 1, 0\}$$$。现在,$$$\operatorname{mex}(M) = 2$$$。

对于第四个测试用例,如果我们选择构造 $$$p = [2, 0, 1, 3, 4]$$$,则 $$$M = \{\operatorname{mex}(1, 3, 4), \operatorname{mex}(2), \operatorname{mex}(0, 1, 3), \operatorname{mex}(4)\} = \{0, 0, 2, 0\}$$$。现在,$$$\operatorname{mex}(M) = 1$$$。

对于第五个测试用例,如果我们选择构造 $$$p = [3, 1, 0, 2]$$$,则 $$$M = \{\operatorname{mex}(3, 1, 0), \operatorname{mex}(1, 0, 2)\} = \{2, 3\}$$$。现在,$$$\operatorname{mex}(M) = 0$$$。