#6379. 「是男人就过8题——Pony.ai」Intervals

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

设区间 [s, t] 表示在 s t 之间的整数集合 (包含 s t )。给定一个 n 个区间的集合 A , 求出一个集合 B (不一定要是 A 的子集), 满足对于任意 [s, t]\in A , 均可以用 B 中若干个区间的并来表示,你的目标是最小化 B 中区间个数

输入格式

本题至多有 100 组测试数据

每一组数据包含一个整数 n , 下面 n 行每行两个空格分开的整数 s_i, t_i , 表示 A 中的一个区间

输出格式

对于每组数据,输出一个整数 m , 表示 B 中的区间个数。

以下 m 行,每行包含两个空格隔开的整数 s,t 表示 B 中的区间

如果有多解,输出任意一组

样例

样例输入

2
1 2
3 4
3
1 2
3 4
1 4
7
5 9
0 6
4 8
3 7
0 5
7 9
4 6

样例输出

2
1 2
3 4
2
1 2
3 4
5
0 5
4 6
3 7
5 8
7 9

数据范围与提示

对于 100\% 的数据, 1 \leq n \leq 1000 , 0 \leq s_i \leq t_i \leq 10^9

特别鸣谢楼天城和吉如一提供试题,数据。