CF2034G2.Simurgh's Watch (Hard Version)

传说中的神鸟 Simurgh 负责守护一片辽阔的土地，她为此招募了 $n$ 名机敏的战士。每位战士都需要在特定的时间段 $[l_i, r_i]$ 内保持警戒，其中 $l_i$ 代表起始时间（包含），$r_i$ 代表结束时间（包含），两者均为正整数。

Simurgh 信任的顾问 Zal 担心，如果多个战士同时在岗且都穿着相同的颜色，那么他们之间可能会难以区分，从而导致混乱。为解决这一问题，在每个整数时刻 $t$，如果有多个战士在岗，必须确保至少有一种颜色仅被其中一个战士穿着。

任务是找出所需的最少颜色数量，并为每个战士的时间段 $[l_i, r_i]$ 分配一种颜色 $c_i$，使得对于包含在至少一个时间段内的每个整数时间点 $t$，总有一种颜色只被一个时间段在$t$时刻使用。

第一行输入一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示 Simurgh 招募的战士数量。
• 随后的 $n$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq 10^9$），表示第 $i$ 位战士的警戒时间段。

所有测试用例中的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例：

• 输出所需的最少颜色数量 $k$。
• 接下来输出一行，包括 $n$ 个整数 $c_i$（$1 \leq c_i \leq k$），每个 $c_i$ 表示分配给第 $i$ 位战士的颜色。

我们可以将每位战士的警戒时间段看作 X 轴上的一个区间。

以下示例展示了如何为各个测试用例的区间着色（区域只有在某时间点，仅某种颜色出现时该区域才被染色）：

• 测试用例 1：

  

• 测试用例 2：

  

• 测试用例 3：

  

本翻译由 AI 自动生成