题目描述

题目译自 XXXI Olimpiada Informatyczna – I etap Zapobiegliwy student

在 Bajtocja 大学的科学节上，有 $n$ 个不同的讲座，编号为 $1$ 到 $n$。每个讲座都在一个连续的时间段内进行。学生 Bajtazar 想要选择一些讲座来参加。他选择的讲座必须在不同的时间进行。

对于 Bajtazar 来说，所有的讲座都同样有趣。但他也想要防备一些意外的情况。他希望能够选择讲座的方式是，如果有一个（任意选择的）讲座被取消了，他还能从剩下的讲座中再选一个，而不会和他原来选择的讲座发生时间冲突。请你帮他选择最多的讲座数，满足上述条件。

形式化地说，如果 Bajtazar 决定选择 $k$ 个互不相同且不冲突的讲座 $u_{1}, \ldots, u_{k}\ (1 \leq u_{i} \leq n)$，那么对于每个 $i=1, \ldots, k$，必须存在一个讲座 $v_{i} \in\{1, \ldots, n\}$，使得 $v_{i} \notin \{u_{1}, \ldots, u_{k}\}$，并且讲座 $u_{1}, \ldots, u_{i-1}, v_{i}, u_{i+1}, \ldots, u_{k}$ 不冲突。两个讲座不冲突，当且仅当一个讲座刚好在另一个讲座结束的时候开始，或者更晚。Bajtazar 想要最大化这样选择的讲座数 $k$。

输入格式

第一行包含一个整数 $n\ (2\leq n \leq 5\cdot 10^5)$，表示所有讲座的数量。接下来的 $n$ 行描述了每个讲座的时间。第 $i$ 行包含两个整数 $a_{i}, b_{i}\ (1 \leq a_{i}<b_{i} \leq 10^{9})$，表示第 $i$ 个讲座的开始时间和结束时间。第 $i$ 个讲座和第 $j$ 个讲座不冲突，当且仅当 $b_{i} \leq a_{j}$ 或者 $b_{j} \leq a_{i}$。

输出格式

第一行输出一个整数，表示满足 Bajtazar 要求的最大可能的讲座数 $k$。在接下来的 $k$ 行中，每行包含两个整数 $u_{i},v_{i}\ (1\leq u_{i}, v_{i} \leq n)$，分别表 Bajtazar 选择的讲座编号和所对应的备选讲座的编号，对应于编号为 $u_{i}$ 的讲座。你可以以任意顺序输出这些讲座对。$v_{1}, \ldots, v_{k}$ 不需要互不相同。

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

3
1 3
4 6
8 7

Bajtazar 决定选择编号为 $u_{1}=1, u_{2}=4$ 和 $u_{3}=8$ 的讲座，分别在时间区间 $[1,5]$, $[9,12]$ 和 $[15,21]$ 进行。这些讲座之间没有冲突。此外：

• 第一个备选讲座，$v_{1}=3$，在时间区间 $[4,8]$ 进行。这个讲座与在时间区间 $[9,12]$ 和 $[15, 21]$ 进行的讲座没有冲突。
• 第二个备选讲座，$v_{2}=6$，在时间区间 $[14,15]$ 进行。这个讲座与在时间区间 $[1,5]$ 和 $[15,21]$ 进行的讲座没有冲突。
• 第三个备选讲座，$v_{3}=7$，在时间区间 $[20,22]$ 进行。这个讲座与在时间区间 $[1,5]$ 和 $[9,12]$ 进行的讲座没有冲突。

样例 2

见附加文件下 [zap1ocen.in](file:zap1ocen.in) 和 [zap1ocen.out](file:zap1ocen.out)。

该样例满足 $n=100$，第 $i$ 个讲座的时间区间为 $[i, i+1]$。

样例 3

见附加文件下 [zap2ocen.in](file:zap2ocen.in) 和 [zap2ocen.out](file:zap2ocen.out)。

该样例满足 $n=5\cdot 10^5$，第 $i$ 个的时间区间为 $[i, i+1]$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	限制	分值
$1$	$n \leq 3000$	$40$
$2$	无额外限制	$60$

如果只有第一行是正确的，你的程序将获得该测试点的 $50\%$ 分数。如果第一行与标准答案相差 $1$ 但备选讲座的选择是正确的，你的程序将获得该测试点的 $15\%$ 分数。