AT_arc222_a [ARC222A] 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.

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 $

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.

### Sample Explanation 1 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 $ .