历史课 History course
题意翻译
## 题目描述
你有一些有关于重要历史事件的讲座的时间方面的信息，这些信息会按照一定顺序给你。每一个历史事件都有一个讲座与之对应。每一个讲座都会持续一段时间[ai,bi]。我们当且仅当在两个讲座的时间间隔有相同之处时，才说这两个讲座是有关联的。当两个有关联的讲座相隔比较近时，安排才会方便。此外，两个内容不相干的讲座的时间安排，我们按照事件的发展顺序去安排（假如事件A发生先于B，则A的讲座应该被安排在B前面）
找到一个最小的整数K（K>=0）和讲座的顺序，要求在这个顺序中，两个有关系的讲座之间最多相隔K个讲座（讲座i和j被视为相隔i-j个讲座）
## 输入
输入的第一行有一个数字T，代表有几组数据，而在每组的输入中：
第一行包含一个数字n（1<=n<=50000）。在下面N行中，每一行包括两个数字ai和bi。
（-10^9<=ai<=bi<=10^9）代表第N场讲座的时间。ai 和bi 是成对出现的，且保证俩数不同。
## 输出
每一组数据有一个自己的输出，按输入中出现的顺序输出答案。每组数据第一行是k的最小值。之后的n行，每一行应该以你规定的顺序，列出你要安排的讲座的持续时间（即这一讲座的[ai,bi]），输出格式与输入格式一致。
请记住要把没有关联的讲座放在正确的位置上
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4569
[PDF](https://uva.onlinejudge.org/external/16/p1694.pdf)