OI题库

有一些闭区间[ai,bi]（i=1、2、…、n），找出区间数最少的表示方案，并按递增的顺序定稿输出文件。当a≤b＜c≤d时，我们说区间[a,b]和[c,d]为递增顺序。

任务：

你的任务是编写一个程序完成下列工作：

• 从文件中读入这些区间；
• 算出满足上述条件的区间；
• 把结果写入文件。

输入：

文件的第一行是整数n，3≤n≤50000，代表区间个数，以下第i+1行1≤i≤n，有两个用空格分开的的整数ai和bi表示一个闭区间[ai,bi]（1≤ai≤bi≤1000000）。

输出：

文件包括，所求的不相交闭区间，每行描述一个闭区间，按照递增顺序。每个区间用两个以空格分开的整数表示，分别是该区间的开头和末端。

输入样例：

5
5 6
1 4
10 10
6 9
8 10

输出样例：

1 4
5 10