403672: GYM101237 I Circle Clique

Do you think that nothing can really surprise you on a programming contest? Are you sure? Then how would you like this! Given a graph consisting of N vertices, find a maximal clique in it, where N is up to 5000!

... that's how the statement could look if this was "Robert Tarjan Contest". Unfortunately, it is only "MSU Trinity Contest", therefore we should add a bit more restrictions so that at least somebody could solve this problem.

You are given a disk of radius R with its center at the origin and N integer points outside that disk. Let us consider a graph on these points as vertices, where points A and B are connected by an edge if and only if the line AB does not intersect the disk.

Find the maximal clique in this graph.

The first line contains two integers N and R, the number of points and the radius of the disk respectively (1 ≤ N ≤ 2000, 1 ≤ R ≤ 5000).

The following N lines contain the coordinates of points in the form x_i y_i ( - 5000 ≤ x_i, y_i ≤ 5000).

It is guaranteed that all points are different, each point lies strictly outside the disk, and no two points lie on a common tangent line to the disk.

On the first line, print the size of the maximal clique. On the second line, print the numbers of points forming that clique. If there are several possible answers, print any one of them.

6 3
0 6
-7 -4
-3 -2
7 -5
-2 3
8 -3

4
1 2 6 4