### COCI 2007/2008, Contest #4

## Task POKLON

Mirko got a set of intervals for his birthday. There are many games he can play with them. In one of
them, Mirko must find the **longest** sequence of **distinct** intervals such that each interval in the
sequence is in the set and that each interval **contains** the one that **follows** in the sequence.

Write a program which finds one such longest sequence.

### Input

The first line of input contains the integer N (1 ≤ N ≤ 100 000), the number of intervals in the set.

Each of the following N lines contains two integers A and B describing one interval (1 ≤ A < B ≤ 1 000 000).

### Output

Output the length K of the longest sequence on the first line.

Each of the following K lines should contain one element of the sequence, an interval in the same format it was given in the input.

### Examples

## Input3 3 4 2 5 1 6 ## Output3 1 6 2 5 3 4 |
## Input5 10 30 20 40 30 50 10 60 30 40 ## Output3 10 60 30 50 30 40 |
## Input6 1 4 1 5 1 6 1 7 2 5 3 5 ## Output5 1 7 1 6 1 5 2 5 3 5 |

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Aug 13, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...