Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Costly Array

By upobir · Limits 2s, 512 MB · Custom Checker

Oyler received a peculiar homework from his school. The teacher gave him a positive number nn and told him to construct an array of length nn, whose entries are in the range 1,,n1, \cdots , n. The teacher also gave some extra conditions in the form of "ll rr", meaning that the numbers at indices between ll and rr (inclusive) should be distinct.

So Oyler is trying to make such an array. To fill up the array, he needs to buy numbers from the local shop. If he buys a number xx, he can use that number at as many indices as he likes. In order to keep the cost of this homework manageable, he wants to buy as few numbers as possible. Given the conditions, output an array that uses minimum number of distinct numbers and satisfies the conditions.


There will be TT testcases.

Each testcase will begin with a line containing space separated numbers nn and cc. nn is the length of the array to be created, cc is the number of conditions.

The next cc lines will contain the requirements. Each requirement is given as space separated numbers ll and rr, meaning that the numbers which have index between ll and rr (inclusive) are distinct.

1T1051 \leq T \leq 10^5
1n1051 \leq n \leq 10^5
0c1050 \leq c \leq 10^5
1lrn 1 \leq l \leq r \leq n
The sum of nn over all testcases 105\leq 10^5
The sum of cc over all testcases 105\leq 10^5


For each testcase, output the final array in one line. The numbers should be space separated and in the range [1,n][1, n].

If there are multiple answers, you can output any such array.


5 2
1 3
2 4
1 3 2 1 1



    66% Solution Ratio

    ASIF_GSCEarliest, 3w ago

    prodip_bsmrstuFastest, 0.0s

    ASIF_GSCLightest, 655 kB

    blizzardShortest, 213B


    Login to submit


    Consider the [l,r][l, r][l,r] that is longest, then we will at least need r−l+1r-l+1r−l+1 distinct v...

    Related Contests