Sensor Network

Time limit2sMemory limit128 MB

Summary

Find the largest group of sensors where every pair lies within distance d and print its size and members.

Level: Hard8 of 10
Topics: Backtracking, Graph, Geometry
Solved: No attempts yet

Problem

Each sensor can communicate directly with sensors within Euclidean distance $d$ . Given $n$ sensor coordinates, find a largest set in which every pair can communicate directly.

Input

The first line has $n$ and $d$ ( $1 \le n \le 100$ , $1 \le d \le 10\,000$ ). The next $n$ lines give coordinates $x$ , $y$ for sensors $1$ through $n$ .

Output

Print the maximum set size on the first line. Print the sensor indices on the second line. Any optimal set is accepted.

Examples1

Example 1
Input
```
4 1
0 0
0 1
1 0
1 1
```
Expected output
```
2
1 2
```