UpDown

A permutation with $2 \cdot N$ values is written on $N$ rows with two elements each, thus forming two columns.

Task

Choose a maximum number of rows $M$ on which, if we write the elements one beneath the other and read them from top to bottom, the elements of the column on the left form an ascending sequence, and the elements of the column on the right form a descending sequence.

Input data

The first line contains the natural number $N$. Each of the following $N$ lines contains two natural numbers separated by a space. All the $2 \cdot N$ elements are distinct natural numbers from the set $\{1,2, \dots, 2 \cdot N \}$.

Output data

The first line will contain the maximum number of rows $M$, followed by $M$ pairs of numbers from the input, which form an ascending sequence on the first column, respectively a descending sequence on the second column.

Constraints and clarifications

• $1 \leq N \leq 300 \ 000$ ($1 \leq 2 \cdot N \leq 600 \ 000$).
• There can be several solutions for the problem.
• If you print only the correct number of rows, you get $20\%$ of the score.
• The test cases are not the same as the ones used in the contest, so the scores might be slightly different from these obtained in the real contest.

Example

stdin

8
7 3
12 10
11 16
4 2
9 8
14 5
1 15
6 13 

stdout

4
1 15
6 13
9 8
14 5 

Explanation

$N=8$

We have a permutation with $16$ elements arranged on $8$ rows out of which the maximum number of rows that satisfy the task of the problem is $M=4$.

The pairs of numbers $(1 \ 15) (6 \ 13) (9 \ 8) (14 \ 5)$ can be found in the rows of the permutation which is given in the input file. The first numbers on the row form the ascending sequence $(1 \ 6 \ 9 \ 14)$, and the other numbers form the descending sequence $(15 \ 13 \ 8 \ 5)$.

Another possible solution can be

• $1 \ 15$
• $6 \ 13$
• $12 \ 10$
• $14 \ 5$