#4051. [Cerc2013] History course

内存限制:128 MiB 时间限制:10 Sec

题目描述

你被给定一系列关于重要的历史事件的演讲,每件事一场演讲,它们不按顺序排列。每件历史事件持续一个时间段[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,该排法最优。