Арктична мережа#10203

Арктична мережа

1 секунда

128 мегабайтів

Дуже легка

Міністерство національної оборони (МНО) планує з'єднати кілька північних форпостів у єдину бездротову мережу. Для побудови мережі повинні використовуватися дві різні технології зв'язку: кожна застава буде оснащена радіоприймачем, а деякі з них додатково отримають супутниковий канал.

Будь-які два аванпости, що мають супутниковий канал, можуть зв'язуватися між собою через супутник, незалежно від відстані між ними. В іншому випадку два аванпости можуть обмінюватися даними по радіо тільки у тому разі, якщо відстань між ними не перевищує $d$ , що залежить від потужності трансиверів. Чим вища потужність, тим більше значення $d$ , проте вартість обладнання при цьому також зростає. З економічних та експлуатаційних міркувань усі трансивери повинні бути однаковими, тобто значення $d$ повинно бути однаковим для всіх пар форпостів.

Необхідно визначити мінімальне значення $d$ , при якому забезпечується зв'язок між будь-якими двома аванпостами — напряму або через інші застави (по ланцюгу з'єднань).

Вхідні дані

Перший рядок містить кількість тестів $n$ . У першому рядку кожного тесту вказані кількість супутникових каналів $s (1 \leq s \leq 100)$ s~(1 \le s \le 100) та кількість аванпостів $p (s < p \leq 500)$ p~(s < p \le 500). Далі слідують $p$ рядків, кожен з яких містить координати $(x, y)$ відповідної застави у кілометрах (цілі числа від $0$ до $10000$ ).

Вихідні дані

Для кожного тесту виведіть мінімальне значення $d$ , необхідне для з'єднання всіх аванпостів у мережу. Результат слід вивести з точністю до двох десяткових знаків.

Приклади

Приклад 1