Background

Translated from XXXI Olimpiada Informatyczna - Stage 1 Zapobiegliwy student。

Problem Description

Consider the following simple problem:

You have $n$ segments on the number line. You want to choose as many segments as possible so that they are pairwise disjoint.

I know you can do it, but you need to solve this:

You have $n$ segments on the number line. You want to choose as many pairs of segments $(u_i, v_i)_{i=1}^k$ as possible, i.e., maximize $k$.

They must satisfy $k + 1$ requirements:

• $u_1, u_2, \cdots, u_k$ are pairwise disjoint.
• $v_1, u_2, u_3, \cdots, u_k$ are pairwise disjoint.
• $u_1, v_2, u_3, u_4, \cdots, u_k$ are pairwise disjoint.
• $\cdots$
• $u_1, u_2, \cdots, u_{k-1}, v_k$ are pairwise disjoint.

Here, for all $i$, $u_i$ and $v_i$ cannot be the same.

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, j$ are disjoint 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 a pair of segment indices.

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

3
1 3
4 6
8 7

见附件

见附件

见附件

见附件

Hint

If your first line is correct but your construction is not (you may choose not to output a construction; in this case, do not output a newline), you can get $50\%$ of the score.

If your construction is valid and the first line differs from the answer by at most $1$, you can get $15\%$ of the score.

Translated by ChatGPT 5