给定一个整数 $$$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)$$$ 最小化。
如果有多个答案,您可以打印其中任意一个。
示例
输入复制
53 11 23 51 11 22 22 22 34 51 22 33 41 14 45 43 51 12 44 44 21 32 4
输出复制
2 0 12 1 00 2 1 32 0 1 3 43 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$$$。