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