题目背景

译自 XXXI Olimpiada Informatyczna - I etap Zapobiegliwy student。

题目描述

考虑如下的一个简单问题：

你有 $n$ 个线段在数轴上，你要选出尽量多的线段，使它们两两不交。

我知道你一定会做，但你需要解决这个：

你有 $n$ 个线段在数轴上，你要选出尽量多的线段对 $(u_i,v_i)_{i=1}^k$，即最大化 $k$。

满足 $k+1$ 个要求：

• $u_1,u_2,\cdots,u_k$ 两两不交。
• $v_1,u_2,u_3,\cdots,u_k$ 两两不交。
• $u_1,v_2,u_3,u_4,\cdots,u_k$ 两两不交。
• $\cdots$
• $u_1,u_2,\cdots,u_{k-1},v_k$ 两两不交。

其中 $\forall i$，$u_i$ 与 $v_i$ 不能相同。

输入格式

第一行一个正整数 $n(n\geq2)$。

接下来 $n$ 行每行两个正整数 $a_i,b_i(1\leq a_i<b_i\leq10^9)$，表示一个线段的两个端点。

两个线段 $i,j$ 不交当且仅当 $b_i\leq a_j$ 或 $b_j\leq a_i$。

输出格式

第一行一个正整数 $k$。

接下来 $k$ 行，每行两个正整数 $u_i,v_i$，表示一对线段的编号。

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

3
1 3
4 6
8 7

见附件

见附件

见附件

见附件

提示

如果你的第一行正确但是方案不对（可以不输出方案，此时不要有换行），你能得到 $50\%$ 的分数。

如果你的方案合法并且第一行和答案相差不超过 $1$，你能得到 $15\%$ 的分数。