Hiperməkan pozulması

3-cü il ABY (Yavin Döyüşündən Sonra). Xarici Halqanın böyük bir hissəsi hələ də İmperiya işğalı altındadır, lakin İmperiya yaxşı təşkil olunmuş Üsyançı Alyansının müqaviməti ilə narahatdır.

Yaxınlarda, Üsyançı Komandanlığından bir ötürmə Alyans donanmasının İmperiya qüvvələrinə qarşı böyük bir hücum planlaşdırdığını bildirdi. Mesajda müqavimət hüceyrələrinin əhəmiyyəti vurğulanır, onlardan hücum başlamazdan az əvvəl hiperfəz şəbəkəsində sabotaj əməliyyatı keçirmələri tələb olunur.

Üsyançılar, işğal olunmuş ərazidə İmperiya qüvvələrinin yerləşdiyi bütün $N$ ulduz sistemlərini müəyyən ediblər və hər bir $i$ üçün A_i dəyəri, $i$-ci sistemdə yerləşən İmperiya əsgərlərinin sayını bilirlər. İmperiya, qoşunların tez yerləşdirilməsi üçün hiperfəz yollarından istifadə edir. Ətraflı ulduz xəritəsində dəqiq olaraq $M$ ikitərəfli hiperfəz xəttinin olduğu göstərilib. Hər bir xətt iki ulduz sistemini birləşdirir və hər iki istiqamətdə hərəkət etmək mümkündür. Heç bir iki sistemi birdən çox hiperfəz xətti birləşdirmir. Üsyançılar İmperiyanın praqmatizmini yaxşı bilirlər: istənilən iki $S$ və $F$ sistemi üçün (1 \leq S, F \leq N, S \neq F) aralarında dəqiq bir hiperfəz yolu var. Yəni, P_1, P_2, \ldots, P_K (ola bilsin boş) ardıcıllığı var ki, $S$ və P_1, P_K və $F$ arasında, həmçinin $1$-dən K-1-ə qədər olan hər bir $i$ üçün P_i və P_{i+1} arasında hiperfəz xətti mövcuddur.

Üsyançıların iki ion pozucu yükləri var və onlar bu yüklərdən istifadə edərək iki hiperfəz xəttini sıradan çıxarmaq və İmperiya qoşunlarının hücumun mərkəzinə tez bir zamanda çatmasının qarşısını almaq istəyirlər. Üsyançılar Alyans hücumunun hansı sistemdən başlayacağını bilmədiklərindən, iki xətti elə seçmək istəyirlər ki, kəsmələrdən sonra yaranan sektorların maksimal hərbi gücü mümkün qədər az olsun.

Bir sektor — hiperfəz yolu ilə istənilən iki sistemi arasında əlaqə olan, maksimal ulduz sistemi çoxluğudur. Sektorun hərbi gücü, həmin sektora daxil olan bütün sistemlər üçün A_i cəminə bərabərdir. Başlanğıcda bütün $N$ sistem bir sektoru təşkil edir.

Şəkil №1. İkinci nümunənin izahı. N = 5, M = 4.

Sizin vəzifəniz — Üsyançılara hansı iki hiperfəz xəttini sıradan çıxarmaq lazım olduğunu tapmaqda kömək etməkdir ki, kəsmələrdən sonra yaranan sektorların ən böyük hərbi gücü mümkün qədər az olsun.