Minimal xərcli axın#3393
Köhnə bir zavod binasında iki nöqtə arasında suyun daşınması sistemini qurmaq üçün köhnə santexnika detallarından istifadə etməyiniz tələb olunur. Bu detallar borular və birləşmələrdən ibarətdir. Birləşmələr, boruların əvvəllər birləşdiyi nöqtələrdir. "Əvvəllər" deyirik, çünki bəzi köhnə borular zədələnmiş və məhv olmuş, nəticədə birləşmələrdə açıq deliklər qalmışdır. Əgər su bu birləşmələrdən birinə daxil olarsa, o, xaricə çıxacaq və binanı su basacaq ki, bu da arzuolunmazdır.
Bu vəziyyəti açıq deliklər arasında yeni borular quraşdırmaqla və ya açıq delikləri bağlayan tıxaclar quraşdırmaqla düzəldə bilərsiniz. İki deliyi birləşdirən yeni boru quraşdırıldıqdan sonra (hansı ki, onlar iki fərqli birləşməyə aid olmalıdır), bu deliklər artıq açıq deyil və su yeni borudan keçə bilər. Yeni borunun quraşdırılma dəyəri, bu borunun birləşdirdiyi iki birləşmənin mərkəzləri arasındakı məsafəyə bərabərdir. Açıq delikdə tıxac quraşdırma dəyəri 0.5-ə bərabərdir. Su heç vaxt çatmayacaq birləşmələrdəki açıq deliklərdən narahat olmamalısınız.
İki birləşmə xüsusi hesab olunur. Biri mənbə adlanır - suyun sistemə daxil olduğu nöqtə. Digəri isə axar adlanır - suyun daxil olması lazım olan nöqtə. Yeni borular və tıxaclar quraşdırıldıqdan sonra su nasoslarla mənbəyə kifayət qədər təzyiq altında vurulacaq (əgər təbii ki, sızma yoxdursa). Siz təzyiqi istədiyiniz kimi seçə bilərsiniz və sistem işləyərkən onu dəyişməməlisiniz. Təbii ki, təzyiq mənbə və axarın hündürlüyünə qədər suyu qaldırmaq üçün kifayət qədər olmalıdır. Sizin vəzifəniz suyu mənbədən axara ən ucuz şəkildə çatdırmaqdır, binanı su basmadan.
Aşağıdakı şəkil birinci testə uyğundur, burada qara nöqtələr açıq deliklərə uyğundur, birləşmə 1 mənbə, birləşmə 7 isə axardır (dairələrdəki qara nöqtələrin mövqeləri əhəmiyyət daşımır və yalnız təsvir üçün istifadə olunur).
Sistemdə su fizika qanunlarına uyğun olaraq axır. Əgər təzyiq birləşməni doldurmaq üçün kifayətdirsə, birləşmə su ilə dolu qalır. Əgər su ilə dolu birləşmədən üfüqi borular və ya aşağıya doğru gedən borular çıxırsa, su bu borularla axacaq. Su təzyiqdən asılı olaraq borularla yuxarıya da axa bilər. Əgər su birləşmədəki açıq deliklərə çatarsa, binanı su basacaq.
Birinci testdə siz 1 və 5 düyünlərini 3 dəyəri ilə birləşdirməli, 2 birləşməsindəki delikləri bağlamalı və təzyiqi yalnız 7 birləşməsinə qədər suyu qaldıracaq şəkildə tənzimləməlisiniz. Su 1, 2, 5, 6, 7 birləşmələrini dolduracaq və daha yuxarı qalxmayacaq. Digər (daha bahalı) həll yolu bütün delikləri 5 qiymətinə bağlamaq və suyun bütün birləşmələrdən axmasına icazə verməkdir. Problemi 1 və 6 düyünlərini boru ilə birləşdirərək və 2 və 5 birləşmələrindəki delikləri bağlayaraq həll etmək mümkün deyil, çünki 6 birləşməsində boru yerləşdirilə biləcək açıq delik yoxdur.
Mövcud boruların və hər hansı yeni boruların bir-birinə mane olmadığını və yalnız qoşulduqları birləşmələrlə kəsişdiyini düşünün. Yəni, hətta A və B birləşmələrini birləşdirən düz xətt C-dən keçsə belə, A və B arasında olan hər hansı bir boru C-yə toxunmur.
Hər testin ilk sətiri iki tam ədəd N və M ehtiva edir, burada N (2 ≤ N ≤ 400) - binadakı birləşmələrin sayı (1-dən N-ə qədər nömrələnmişdir) və M (0 ≤ M ≤ 50000) - istifadəyə yararlı mövcud boruların sayıdır. Növbəti N sətirin hər biri dörd tam ədəd x_i, y_i, z_i və k_i ehtiva edir, şərtlərə uyğun olaraq: -10000 ≤ x_i, y_i, z_i ≤ 10000 və 0 ≤ k_i ≤ 400, i = 1, 2, ..., N. i-ci sətir i-ci birləşməni təsvir edir: (x_i, y_i, z_i) - i-ci birləşmənin yerləşdiyi yer, burada Oz oxu şaquli yerləşir; k_i birləşmədəki açıq deliklərin sayını göstərir. Növbəti M sətirin hər biri iki tam ədəd a_j və b_j (1 ≤ a_j < b_j ≤ N) ehtiva edir. j-ci sətir j-ci borunun a_j və b_j düyünlərini birləşdirdiyini göstərir. Hər hansı bir birləşmə cütü arasında bir borudan çox ola bilməz, heç bir iki birləşmə eyni koordinatlara malik deyil. Mənbə 1-ci birləşmədir, axar isə N-ci birləşmədir.
Hər test üçün onun nömrəsini çıxış edin. Əgər tələb olunan boru və tıxac sistemini qurmaq mümkündürsə, mənbəni axara birləşdirmək üçün ən kiçik dəyəri dörd ondalık rəqəmlə çıxış edin. Əgər axtarılan birləşmə şəbəkəsi mövcud deyilsə, impossible sözünü çıxış edin.
Nümunə 1