题目描述

给定 \(n\) 个闭区间 \([a_i;b_i]\)，其中 \(i=1,2,...,n\)。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，\([1;2]\) 和 \([2;3]\) 可以合并为 \([1;3],[1;3]\) 和 \([2;4]\) 可以合并为 \([1;4]\)，但是 \([1;2]\) 和 \([3;4]\) 不可以合并。

我们的任务是判断这些区间可以合并成多少个分离的区间，并按照这些区间左端点从小到大输出。

格式

输入格式

第一行为一个整数 \(n\)。表示输入区间的数量。

之后 \(n\) 行，在第 \(i\) 行上，为两个整数 \(a_i\) 和 \(b_i\) ，整数之间用一个空格分隔，表示区间 \([a_i; b_i]\)。

输出格式

输出多行，每行一个合并后区间的左右界，中间用空格隔开。

样例1

样例输入1

5
5 6
1 5
10 10
7 9
8 10

样例输出1

1 6
7 10

限制

时间：\(1s\) 空间：\(128M\)

\(3 <= n <= 50,000; 1 <= ai <= bi <= 1,000,000\)

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)
模拟赛\(T1\)