Description

Taro has a special rabbit that has only a left eye, so when it moves it cannot make right turns. One day, Taro plays a game with the one-eyed rabbit. Taro places $n$ carrots on the plane, with each carrot at position $(x_i, y_i)$, and all $x_i$ are distinct and all $y_i$ are distinct. The rabbit is going to eat these carrots.

Let carrot $A(x_i, y_i)$ be the carrot with the smallest $x$-coordinate among all carrots. Then the rabbit will start from $(0, y_i)$, head to carrot $A$, and then start eating carrots. After it finishes a carrot, the rabbit will choose the next carrot as its target and go straight to it; of course, while moving, it cannot make right turns. The rabbit also leaves a special smell along its path, so it does not want the path it is about to take to intersect the path it has already traveled. Taro wants to know how the rabbit can eat the maximum number of carrots.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers. The $(i+1)$-th line gives the position of carrot $i$, $(x_i, y_i)$.

Output Format

Output one line: first output the maximum number of carrots the rabbit can eat, then output the order in which it eats the carrots (by carrot indices from $1$ to $n$, space-separated).

10
4 5
9 8
5 9
1 7
3 2
6 3
10 10
8 1
2 4
7 6

10 8 7 3 4 9 5 6 2 1 10

Hint

• For 40% of the testdata, $n \le 100$.
• For 100% of the testdata, $n \le 1000$, $0 < x_i \le 10^4$, $0 < y_i \le 10^4$.

Translated by ChatGPT 5