Problem Description

Given $n$ intervals, Mirko wants to construct some intervals such that each later interval is a sub-interval of the previous one, and every number in these intervals is contained in the given intervals.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers $[A,B]$, representing a given interval.

Output Format

The first line contains an integer $k$, which is the number of intervals that can be constructed.

The next $k$ lines each contain two integers, in order, representing the constructed intervals.

3
3 4
2 5
1 6

3
1 6
2 5
3 4

5
10 30
20 40
30 50
10 60
30 40

3
10 60
30 50
30 40

6
1 4
1 5
1 6
1 7
2 5
3 5

5
1 7
1 6
1 5
2 5
3 5

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^5$ and $1\le A<B\le 10^6$.

Notes

This problem is translated from COCI2007-2008 CONTEST #4 T5 POKLON。

Translated by ChatGPT 5