CF2162F.Beautiful Intervals

You are given an integer $n$ and $m$ intervals. Each interval is of the form $[l_i, r_i]$ and satisfies $1 \le l_i \le r_i \le n$. Note that there can be duplicate intervals.

Let $p$ be a permutation of length $n$ containing all the integers $0,1,2,\dots,n-1$ exactly once.

There is a multiset $M$ which is initially empty.

For each interval $[l_i, r_i]$:

• consider the subarray $p[l_i \dots r_i]$,
• compute $v_i = \operatorname{mex}$$^{\text{∗}}$$(p[l_i \dots r_i])$,
• insert $v_i$ into $M$.

After processing all the intervals, $M$ will be equal to ${v_1, v_2, \dots, v_m}$.

Your task is to construct a permutation $p$ of length $n$ containing all the integers $0,1,2,\dots,n-1$ exactly once such that $\operatorname{mex}(M)$ is minimized.

$^{\text{∗}}$$\operatorname{mex}(a)$ denotes the minimum excluded (MEX) of the integers in $a$. For example, $\operatorname{mex}([2,2,1])=0$ because $0$ does not belong to the array, and $\operatorname{mex}([0,3,1,2])=4$ because $0$, $1$, $2$, and $3$ appear in the array, but $4$ does not.

给你一个整数 $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$ 没有出现。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Description of each testcase follows.

The first line contains two integers $n$ and $m$ ($3 \le n \le 3000$, $1 \le m \le 3000$).

The next $m$ lines each contain two space-separated integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$) each denoting an interval.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$, and the sum of $m$ over all test cases does not exceed $3000$.

第一行包含一个整数 $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$。

For each testcase, print a permutation $p$ of length $n$ containing all the integers $0,1,2,\dots,n-1$ exactly once such that $\operatorname{mex}(M)$ is minimized.

If there are multiple answers, you may print any one of them.

对于每个测试用例，输出一个长度为 $n$ 的排列 $p$，该排列恰好包含所有整数 $0,1,2,\dots,n-1$ 各一次，使得 $\operatorname{mex}(M)$ 最小。

如果存在多个满足条件的答案，你可以输出其中任意一个。

For the first testcase, if we choose to construct $p = [2, 0, 1]$, then $M = {\operatorname{mex}(2, 0)} = {1}$. Now, $\operatorname{mex}(M) = 0$.

For the third testcase, if we choose to construct $p = [0, 2, 1, 3]$, then $M = {\operatorname{mex}(0, 2), \operatorname{mex}(2, 1), \operatorname{mex}(1, 3), \operatorname{mex}(0), \operatorname{mex}(3)} = {1, 0, 0, 1, 0}$. Now, $\operatorname{mex}(M) = 2$.

For the fourth testcase, if we choose to construct $p = [2, 0, 1, 3, 4]$, then $M = {\operatorname{mex}(1, 3, 4), \operatorname{mex}(2), \operatorname{mex}(0, 1, 3), \operatorname{mex}(4)} = {0, 0, 2, 0}$. Now, $\operatorname{mex}(M) = 1$.

For the fifth testcase, if we choose to construct $p = [3, 1, 0, 2]$, then $M = {\operatorname{mex}(3, 1, 0), \operatorname{mex}(1, 0, 2)} = {2, 3}$. Now, $\operatorname{mex}(M) = 0$.

对于第一个测试用例，如果我们选择构造 $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$。