在拜特大学（University of Bajtock）的科学节期间，共有 $n$ 场不同的讲座，编号从 $1$ 到 $n$。每场讲座都在一个特定的时间段内进行。学生拜特扎尔（Bajtazar）想要选择一些讲座参加。他所选择的讲座必须在不同的时间进行。

对拜特扎尔来说，所有提供的讲座都同样有趣。但他希望为各种随机事件做好准备。因此，他想选择讲座，使得如果其中任意一场（任意选择的）被取消，他都能从剩余的讲座中再选出一场，且该讲座不会与他最初选择的其他讲座冲突。请帮助他选择满足上述条件的最大数量的讲座。

形式化地说，如果拜特扎尔决定选择 $k$ 场两两不同且互不冲突的讲座 $u_1, \dots, u_k$（其中 $1 \le u_i \le n$），那么对于每个 $i = 1, \dots, k$，必须存在一场讲座 $v_i \in \{1, \dots, n\}$，使得 $v_i \notin \{u_1, \dots, u_k\}$，且讲座 $u_1, \dots, u_{i-1}, v_i, u_{i+1}, \dots, u_k$ 互不冲突。两场讲座互不冲突，当且仅当其中一场讲座的开始时间不早于另一场讲座的结束时间。拜特扎尔希望最大化所选讲座的数量 $k$。

输入格式

输入的第一行包含一个整数 $n$ ($n \ge 2$)，表示所有讲座的总数。接下来的 $n$ 行，每行描述一场讲座。第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i < b_i \le 10^9$)，分别表示第 $i$ 场讲座的开始时间和结束时间。第 $i$ 场讲座和第 $j$ 场讲座互不冲突，如果 $b_i \le a_j$ 或 $b_j \le a_i$。

输出格式

输出的第一行应包含满足拜特扎尔条件的最大讲座数量 $k$。在接下来的 $k$ 行中，每行应包含两个范围在 $1$ 到 $n$ 之间的整数 $u_i$ 和 $v_i$，其中 $u_i$ 表示拜特扎尔选择的讲座编号，$v_i$ 表示与讲座 $u_i$ 对应的备选讲座编号。这些对可以按任意顺序输出。$v_1, \dots, v_k$ 不必两两不同。

样例

输入格式 1

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

输出格式 1

3
1 3
4 6
8 7

说明

拜特扎尔决定选择编号为 $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]$ 进行的讲座不冲突。

测试样例

测试样例 0 即为上述示例。此外： 样例 1：$n = 100$，第 $i$ 场讲座为 $[i, i + 1]$； 样例 2：$n = 500\,000$，第 $i$ 场讲座为 $[i, i + 100]$。

评分

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

子任务