Cellular communication#2003
In a remote region, there are small villages. A cellular company wants to provide these villages with mobile coverage by constructing transmission stations. For technical reasons, stations can only be installed in the villages themselves.
The coverage radius of each station and the coordinates of the villages are known. All villages are located on a flat plain with no obstacles to the radio signal, so the coverage radius of a station does not depend on its location. If a village lies exactly on the boundary of a station's coverage area, it is considered covered.
It is required to provide coverage to all residents by building the minimum number of stations.
The first line contains two integers separated by a space: (1 \leq N \leq 30) — the number of villages, and (1 \leq R \leq 1000) — the coverage radius of the stations. Each of the following lines contains the coordinates of a village in the Cartesian plane (two integers and separated by a space, both from to ).
In the first line, output a single integer — the minimum number of stations that must be built. In the second line, output numbers separated by spaces — the indices of the villages where the stations should be built. Villages are numbered from to in the order in which they appear in the input.
Example 1