БГУ Личное Первенство
Арктическая сеть
Министерство национальной обороны (МНО) хочет соединить несколько северных форпостов беспроводной сетью. При создании сети должны использоваться две различные технологии связи: каждая застава будет иметь радиоприемник, а некоторые заставы дополнительно будут иметь спутниковый канал.
Любые два аванпоста со спутниковым каналом могут связываться через спутник, независимо от их местоположения. В противном случае два аванпоста могут общаться по радио, только если расстояние между ними не превышает d, что зависит от мощности трансиверов. Чем выше мощность, тем выше d, но стоят они больше. По соображениям покупки и обслуживания трансиверы на заставах должныбыть идентичными; то есть значение d должно быть одинаковым для каждой пары форпостов.
Вам ледует определить наименьшее значение d, необходимое для трансиверов. Между каждой парой аванпостов должен быть хотя бы один канал связи (прямой или косвенный).
Вхідні дані
Первая строка содержит количество n тестов. Первая строка каждого теста содержит количество спутниковых каналов s (1 ≤ s ≤ 100) и количество аванпостов p (s < p ≤ 500). Далее следуют p строк, в которых указаны координаты (x, y) каждой заставы в км (координаты - целые числа от 0 до 10000).
Вихідні дані
Для каждого теста вывести минимальное d, необходимое для подключения к сети. Вывод следует совершить с точностью до 2 десятичных знаков.
Приклад
1 2 4 1 0 3 0 6 0 7 2
2.24