Arktik şəbəkə

Milli Müdafiə Nazirliyi (MMN) bir neçə şimal forpostunu simsiz şəbəkə ilə birləşdirmək istəyir. Şəbəkənin yaradılması üçün iki fərqli əlaqə texnologiyası istifadə olunacaq: hər bir forpostda radio qəbuledici olacaq və bəzi forpostlarda əlavə olaraq peyk kanalı olacaq.

Peyk kanalı olan istənilən iki forpost, yerləşdikləri yerdən asılı olmayaraq, peyk vasitəsilə əlaqə saxlaya bilərlər. Əks halda, iki forpost yalnız aralarındakı məsafə $d$-dən çox olmadıqda radio vasitəsilə əlaqə saxlaya bilər, bu isə qəbuledicilərin gücündən asılıdır. Daha yüksək güc daha böyük $d$ verir, lakin daha bahalıdır. Alış və texniki xidmət baxımından forpostlardakı qəbuledicilər eyni olmalıdır, yəni $d$ hər bir forpost cütü üçün eyni olmalıdır.

Sizin vəzifəniz qəbuledicilər üçün lazım olan minimal $d$-ni müəyyən etməkdir. Hər bir forpost cütü arasında ən azı bir əlaqə yolu (birbaşa və ya dolayı) olmalıdır.

Giriş verilənləri

Birinci sətir $n$ sayını ehtiva edir — testlərin sayı. Hər bir testin birinci sətiri peyk kanallarının sayı $s(1\le s\le 100)$ və forpostların sayı $p(s<p\le 500)$-ni ehtiva edir. Daha sonra $p$ sətir gəlir, burada hər bir forpostun $(x,y)$ koordinatları km ilə göstərilir (koordinatlar $0$-dan $10000$-ə qədər tam ədədlərdir).

Çıxış verilənləri

Hər bir hal üçün şəbəkəyə qoşulmaq üçün lazım olan minimal $d$-ni çıxış edin. Çıxış məlumatları $2$ ondalık dəqiqliklə göstərilməlidir.

Nümunələr