407265: GYM102739 G План Д

Как и Никита, Данила получил письма с кучей домашек. Разумеется, он тут же составил из них список и собрался выполнять в том порядке, в котором они записаны. Однако довольно быстро выяснилось, что далеко не все дела можно начать тогда, когда Данила это запланировал. Так что план придётся менять.

Для начала Данила разделил все домашки на подзадачи, выполнение каждой из которых займёт у него занимать одну (условную) единицу времени. Далее, для каждой подзадачи он определил день $$$s_j$$$, не раньше которого её можно начать выполнять, и день $$$f_j$$$, не позже которого её нужно закончить. Если в некоторый день Данил приступит к какой-либо подзадаче, то обязательно закончит её в этот же день.

Все домашки Данил хочет успеть выполнить за ближайшие $$$m$$$ дней. Также он хочет, чтобы подзадачи распределилсь достаточно равномерно, т.е. максимальное количество подзадач, которые он будет выполнять в течение одного дня, было минимально возможным.

Ваша задача — составить такой план распределения подзадач по дням.

В первой строке содержатся целые числа $$$n$$$ и $$$m$$$ $$$(1 \le n, \, m \le 3 \cdot 10^5)$$$ — число подзадач и число дней, за которые эти подзадачи нужно сделать.

В каждой из следующих $$$n$$$ строк содержится по два целых числа $$$s_j$$$ и $$$f_j$$$ $$$(1 \le s_j \le f_j \le m)$$$ — ограничения для $$$j$$$-й подзадачи.

В первой строке выведите целое число — минимально возможное максимальное число подзадач, которое придётся выполнить Даниле в течение одного дня.

В каждой из следующих $$$m$$$ строк выведите сначала число подзадач, которые Данил выполнит в этот день, а затем — номера этих подзадач.

Если существует несколько вариантов ответа, выведите любой.

$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 27 & n, m \le 100 & \text { подзадача } & \\ \hline 2 & 35 & s_i, f_i \le 1000 & \text { подзадача } & 1 \\ \hline 3 & 38 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2 \\ \hline \end{array}$$$$$$

12 7
2 5
1 3
6 7
3 6
2 2
1 7
4 5
7 7
5 7
4 6
2 5
2 6

2
1 2
2 5 1
2 11 4
2 7 10
2 12 9
1 3
2 6 8