bzoj#P4051. [Cerc2013] History course

[Cerc2013] History course

题目描述

你被给定一系列关于重要的历史事件的演讲,每件事对应一场演讲。

它们不按顺序排列,每件历史事件持续一个时间段 [ai,bi][a_i,b_i]

如果两件事的时间有共同区间,我们说它们是有关联的,把关于有关联的历史事件的演讲排的彼此靠近能使课程更便于理解。

此外,不相关的演讲必须按历史事件的发生时间排序(如果 A 在 B 之前发生,且 AB 不相关,那么关于 A 的演讲必须在 B 之前进行)。

找出最小的整数 kkk0k \ge 0) 和一个演讲的顺序,使得排序后任意两场相关的演讲之间的间隔不超过 kk(第 ii 场演讲和第 jj 场演讲之间的间隔是 ij|i-j|)。

输入格式

第一行包括数据组数 TT

每组数据的第一行是一个数 nn,接下来 nn 行每行包括两个整数 [ai,bi][a_i,b_i],区间两两不相同。

输出格式

每组数据答案的第一行是一个最小值 kk,接下来 nn 行按顺序列举排列后的演讲的历史区间(与输入中的格式一样),使得任意两个相关的演讲间隔不超过 kk

切记将不相关的演讲按时间顺序排列!

1 
3 
1 6 
2 3 
4 5 
1 
2 3 
1 6 
4 5 

样例说明

共有三个历史事件,其中 1,21,21,31,3 是相关的,2,32,3 不相关,且 2233 之前发生,所以 22 应该排在 33 的前面。

对于相关的历史事件,1122 在排列后的位置是 2211,间隔为 11,1133 在排列后的位置为 2233,间隔为 11,所以此时 kk 最小为 11,该排法最优。

数据规模与约定

对于 100%100\% 的数据,1n5×1041 \le n \le 5 \times 10^4109aibi109-10^9 \le a_i \le b_i \le 10^9