Problem Description

Consider the following simple problem:

You have $n$ segments on a number line, and you need to select as many segments as possible such that no two segments intersect.

I know you can solve this, but you need to address this variation:

You have $n$ segments on a number line, and you need to select as many pairs of segments $(u_i, v_i)_{i=1}^k$, maximizing $k$.

This must satisfy $k+1$ requirements:

• $u_1, u_2, \cdots, u_k$ do not intersect each other.
• $v_1, u_2, u_3, \cdots, u_k$ do not intersect each other.
• $u_1, v_2, u_3, u_4, \cdots, u_k$ do not intersect each other.
• $\cdots$
• $u_1, u_2, \cdots, u_{k-1}, v_k$ do not intersect each other.

Where $\forall i$, $u_i$ and $v_i$ are not the same segment.

Input Format

The first line contains a positive integer $n (n \geq 2)$.

The next $n$ lines each contain two positive integers $a_i, b_i (1 \leq a_i < b_i \leq 10^9)$, representing the two endpoints of a segment.

Two segments $i$ and $j$ do not intersect if and only if $b_i \leq a_j$ or $b_j \leq a_i$.

Output Format

The first line contains a positive integer $k$.

The next $k$ lines each contain two positive integers $u_i, v_i$, representing the indices of a pair of segments.

Sample Input and Output

Sample Input #1

8
1 5
3 10
4 8
9 12
11 16
14 15
20 22
15 21

Sample Output #1

3
1 3
4 6
8 7

Sample Input #2

(See attachment)

Sample Output #2

(See attachment)

Sample Input #3

(See attachment)

Sample Output #3

(See attachment)

Notes/Hints

If your first line is correct but the solution is incorrect (you can choose not to output the solution, in which case do not include a newline), you can get $50\%$ of the points.

If your solution is valid and the first line is within $1$ of the correct answer, you can get $15\%$ of the points.

见题面 Input 部分

见题面 Output 部分