P7013 [CERC2013] History course

你需要按某种顺序为一系列重要历史事件安排讲座，每个讲座对应一个事件。每个事件持续一段时间区间 $[a_i, b_i]$。如果两个事件的时间区间有公共点，则称这两个事件是相关的。为了方便起见，安排相关事件的讲座时应尽量靠近。此外，对于不相关的事件，讲座应按照事件发生的顺序进行（如果事件 A 先于不相关事件 $B$ 发生，那么 A 的讲座应先于 B 的讲座）。找到最小的整数 $k \ge 0$ 和一个讲座顺序，使得任何两个相关事件的讲座之间的间隔最多为 $k$（讲座编号 $i$ 和 $j$ 之间的间隔被认为是 $|i−j|$）。

输入的第一行包含测试用例的数量 $t$。每个测试用例的描述如下：每个测试用例的第一行包含一个整数 $n (1 \le n \le 50000)$。接下来的 $n$ 行中的每一行包含两个整数 $a_i$ 和 $b_i (-10^9 \le a_i \le b_i \le 10^9)$，表示第 $i$ 个区间的两个端点。所有区间是两两不同的。

按输入中出现的顺序输出每个测试用例的答案。每个测试用例答案的第一行应包含最小值 $k$。接下来的 $n$ 行应按顺序列出区间（格式与输入相同），使得任何两个相关事件的讲座之间的间隔最多为 $k$。记得将任何不相关的区间按正确的顺序排列！

时间限制：10 秒，内存限制：128 MB。感谢 [hht2006](/user/175829) 提供的 Special Judge。 题面翻译由 ChatGPT-4o 提供。