Dağların möhkəm bağlı oğlu

Eldar Boqdanov, dağların qürurlu oğlu, güclü bir insandır. Lakin onun Ivan Metelskiyə qarşı öhdəlikləri var və bunlar onun Qış Məktəbi 2011-də gününü yüksək səviyyədə keçirməsini təmin etməlidir. O öyrətdiyi nəzəri materiallar arasında güclü əlaqəli komponentlər mövzusu da var idi. Həyatda isə, Snark adlı gözlənilməz komponent ortaya çıxdı və o, "İki Paytaxtın Qran Prisi"ni keçirməyi təklif etdi, bu isə Eldarı əlavə məşğul etdi.

Bütün bu əlaqələrə baxmayaraq, Eldar aşağıdakı problemi həll etməyə daha da dərindən girişdi:

Sizə $n$ zirvədən və m_1 kənardan ibarət bir istiqamətli qraf verilir. Bilinir ki, elə zirvələr $s$ və $t$ mövcuddur ki, bütün zirvələr $s$-dən əlçatandır və $t$ isə bütün zirvələrdən əlçatandır. Bundan əlavə, bu zirvələr üzərində ikinci bir m_2 kənar dəsti verilmişdir. İkinci dəstdəki hər bir kənarın integer çəkisi var.

O kənarların bir qismini qrafa əlavə etməlisiniz ki, aşağıdakı şərtlər ödənsin:

• Əlavə etdiyiniz kənarlarla birlikdə qraf güclü əlaqəli olmalıdır (hər bir zirvədən digər istənilən zirvəyə yol olmalıdır).

• Əlavə etdiyiniz kənarların ümumi çəkiləri minimum olmalıdır.

Eldar öhdəlikləri ilə məşğul olduğu üçün sizdən bu problemi həll etməyinizi və həllin mövcud olub-olmadığı barədə ona məlumat verməyinizi xahiş edir. Əgər həll varsa, tələb olunan qiymətləri hesablayın.