AT_arc222_a [ARC222A] Colorful Intervals

给定正整数 $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$ 组测试数据，请求解每组测试数据。

输入由标准输入给出，格式如下： > $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$

每组测试数据输出一行。对于每组测试数据，输出满足题意、且 $\max(A_1, A_2, \ldots, A_N)$ 最小的正整数序列 $A$ 的各个元素，空格分隔。 > $A_1$ $A_2$ $\ldots$ $A_N$ 如果存在多个满足条件的 $A$，输出其中任意一个即可。

### 样例解释 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$。 由 ChatGPT 5 翻译