Dirty Deeds Done Dirt Cheap

题意翻译

## 题目描述 有 $n$ 个整数对 $(a_1, b_1), (a_2, b_2), \cdots, (a_n, b_n)$. 保证 $a_1, b_1, a_2, b_2, \cdots, a_n, b_n$ 两两不相等, 并且均在区间 $[1, 2 \cdot n]$ 内. 好序列的定义: 对于一个序列 $x_1, x_2, \cdots, x_{2k}$, 满足 - $x_1 < x_2 > x_3 < \cdots < x_{2k - 2} > x_{2k - 1} < x_{2k}$ 或 - $x_1 > x_2 < x_3 > \cdots > x_{2k - 2} < x_{2k - 1} > x_{2k}$. 求一个序列 $i_1, i_2, \cdots, i_t$ 满足 $a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \cdots, a_{i_t}, b_{i_t}$ 是好序列. 输出 $t$ 的最大值以及对应的序列 $i_1, i_2, \cdots, i_t$. ## 输入输出格式 ### 输入格式 第一行包含一个整数 $n$, 即数对的个数. 后面 $n$ 行为数对, 每行包含一个数对 $(a_i, b_i)$. ### 输出格式 第一行输出 $t$, 即所求序列长度. 接着输出满足题意的序列 $i_1, i_2, \cdots, i_t$. ## 说明 ### 数据范围 $2 \leq n \leq 3 \cdot 10^5$ $1 \leq a_i, b_i \leq 2 \cdot n$ 并且所有 $a_i, b_i$ 两两不相等. ### 样例解释 样例 1: $1 < 7 > 3 < 5 > 2 < 10$. 样例 2: $6 > 1 < 3 > 2 < 5 > 4$.

题目描述

You are given $ n $ pairs of integers $ (a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n) $ . All of the integers in the pairs are distinct and are in the range from $ 1 $ to $ 2 \cdot n $ inclusive. Let's call a sequence of integers $ x_1, x_2, \ldots, x_{2k} $ good if either - $ x_1 < x_2 > x_3 < \ldots < x_{2k-2} > x_{2k-1} < x_{2k} $ , or - $ x_1 > x_2 < x_3 > \ldots > x_{2k-2} < x_{2k-1} > x_{2k} $ . You need to choose a subset of distinct indices $ i_1, i_2, \ldots, i_t $ and their order in a way that if you write down all numbers from the pairs in a single sequence (the sequence would be $ a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \ldots, a_{i_t}, b_{i_t} $ ), this sequence is good. What is the largest subset of indices you can choose? You also need to construct the corresponding index sequence $ i_1, i_2, \ldots, i_t $ .

输入输出格式

输入格式

The first line contains single integer $ n $ ( $ 2 \leq n \leq 3 \cdot 10^5 $ ) — the number of pairs. Each of the next $ n $ lines contain two numbers — $ a_i $ and $ b_i $ ( $ 1 \le a_i, b_i \le 2 \cdot n $ ) — the elements of the pairs. It is guaranteed that all integers in the pairs are distinct, that is, every integer from $ 1 $ to $ 2 \cdot n $ is mentioned exactly once.

输出格式

In the first line print a single integer $ t $ — the number of pairs in the answer. Then print $ t $ distinct integers $ i_1, i_2, \ldots, i_t $ — the indexes of pairs in the corresponding order.

输入输出样例

输入样例 #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

说明

The final sequence in the first example is $ 1 < 7 > 3 < 5 > 2 < 10 $ . The final sequence in the second example is $ 6 > 1 < 3 > 2 < 5 > 4 $ .