[Cerc2013] History course
时间限制：10s 空间限制：128MB
题目描述
你被给定一系列关于重要的历史事件的演讲，每件事一场演讲，它们不按顺序排列。每件历史事件持续一个时间段[ai，bi]。如果两件事的时间有共同区间，我们说它们是有关联的。把关于有关联的历史事件的演讲排的彼此靠近能使课程更便于理解。此外，不相关的演讲必须按历史事件的发生时间排序（如果A在B之前发生，且AB不相关，那么关于A的演讲必须在B之前进行）
找出最小的整数k>=0和一个演讲的顺序，使得排序后任意两场相关的演讲之间的间隔不超过k（第i场演讲和第j场演讲之间的间隔是|i-j|）。
输入格式
第一行包括数据组数T。每组数据包含以下内容：
每组数据的第一行是一个数n，1<=n<=50000。接下来n行包括两个整数ai和bi，-10^9<=ai<=bi<=10^9。区间两两不相同。
输出格式
每组数据答案的第一行是一个最小值k，接下来n行按顺序列举排列后的演讲的历史事件的区间（与输入中的格式一样），使得任意两个相关的演讲相隔不超过k。切记将不相关的演讲按时间顺序排列！
样例输入
1 3 1 6 2 3 4 5
样例输出
1 2 3 1 6 4 5
提示
共有三个历史事件，其中1,2；1,3是相关的，2,3不相关，且2在3之前发生，所以2应该排在3的前面。对于相关的历史事件，1与2在排列后的位置是2和1，间隔为1,1与3在排列后的位置为2与3，间隔为1,所以此时k最小为1，该排法最优。
题目来源
没有写明来源