Diversiya
1944-cü ildir. Belarusiyanın əksər əraziləri hələ də alman-faşist işğalçıları tərəfindən işğal olunub. Lakin işğal olunmuş ərazilərdə belə, düşmənə qarşı yaxşı təşkil olunmuş partizan hərəkatı fəaliyyət göstərir.
Bir neçə gün əvvəl baş komandanın qərargahından bir mesaj alındı. Bu mesaja əsasən, sovet ordusu "Baqration" kod adı altında genişmiqyaslı hücum hazırlayır. Mesajda partizan hərəkatına böyük ümidlər bəsləndiyi və hücum ərəfəsində partizanlardan diversiya əməliyyatı keçirmələri tələb olunduğu bildirilir.
Partizanlar işğal olunmuş ərazidə düşmən qoşunlarının yerləşdiyi N şəhəri müəyyən ediblər və i-ci şəhərdəki düşmən əsgərlərinin sayını A_i olaraq bilirlər. Məlumdur ki, almanlar qoşunların daşınması üçün dəmir yolu əlaqəsindən istifadə edirlər. Dəmir yollarının dəqiq xəritəsi tərtib edilmişdir və bu xəritədə M ikitərəfli dəmir yolu (yol) mövcuddur. Hər bir dəmir yolu iki şəhəri birləşdirir. Əgər X şəhəri dəmir yolu ilə Y şəhəri ilə bağlıdırsa, bu yoldan istifadə edərək həm X şəhərindən Y-yə, həm də Y-dən X-ə getmək mümkündür. İstənilən iki şəhəri ən çox bir dəmir yolu birləşdirir. Partizanlara almanların praqmatikliyi yaxşı məlumdur, buna görə də istənilən iki S və F şəhəri üçün (1 ≤ S, F ≤ N, S ≠ F) S və F şəhərlərini birləşdirən dəqiq bir yol (marşrut) mövcuddur. Yəni, S və P_1 arasında dəmir yolu, P_K və F arasında dəmir yolu mövcuddur və hər hansı i üçün 1-dən K-1-ə qədər P_i və P_i+1 şəhərlərini birləşdirən dəmir yolu mövcuddur.
Partizanlar iki partlayıcı qurğuya malikdirlər və bu qurğuları iki dəmir yolunu partlatmaq üçün istifadə etmək istəyirlər ki, düşmən qoşunlarının hücum mərkəzinə sürətli daşınmasının qarşısını alsınlar. Partizanlara hücumun hansı şəhərdən başlayacağı məlum deyil, ona görə də onlar elə iki dəmir yolu seçmək istəyirlər ki, partlayış nəticəsində yaranan bölgələrin hərbi potensialının maksimum dəyəri minimal olsun.
Bölgə dedikdə, daxilindəki istənilən iki şəhər arasında marşrut olan şəhərlərin maksimum daxil olan çoxluğu nəzərdə tutulur. Bölgənin hərbi potensialı həmin bölgəyə daxil olan bütün şəhərlərin A_i cəmi ilə müəyyən edilir. Əvvəlcə bütün N şəhəri bir bölgə təşkil edir.
Şəkil №1. İkinci nümunənin təsviri.N = 5, M = 4.
Sizin vəzifəniz partizanlara elə iki dəmir yolu müəyyən etməyə kömək etməkdir ki, onları partlatdıqda yaranan bölgələrin hərbi potensialının maksimum dəyəri minimal olsun.
Giriş verilənləri
Giriş faylının ilk sətiri müvafiq olaraq iki tam ədəd N (3 ≤ N ≤ 100000) və M (2 ≤ M ≤ 1000000) ehtiva edir.
İkinci sətir dəqiq N tam ədəd A_i_{ }(1 ≤ A_i ≤ 10^9, ∑A_i_{ }≤ 10^9) ehtiva edir – i-ci şəhərdəki düşmən əsgərlərinin sayı, ədədlər tək boşluqla ayrılır.
Növbəti M sətir şəhərlər arasındakı dəmir yollarını təsvir edir. Hər bir sətir iki tam ədəd X_i və Y_i_{ }(1 ≤ X_i, Y_i ≤ N, X_i_{ }≠ Y_i), tək boşluqla ayrılmış, burada X_i və Y_i dəmir yolu ilə bağlı olan şəhərlərin nömrələridir.
Çıxış verilənləri
Çıxış faylının ilk və yeganə sətiri iki ədəd ehtiva etməlidir – partladıqda yaranan bölgələrin hərbi potensialının maksimum dəyəri minimal olacaq dəmir yollarının nömrələri. Yollar daxilolma sırasına görə 1-dən M-ə qədər nömrələnir. Bir neçə həll varsa, onlardan birini çıxarın. Yolların nömrələrinin çıxış sırası əhəmiyyət daşımır.