AT_arc222_a.Colorful Intervals

You are given positive integers $N$ and $M$. For each $j = 1, 2, \ldots, M$, you are given a pair of integers $(L_j, R_j)$ satisfying $1\leq L_j\leq R_j\leq N$.

Consider a length-$N$ positive integer sequence $A = (A_1, A_2, \ldots, A_N)$ satisfying the following condition for all $j = 1, 2, \ldots, M$:

• $A_{L_j}, A_{L_j+1}, \ldots, A_{R_j}$ are all distinct.

It can be proved that such a positive integer sequence $A$ always exists. Among all positive integer sequences $A$ satisfying the condition, output one that minimizes the value of $\max(A_1, A_2, \ldots, A_N)$.

$T$ test cases are given; solve each of them.

给定正整数 $N$ 和 $M$。对于每个 $j = 1, 2, \ldots, M$，给定一对满足 $1\leq L_j\leq R_j\leq N$ 的整数 $(L_j, R_j)$。

考虑一个长度为 $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$ 组测试数据；请分别求解每组数据。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$N$ $M$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

输入从标准输入给出，格式如下：

$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$

Output one line per test case. For each test case, output the elements, space-separated, of a positive integer sequence $A$ satisfying the condition that minimizes $\max(A_1, A_2, \ldots, A_N)$.

$A_1$ $A_2$ $\ldots$ $A_N$

If multiple such $A$ exist, any of them will be accepted.

每个测试用例输出一行。对于每个测试用例，输出满足条件的正整数序列 $A$ 的各元素（以空格分隔），使得 $\max(A_1, A_2, \ldots, A_N)$ 最小。

$A_1$ $A_2$ $\ldots$ $A_N$

若存在多个满足条件的序列 $A$，输出其中任意一个即可。

Sample 1 Explanation:
For the first test case, the output can be verified to satisfy the condition as follows:

• $A_1, A_2, A_3, A_4, A_5$ are $1, 2, 3, 4, 5$, which are all distinct.

In this case, $\max(A_1, A_2, \ldots, A_N) = 5$, which is the minimum value for a positive integer sequence satisfying the condition.

For the second test case, the output can be verified to satisfy the condition as follows:

• $A_1, A_2$ are $3, 1$, which are all distinct.
• $A_2, A_3$ are $1, 2$, which are all distinct.
• $A_3, A_4, A_5$ are $2, 1, 3$, which are all distinct.

In this case, $\max(A_1, A_2, \ldots, A_N) = 3$, which is the minimum value for a positive integer sequence satisfying the condition.

Constraints

• $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$)
• All input values are integers.
• The sum of $N$ over all test cases is at most $2\times 10^5$.
• The sum of $M$ over all test cases is at most $2\times 10^5$.

样例 1 解释：
对于第一个测试用例，输出可验证满足如下条件：

• $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$，这是满足该条件的正整数序列所能达到的最小最大值。

约束条件

• $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$。