ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1824. Ифрит-бомбардировки

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
За шесть с половиной лет, прошедших после первых экспериментальных джинн-бомбардировок, Питирим Шварц достиг значительных успехов. Его новейшая разработка — бутылка с ифритом — предназначена специально для бомбардировки крупных городов. С помощью нескольких таких бутылок можно, например, стереть с лица земли все n крупных городов соседнего государства… Увы, бутылок с ифритами у Питирима совсем немного, поэтому он поручил программисту Привалову вычислить минимальное количество бутылок, необходимое для уничтожения всех n городов.
Для удобства прицеливания планируется сбрасывать бутылки только непосредственно на города. Ифрит разрушает все города, находящиеся на расстоянии не более r от точки падения бутылки. Радиус поражения столь велик, что города можно считать точками на плоскости.

Исходные данные

В первой строке записаны целые числа n и r (1 ≤ n ≤ 30; 1 ≤ r ≤ 1000). В i-й из следующих n строк записаны координаты i-го города — два целых числа в пределах от 0 до 1000.

Результат

В первой строке выведите минимальное количество бутылок с ифритами, необходимых для разрушения всех городов. В следующей строке через пробел выведите номера городов, на которые нужно сбросить эти бутылки. Если существует несколько способов сбросить бутылки, можно вывести любой из них.

Пример

исходные данныерезультат
4 50
10 10
500 500
501 501
999 999
3
1 3 4
Автор задачи: Игорь Андрианов
Источник задачи: XII открытое личное первенство УрГУ (19 марта 2011)