Optimal Wish Route and Road Roller Minimization

Mr. S is responsible for a vast field represented as a 2D plane. There are (n) wish trees in the field, numbered (1,2,\dots,n). The (i)th tree is at coordinates ((x_i, y_i)) and no two trees share the same coordinates.

Mr. P starts at the origin ((0,0)) and drives in rounds. In each round, he chooses one of the following five directions: left ((-x) direction), right ((+x) direction), up ((+y) direction), up-left at (45^\circ) (i.e. moving such that (x) decreases and (y) increases with (x)‐decrease equal to (y)‐increase) and up‐right at (45^\circ) (i.e. moving such that (x) increases and (y) increases with the same amount). The rule is that he must choose a direction in which there is at least one tree on that ray that he has not yet visited, and he must drive along that ray until he reaches the closest unvisited tree. There he makes his wish and then proceeds with the next round. If no valid direction is available, his journey stops. Mr. P follows an optimal strategy so that he can visit as many trees as possible. (If there are more than one optimal strategy, any one may be chosen.)

Unfortunately, while driving Mr. P leaves tire tracks along his travel. A tire track is a line segment connecting the endpoints of a round – either from the origin to a tree or between two trees. The twist is that tracks corresponding to non‐horizontal moves (i.e. moves in the up, up-left (45^\circ), or up‐right (45^\circ) directions) are considered unsightly by Mr. S. In anticipation of many wishers following Mr. P with the same optimal strategy, Mr. S plans to hire some road rollers. Each road roller works in the following mode:

1. It may start from the origin or any tree.

2. It can only move in one of the three directions: up, up-left (45^\circ), or up-right (45^\circ); furthermore, it may only change direction or stop when it is at a tree.

3. It is only allowed to travel along those road segments that could possibly be part of an optimal driving route (i.e. segments corresponding to up, up-left, and up-right moves in some optimal strategy). Note that the same segment may be traversed by more than one road roller.

There are two tasks:

1. Provide Mr. P with an optimal route. In other words, output any route that begins at the origin and visits the maximum possible number of trees, where in each move the car goes in one of the five allowed directions and always stops at the nearest unvisited tree in that direction. (The output should list the indices of the trees visited in order.)

2. Tell Mr. S the minimum number of road rollers needed to cover all "possible unsightly" (i.e. non-horizontal) segments that might appear in an optimal route. A road roller can cover a contiguous chain of such segments (moving only in up, up-left and up-right directions, with direction changes only at trees).

For clarity, note that an edge (or segment) from point A ((x_A, y_A)) to B ((x_B, y_B)) is considered to be in a specific direction if:

• Left: (y_B=y_A) and (x_B<x_A) (choose the one with maximum (x_B)).
• Right: (y_B=y_A) and (x_B>x_A) (choose the one with minimum (x_B)).
• Up: (x_B=x_A) and (y_B>y_A) (choose the one with minimum (y_B)).
• Up-left: (x_A-x_B=y_B-y_A>0) (choose the one with minimum (y_B-y_A)).
• Up-right: (x_B-x_A=y_B-y_A>0) (choose the one with minimum (y_B-y_A)).

An edge is eligible for road rolling (i.e. it is "unsightly") if it is in one of the three directions: up, up-left, or up-right, and it may appear in some optimal route.

Your program should:

(1) Compute an optimal route from the origin (output the list of visited tree indices in order; do not include the origin).

(2) Collect the set (S) of all unsightly edges that can be part of an optimal route (that is, for any node A having an outgoing edge in an allowed upward direction to node B, if the transition is optimal then include it in (S)). Then, treat each road roller as being able to cover a contiguous chain of edges from (S) (i.e. a path in the directed graph induced by (S)) and determine the minimum number of chains needed to cover all of (S). This number is the minimum number of road rollers required.

Input and output formats are described below.

inputFormat

The first line contains a single integer \(n\) \((1 \le n \le 1000)\), the number of trees.

Each of the following \(n\) lines contains two space-separated integers \(x_i\) and \(y_i\) \((|x_i|,|y_i| \le 10^9)\) representing the coordinates of the \(i\)th tree. All tree coordinates are distinct.

outputFormat

On the first line, output an integer \(k\), the number of trees visited in an optimal route by Mr. P.

On the second line, output \(k\) space‐separated integers representing the indices of the trees (from the input order, 1-indexed) in the order they are visited.

On the third line, output a single integer – the minimum number of road rollers required by Mr. S.

sample

3
1 1
-1 0
0 2

1
2
2

</p>