В одной отдалённой местности располагаются N
небольших деревень. Сотовая компания приняла решение обеспечить их сотовой
связью, для этого нужно построить приёмо-передающие станции. По техническим
причинам было принято решение размещать станции только в самих деревнях.
Радиус действия станций и координаты деревень известны.
Все деревни находятся на плоской равнине без препятствий для радиосигнала, то
есть радиус действия станции не зависит от места её установки. Если деревня
оказывается ровно на границе зоны действия какой-то станции, то считается, что
связь в ней есть.
Требуется обеспечить связью всех жителей, построив для
этого наименьшее количество станций.
В первой строке входного файла записаны через пробел
два целых числа: N (1 ≤ N ≤ 30) — количество деревень и R (1 ≤ R ≤ 1000) — радиус действия станций. В каждой из следующих
N строк записаны координаты очередной деревни в декартовой системе (два
целых числа x и y через пробел в диапазоне от 0 до 1000).
В первой строке выходного файла выведите целое число M
— минимальное количество станций, которое потребуется построить. В следующей
строке через пробел выведите M чисел — номера деревень, в которых нужно построить
станции. Нумерация деревень от 1 до N
в соответствии с порядком, в котором они
шли во входном файле.
Пример
|
Поток ввода
|
Поток вывода
|
|
4
50
10
10
500
500
501
501
999
999
|
3
1
3 4
|
