Under construction

Still being built. Things may change

Birthday

Time limit1sMemory limit128 MB

Summary
Given N intervals, find and print the longest chain of distinct intervals where each contains the next one.
Level

Medium6 of 10

Topics
Dynamic programming, Sorting, Greedy
Solved
No attempts yet

Problem

Sang-geun received N intervals as a birthday gift. Each interval is a numeric interval written as [A, B], where A and B are integers.

He wants to build the longest possible sequence from the intervals he has. All intervals in the sequence must be distinct, and each interval must contain the interval immediately after it. Interval [A, B] contains interval [C, D] when A ≤ C and D ≤ B.

Find one longest interval sequence that satisfies these conditions.

Input

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

Each of the next N lines contains two integers A and B describing an interval [A, B]. (1 ≤ A < B ≤ 1,000,000)

Output

Print K, the length of the sequence, on the first line. Then print K lines containing the intervals in sequence order. Each interval must be printed in the same format as the input: A B.

Examples3

  1. Example 1

    Input
    5
10 30
20 40
30 50
10 60
30 40
    Expected output
    3
10 60
30 50
30 40

  2. Example 2

    Input
    3
3 4
2 5
1 6
    Expected output
    3
1 6
2 5
3 4

  3. Example 3

    Input
    6
1 4
1 5
1 6
1 7
2 5
3 5
    Expected output
    5
1 7
1 6
1 5
2 5
3 5