Kotlin Heroes: Episode 3 |
---|
Закончено |
Последнее время Поликарп фанатеет от новинок кинематографа и старается их не пропускать!
В ближайшее время выйдут $$$n$$$ новых фильмов: $$$i$$$-й из них поступит в прокат в день $$$a_i$$$ и закончит прокат в день $$$b_i$$$. Это значит, что если Поликарп хочет посмотреть $$$i$$$-й фильм в кинотеатре, то должен это сделать в отрезок дней с $$$a_i$$$ по $$$b_i$$$ включительно.
Возможно, у Поликарпа не будет возможности посмотреть фильм в кинотеатре, тогда он может сделать это и после дня $$$b_i$$$, посмотрев его с помощью одного из онлайн-сервисов. Конечно, это нежелательный исход для Поликарпа, ведь весь мир уже успеет обсудить этот фильм в социальных сетях!
В день Поликарп может посмотреть не более $$$m$$$ фильмов. Помогите Поликарпу найти такое расписание просмотра фильмов, что каждый фильм будет просмотрен в кинотеатре. Если такое расписание не существует, то Поликарп хочет смотреть фильмы так, чтобы
В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте. Далее следуют описания $$$t$$$ наборов входных данных.
Первая строка каждого из наборов содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — количество фильмов и максимальное количество фильмов, сколько Поликарп может просмотреть в день.
Далее в $$$n$$$ строках описаны сами фильмы, по одному в строке, парой целых чисел $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$) — первый и последний день проката для $$$i$$$-го фильма.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2 \cdot 10^5$$$.
Выведите $$$t$$$ ответов на заданные наборы входных данных в порядке их записи в тесте: $$$i$$$-й ответ должен состоять из двух строк. В первую строку ответа выведите целое число $$$d$$$:
Во вторую строку ответа выведите $$$n$$$ положительных целых чисел $$$t_1, t_2, \dots, t_n$$$, где $$$t_i$$$ — номер дня, когда надо посмотреть $$$i$$$-й фильм, в оптимальном расписании.
Если ответов несколько, то выведите любой из них.
3 7 2 1 2 1 3 2 2 2 3 1 1 2 3 1 2 5 3 1 1 1 1 1 1 1 1 1 1 6 1 13 13 31 31 25 25 12 12 14 14 10 10
1 1 3 2 3 1 4 2 1 1 1 1 2 2 0 13 31 25 12 14 10
Название |
---|