题目描述

对于实数 $L$ 和 $R$，我们用$[L,R)$表示大于等于 $L$ 且小于 $R$ 的实数集合。这样的集合被称为右半开区间。

给定 $N$ 个右半开区间 $[L_i,R_i)$。设 $S$ 为它们的并集。将 $S$ 表示为最少数量的右半开区间的并集。

输入格式

输入从标准输入中给出，格式如下：

$N$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

输出格式

设 $k$ 为表示 $S$ 所需的最少右半开区间数。按 $X_i$ 升序输出这 $k$ 个右半开区间 $[X_i,Y_i)$，格式如下：

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_k$ $Y_k$

样例

3
10 20
20 30
40 50

10 30
40 50

3
10 40
30 60
20 50

10 60

样例解释

【样例1说明】
三个右半开区间 $[10,20),[20,30),[40,50)$ 的并集等于两个右半开区间 $[10,30),[40,50)$ 的并集。

【样例2说明】
三个右半开区间 $[10,40),[30,60),[20,50)$ 的并集等于一个右半开区间 $[10,60)$ 的并集。

数据范围

• $1 \leq N \leq 2\times 10^5$
• $1 \leq L_i < R_i \leq 2\times 10^5$
• 输入中的所有值都是整数。

来源

• AtCoder ABC256D