P17425 [ICPC 2018 Xuzhou R] Rikka with A Long Colour Palette

**蓝色，天空、海洋与你眼眸的颜色。** **绿色，自然、生机与生命的颜色。** **紫色，明断之人的颜色，也是追求精神圆满者的颜色。** **橙色，唯一一种同时是水果的颜色。** **黄色，笑脸中的颜色。** **红色，最温暖的颜色。** Rikka 喜爱它们所有，但什么才是她最钟情的颜色？她找到了 $k$ 种不同的颜色，编号从 $1$ 到 $k$，她知道最好的颜色应该是由它们全部混合之后得到的。那最好的颜色被称作 **DREAM**。 Rikka 还准备了一个长度为 $10^9$ 的狭长调色板。她在调色板上指定了 $n$ 个线段。一个由两个整数 $l$ 和 $r$（$0 \le l < r \le 10^9$）描述的线段表示调色板上的一个区域，该区域的左端点（相应地，右端点）与调色板最左端的距离为 $l$（相应地，$r$）。 对于每个指定的线段，她会将自己找到的这些颜色（从 $1$ 到 $k$）中的任意一种颜料均匀地涂抹在上面。由于这些线段可能相交，某些区域可能含有多种不同颜色的颜料。如果某些区域含有全部 $k$ 种她找到的不同颜色，这些颜色便会融合成为 DREAM。 现在，Rikka 希望你最大化调色板中能够融合成为 DREAM 的所有区域的总长度。你还需要给出一个可行的方案。

输入包含多组测试数据，第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试数据的组数。 对于每组测试数据，第一行包含两个整数 $n$（$1 \le n \le 2 \times 10^5$），表示 Rikka 指定的线段数量，以及 $k$（$1 \le k \le 2 \times 10^5$），表示 Rikka 找到的颜色种数。 接下来的 $n$ 行，每行包含两个整数 $l$ 和 $r$（$0 \le l < r \le 10^9$），表示调色板上的第 $i$ 条线段。 输入保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^6$。

对于每组测试数据，输出两行。第一行输出一个整数，表示所求区域的最大总长度。然后第二行输出 $n$ 个由空格分隔的整数，描述一个可行的方案，其中第 $i$ 个数表示第 $i$ 条线段所涂的颜色。 所有可行的方案均被允许，因此你可以输出其中任意一种。

翻译由 DeepSeek V4 Pro 完成