Dağların möhkəm bağlı oğlu
Eldar Boqdanov, dağların şanlı oğlu, güclü bir adamdır. Lakin o, İvan Metelskiyə verdiyi sözə görə 2011 Qış Məktəbində gününü yüksək səviyyədə keçirməlidir. Üstəlik, onun tədris etdiyi nəzəri materiallardan biri güclü bağlılıq komponentləri idi və burada Snark adlı birisi gözlənilmədən "İki Paytaxtın Qran-Prisi"ni keçirməyi təklif etdi, bu da Eldarı daha da bağladı.
Belə bir bağlılıqdan Eldar daha da güclü olur və növbəti tapşırığın həllinə daha da həvəslə girişir:
Verilmişdir n zirvəli və m_1 qollu istiqamətli qraf. Məlumdur ki, qrafda s və t zirvələri var ki, s-dən bütün zirvələrə çatmaq mümkündür və bütün zirvələrdən t-yə çatmaq mümkündür. Həmçinin eyni zirvələr çoxluğunda m_2 elementdən ibarət olan başqa bir qollar çoxluğu verilib. Bu çoxluqdakı qollara bəzi tam ədədi ağırlıqlar təyin olunub.
Qrafa ikinci çoxluqdan bəzi qollar əlavə etmək lazımdır ki, aşağıdakı tələblər yerinə yetirilsin:
əlavə edilmiş qollarla qraf güclü bağlı olmalıdır (hər bir zirvədən hər birinə çatmaq mümkün olmalıdır),
əlavə edilmiş qolların ümumi ağırlığı minimal olmalıdır.
Eldar, İvan, Snark və gələcəkdə keçiriləcək İki Paytaxtın Qran-Prisi ilə əlaqələrə çox bağlı olduğu üçün, bu tapşırığı həll etməyi sizə təklif edir və hər hansı bir halda ona tapşırığın həllinin mövcudluğu barədə məlumat verməyinizi, həll mövcud olduqda isə hesablamanızı və daha bir neçə şeyi etməyinizi təklif edir...
Giriş verilənləri
Birinci sətirdə tam ədəd n (1 ≤ n ≤ 100000) verilib. İkinci sətirdə tam qeyri-mənfi ədəd m_1 verilib. Sonra m_1 sətirdə verilmiş qrafın qollarının təsvirləri verilib. Hər bir qol başlanğıc və son nömrələri ilə təyin olunur. Növbəti sətirdə tam qeyri-mənfi ədəd m_2 verilib. Sonra m_2 sətirdə əlavə edilə bilən qolların təsvirləri verilib. Hər bir qol başlanğıc və son nömrələri və öz ağırlığı ilə - -10^9 ilə 10^9 arasında tam ədəd ilə təyin olunur. Məlumdur ki, 0 ≤ m_1 + m_2 ≤ 500000.
Çıxış verilənləri
Birinci sətirdə məsələnin həllinin mövcudluğuna görə "YES" və ya "NO" çıxarın. Əgər həll mövcuddursa, üç sətir çıxarın. Birincisində əlavə edilmiş qolların ümumi ağırlığını çıxarın. İkincisində əlavə edilmiş qolların sayını çıxarın. Sonra ayrı-ayrı sətirlərdə əlavə edilmiş qolların nömrələrini çıxarın. Qollar giriş faylında göstərildiyi sırada birdən başlayaraq nömrələnir. Hər bir əlavə edilmiş qolu dəqiq bir dəfə çıxarmaq lazımdır.