Avtomagistrallar
Ostrov dövləti Flatopiya mükəmməl düz bir ərazidir. Təəssüf ki, Flatopiyada çox zəif bir avtomobil yolu sistemi mövcuddur. Flatopiya hökuməti bu problemi anlayır və artıq bəzi əsas şəhərləri birləşdirən bir sıra avtomagistrallar inşa edib. Lakin, hələ də şosse yolu ilə çatmaq mümkün olmayan bəzi şəhərlər var. Hər hansı bir şəhər cütlüyü arasında şosse sistemi daxilində hərəkət edə bilmək üçün daha çox avtomagistral inşa etmək lazımdır.
Flatopiya şəhərləri 1-dən n-ə qədər nömrələnmişdir və şəhər i-nin yerləşməsi Dekart koordinatları ilə (x[i], y[i]) verilir. Hər bir avtomagistral yalnız iki şəhəri birləşdirir. Bütün avtomagistrallar (həm ilkin, həm də planlaşdırılanlar) düz xətlər boyunca keçir, buna görə də onların uzunluğu şəhərlər arasındakı Dekart məsafəsinə bərabərdir. Bütün avtomagistrallar hər iki istiqamətdə istifadə edilə bilər. Avtomagistrallar sərbəst şəkildə kəsişə bilər, lakin sürücü yalnız hər iki avtomagistralın son nöqtəsində yerləşən şəhərdə avtomagistrallar arasında keçid edə bilər.
Flatopiya hökuməti yeni avtomagistralların tikinti xərclərini minimallaşdırmaq istəyir. Lakin, onlar əmin olmaq istəyirlər ki, hər bir şəhərə şosse yolu ilə çatmaq mümkündür. Flatopiya bu qədər düz olduğuna görə, avtomagistralın tikinti xərci həmişə onun uzunluğu ilə mütənasibdir. Beləliklə, ən ucuz avtomagistral sistemi, avtomagistralların ümumi uzunluğunu minimallaşdıran sistem olacaqdır.
Giriş məlumatları
Birinci sətir testlərin sayını ehtiva edir. Daha sonra boş bir sətir və boş sətirlərlə ayrılmış məlumat dəstləri gəlir. Hər bir test iki hissədən ibarətdir. Birinci hissədə ölkənin bütün şəhərləri, ikinci hissədə isə əvvəlcədən tikilmiş avtomagistrallar təsvir edilir.
Hər bir testin birinci sətiri şəhərlərin sayını n (1 ≤ n ≤ 750) ehtiva edir. Növbəti n sətirin hər biri x[i] və y[i] - i-ci şəhərin koordinatlarını (burada i 1-dən n-ə qədər) ehtiva edən iki tam ədəd ehtiva edir. Koordinatların mütləq qiyməti 10000-dən çox deyil. Hər bir şəhər unikal bir yerləşməyə malikdir.
Növbəti sətir mövcud avtomagistralların sayını m (0 ≤ m ≤ 1000) ehtiva edir. Növbəti m sətirin hər biri artıq avtomagistralla birləşdirilmiş şəhər nömrələrinin bir cütünü ehtiva edir. Hər bir şəhər cütü ən çox bir avtomagistralla birləşdirilir.
Çıxış məlumatları
Hər bir test üçün bütün şəhərləri minimal mümkün yeni avtomagistralların ümumi uzunluğu ilə birləşdirmək üçün inşa edilməli olan hər yeni avtomagistral üçün bir sətir çıxarın. Hər bir avtomagistral, onu birləşdirən şəhərlərin nömrələri ilə, boşluqla ayrılmış şəkildə təqdim edilməlidir.
Əgər yeni avtomagistrallar inşa etmək lazım deyilsə (bütün şəhərlər artıq birləşdirilibsə), "No new highways need" cümləsini çıxarın.
Ayrı-ayrı testlər arasında bir boş sətir çıxarmaq lazımdır.