区间合并问题

题目描述

给定 $n$ 个闭区间 $[L_i,R_i]$。这些区间的并集可以表示为若干个互不相交的闭区间，请求出所含区间数量最少的表示方案。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $L_i,R_i$，表示一个闭区间。

输出格式

第一行输出一个整数 $x$，表示合并后的区间数量。

接下来 $x$ 行，每行输出两个整数，表示一个合并后的闭区间。请按左端点从小到大的顺序输出。

样例输入 1

4
1 3
4 5
4 7
8 9

样例输出 1

3
1 3
4 7
8 9

数据范围

对于所有测试数据，$1\le n\le 2\times 10^5$，$1\le L_i\le R_i\le 2\times 10^5$。