A13206 | Movie Fan

The first line contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases in the input. The following are descriptions of the $t$ test cases.

The first line of each test case contains two integers $n$ and $m$ ( $1 \le n \le 2 \cdot 10^5$ , $1 \le m \le 10^9$ ) — the number of movies and the maximum number of movies that Polycarp can view per day.

In the next $n$ lines, the movies themselves are described, one per line, by a pair of integers $a_i$ , $b_i$ ( $1 \le a_i \le b_i \le 10^9$ ) — the first and last airing days for the $i$ -th movie.

It is guaranteed that the sum of the values $n$ for all test cases in the input does not exceed $2 \cdot 10^5$ .

Print $t$ answers to given test cases in the order in which they appear in the input: the $i$ -th answer should consist of two lines. Print the integer $d$ in the first line of each test case answer:

- $d=0$ , if there is a schedule such that all movies are watched during airing,
- $d>0$ , if such a schedule does not exist — in this case, $d$ is equal to the minimum value of maximum among all the watching "delays" after the end of airing.

In the second line of the answer to each test case, print $n$ positive integers $t_1, t_2, \dots, t_n$ , where $t_i$ is the number of the day when Polycarp needs to watch the $i$ -th movie in the optimal schedule.

If there are several answers, print any of them.

无