← 返回题目列表

Codeforces · 1148/D

D. 肮脏的行为做了肮脏的廉价

中文机器翻译题面 查看原题

给你 $$$n$$$ 整数对 $$$(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$$$。这些对中的所有整数都是不同的,并且范围在 $$$1$$$ 到 $$$2 \cdot n$$$ 之间(包括 $$$1$$$)。

让我们调用整数序列 $$$x_1, x_2, \ldots, x_{2k}$$$ 好,如果

- $$$x_1 < x_2 > x_3 < \ldots < x_{2k-2} > x_{2k-1} < x_{2k}$$$,或
- $$$x_1 > x_2 < x_3 > \ldots > x_{2k-2} < x_{2k-1} > x_{2k}$$$。

您需要选择不同索引 $$$i_1, i_2, \ldots, i_t$$$ 的子集及其顺序,如果您在单个序列中写下这些对中的所有数字(序列将为 $$$a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \ldots, a_{i_t}, b_{i_t}$$$),这个序列很好。

您可以选择的最大索引子集是什么?还需要构造相应的索引序列$$$i_1, i_2, \ldots, i_t$$$。

输入

第一行包含单个整数 $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — 对的数量。

接下来的 $$$n$$$ 行包含两个数字 — $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 2 \cdot n$$$) — 成对的元素。

保证对中的所有整数都是不同的,也就是说,从 $$$1$$$ 到 $$$2 \cdot n$$$ 的每个整数都被恰好提到一次。

输出

在第一行中打印一个整数 $$$t$$$ — 答案中的对数。

然后打印 $$$t$$$ 不同的整数 $$$i_1, i_2, \ldots, i_t$$$ - 按相应顺序的对的索引。

示例

输入 #1

5
1 7
6 4
2 10
9 8
3 5

输出 #1

3
1 5 3

输入 #2

3
5 4
3 2
6 1

输出 #2

3
3 2 1

注意

第一个示例中的最终序列是 $$$1 < 7 > 3 < 5 > 2 < 10$$$。

第二个示例中的最终序列是 $$$6 > 1 < 3 > 2 < 5 > 4$$$。