困难优化

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定 $n$ 个闭线段 $[L_i,R_i]$。所有 $2n$ 个端点都是两两不同的整数，并且这些线段构成层状集：任意两条线段要么互不相交，要么其中一条严格包含另一条。

请在每条线段 $[L_i,R_i]$ 中选择一个非空、端点为整数的子线段 $[l_i,r_i]$，满足 $L_i\le l_i<r_i\le R_i$。任意两个所选子线段的内部不能相交，但允许它们拥有相同端点。

最大化

你需要同时输出最大值和一组达到最大值的构造。答案可能不唯一，任何最优合法构造均可通过。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行两个整数 $L_i,R_i$。

输出格式

第一行输出最大长度和。

接下来 $n$ 行，第 $i$ 行输出两个整数 $l_i,r_i$，表示为输入中的第 $i$ 条线段选择的子线段。

样例输入

4
1 10
2 3
5 9
6 7

样例输出

7
3 6
2 3
7 9
6 7

样例说明

下图分别展示原线段与样例构造。

数据范围

对于全部数据，$1\le n\le2000$，$0\le L_i<R_i\le10^9$。所有端点两两不同，输入线段构成层状集。

每个测试点独立计分。