Arktik şəbəkə#10203
Milli Müdafiə Nazirliyi (MMN) şimal forpostlarını vahid simsiz şəbəkədə birləşdirməyi planlaşdırır. Şəbəkənin qurulması üçün iki fərqli əlaqə texnologiyası istifadə edilməlidir: hər bir forposta radioqəbuledici quraşdırılacaq və onlardan bəziləri əlavə olaraq peyk kanalı alacaq.
Peyk kanalı olan istənilən iki avanpost arasında peyk üzərindən məsafədən asılı olmadan əlaqə qurula bilər. Əks halda, iki avanpost arasında yalnız o halda radio vasitəsilə məlumat mübadiləsi aparıla bilər ki, onların arasındakı məsafə transiverlərin gücündən asılı olan -dən artıq olmasın. Güc nə qədər yüksək olsa, dəyəri də bir o qədər böyükdür, lakin bu halda avadanlığın dəyəri də artır. İqtisadi və əməliyyat səbəblərinə görə bütün transiverlər eyni olmalıdır, yəni bütün forpostlar üçün dəyəri eyni olmalıdır.
Birbaşa və ya digər forpostlar arasında əlaqə zənciri ilə, istənilən iki avanpost arasında əlaqəni təmin edə biləcək minimal dəyərini tapmaq lazımdır.
Birinci sətir testlərin sayı -ni ehtiva edir. Hər bir testin ilk sətirində peyk kanallarının sayı s~(1 \le s \le 100) və avanpostların sayı p~(s < p \le 500) verilmişdir. Daha sonra hər biri müvafiq forpostun koordinatlarını '(x, y)' (kilometrlə, -dan -ə qədər tam ədədlər) göstərən sətir gəlir.
Hər bir test üçün bütün avanpostları şəbəkədə birləşdirmək üçün tələb olunan minimal dəyərini çıxarın. Nəticə iki ondalık dəqiqliklə çıxarılmalıdır.
Nümunə 1