P9925 [POI 2023/2024 R1] Thrifty Student

Translated from [XXXI Olimpiada Informatyczna - Stage 1](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Zapobiegliwy student](https://sio2.mimuw.edu.pl/c/oi31-1/p/zap/)。

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.

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$.

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.

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. | Subtask ID | Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $n \leq 3000$ | 40 | | 2 | $n \leq 500000$ | 60 | Translated by ChatGPT 5