Preparing NOJ

Distinct Values

2000ms 32768K


Chiaki has an array of $$$n$$$ positive integers. You are told some facts about the array: for every two elements $$$a_i$$$ and $$$a_j$$$ in the subarray $$$a_{l..r}$$$ ($$$l \le i < j \le r$$$), $$$a_i \ne a_j$$$ holds.
Chiaki would like to find a lexicographically minimal array which meets the facts.


There are multiple test cases. The first line of input contains an integer $$$T$$$, indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^5$$$) -- the length of the array and the number of facts. Each of the next $$$m$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

It is guaranteed that neither the sum of all $$$n$$$ nor the sum of all $$$m$$$ exceeds $$$10^6$$$.


For each test case, output $$$n$$$ integers denoting the lexicographically minimal array. Integers should be separated by a single space, and no extra spaces are allowed at the end of lines.

Sample Input:

2 1
1 2
4 2
1 2
3 4
5 2
1 3
2 4

Sample Output:

1 2
1 2 1 2
1 2 3 1 1



Provider HDU

Origin 2018 Multi-University Training Contest 1

Code HDU6301


Submitted 90

Passed 43

AC Rate 47.78%

Date 06/03/2019 16:57:44


Nothing Yet