题目描述

设区间 $[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$ 。

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