Единственное различие между двумя версиями задачи заключается в том, учитываются ли пересечения во всех точках или только в целых точках.
Легендарная мифическая птица Симург отвечает за охрану обширных земель, и для этой цели она наняла $$$n$$$ бдительных воинов. Каждый воин находится в боевой готовности в течение определенного отрезка времени $$$[l_i, r_i]$$$, где $$$l_i$$$ — время начала (включительно), а $$$r_i$$$ — время окончания (включительно), оба являются целыми положительными числами.
Один из доверенных советников Симурга, Зал, обеспокоен тем, что если несколько воинов будут караулить в одно и то же время и будут одеты в один и тот же цвет, они могут стать неотличимыми, что вызовет путаницу в дозоре. Чтобы предотвратить это, всякий раз, когда несколько воинов находятся на страже в один и тот же (возможно, нецелый) момент времени, должен быть хотя бы один цвет, который носит ровно один воин.
Таким образом, ваша задача состоит в том, чтобы определить минимальное необходимое количество цветов и назначить цвет $$$c_i$$$ каждому отрезку дозора воина $$$[l_i, r_i]$$$ таким образом, чтобы для каждого (возможно, нецелого) момента времени $$$t$$$ существовал цвет, который принадлежит ровно одному отрезку, содержащему $$$t$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Для каждого набора входных данных:
- Первая строка содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество воинов, размещенных Симургом.
- Каждая из следующих $$$n$$$ строк содержит по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$) — начало и окончание отрезка времени воина.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных:
- Выведите минимальное необходимое количество цветов $$$k$$$.
- Затем выведите строку из $$$n$$$ целых чисел $$$c_i$$$ ($$$1 \leq c_i \leq k$$$), где каждое $$$c_i$$$ — это цвет, присвоенный $$$i$$$-му воину.
521 23 421 22 331 42 53 651 42 83 75 106 951 52 63 74 76 7
1 1 1 2 1 2 2 1 2 1 3 2 3 1 2 1 3 2 1 3 1 1
Мы можем представить отрезок наблюдения каждого воина в виде отрезка по оси X;
В 1 наборе входных данных у нас есть два независимых отрезка, которые могут быть окрашены в один и тот же цвет.
Во 2 наборе входных данных точка 2 является общей для двух отрезков, что означает, что мы не можем раскрасить их в один и тот же цвет.
В 3 наборе входных данных отрезки могут быть окрашены, как показано ниже (отрезки покрашены в выбранный цвет; области закрашены цветом, если данный цвет встречается в этот момент времени ровно один раз):
В 4 наборе входных данных отрезки могут быть окрашены, как показано ниже:
В 5 наборе входных данных отрезки могут быть окрашены, как показано ниже. Изображение справа демонстрирует пример неправильной раскраски для этого набора входных данных; на момент времени $$$5.5$$$ нет уникального цвета:
