J4 实践-5 区间合并

题目描述

给定 $n$ 条线段，合并线段，使得合并后的间隔最小，然后输出合并后间隔最小的线段们。

输入格式

第一行，仅一个整数，表示有 $N$ 条线段。

接下来有 $N$ 行，每行两个整数 $a_i$ 和 $b_i$，其中 $a_i$ 表示线段的左端点，$b_i$ 表示线段的右端点。

输出格式

输出应包含所有计算的成对非相交的线段的描述。在每一行中都应该写一个线段的描述。它应该由两个整数组成，用一个空格隔开，分别是线段的左端点和右端点。线段应按升序写入输出。

样例输入

5
5 6
1 4
10 10
6 9
8 10

样例输出

1 4
5 10

样例分析

线段$1,3,4,5$可以合并为一条线段。

数据范围

对于 $100\%$ 的数据：$3 \le n \le 50000$， $1 \le ai \le bi \le 1000000$。