CF1148D Dirty Deeds Done Dirt Cheap

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.

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 $ .