Порушення гіперпростору#3033
3 рік ПБЯ (Після битви при Явіні). Значна частина Зовнішнього кільця досі перебуває під окупацією Імперії, але Імперію турбує добре організований опір Альянсу повстанців.
Нещодавно передача з командного центру Повстанців оголосила, що флот Альянсу планує масштабний наступ проти сил Імперії. У повідомленні підкреслюється важливість дій осередків опору, які мають здійснити диверсію на гіперпросторовій мережі безпосередньо перед початком наступу.
Повстанці визначили всі зоряних систем у окупованому секторі, в яких розміщені сили Імперії, й для кожної відомо A_i — кількість імперських військ у -й системі. Імперія покладається на гіперпросторові траси для швидкого перекидання військ. Детальна зоряна карта містить рівно двонаправлених гіперпросторових ліній. Кожна лінія з'єднує дві зоряні системи, забезпечуючи рух в обидві сторони. Жодна пара систем не з'єднана більш ніж однією гіперпросторовою лінією. Повстанці усвідомлюють прагматичність Імперії: для будь-яких двох систем і (1 \leq S, F \leq N, S \neq F) існує рівно один гіперпросторовий шлях між і . Тобто існує єдина послідовність систем P_1, P_2, \ldots, P_K (можливо, порожня), така що існує гіперпросторова лінія між і P_1, лінія між P_K і , і для кожного від до K-1 існує лінія, що з'єднує P_i та P_{i+1}.
У повстанців є два іонних руйнівних заряди, які вони хочуть використати для знеструмлення двох гіперпросторових ліній з метою унеможливити швидке перекидання імперських військ до центру наступу. Повстанці не знають, з якої системи почнеться атака Альянсу, тому бажають вибрати такі дві лінії, щоб після диверсії максимальна військова сила будь-якого з утворених секторів була мінімальною.
Сектор — це максимальна сукупність зоряних систем, у якій будь-які дві системи цієї множини з'єднані гіперпросторовими шляхами. Військовою силою сектора є сума A_i для всіх систем цього сектора. Спочатку всі систем утворюють один сектор.
Рисунок №1. Опис другого прикладу. N = 5, M = 4.
Ваше завдання — допомогти повстанцям визначити, які дві гіперпросторові лінії слід вивести з ладу, щоб мінімізувати максимальну військову силу отриманих секторів після диверсії.
Перший рядок містить два цілих числа (3 \leq N \leq 100000) і (2 \leq M \leq 1000000).
Другий рядок містить рівно цілих чисел A_i (1 \leq A_i \leq 10^9, \sum A_i \leq 10^9) — кількість імперських військ у системі , розділені пробілами.
Далі у наступних рядках описані гіперпросторові лінії між системами. Кожен рядок містить два цілих числа X_i та Y_i (1 \leq X_i, Y_i \leq N, X_i \neq Y_i), розділені пробілом, — індекси систем, які з'єднує ця гіперпросторова лінія.
Виведіть в одному рядку два числа — номери гіперпросторових ліній, які треба вивести з ладу, мінімізуючи максимальну військову силу сектора після диверсії. Лінії пронумеровані послідовно від до в порядку їх задання. Якщо існує кілька розв'язків, виведіть будь-який з них. Порядок номерів ліній не має значення.
Приклад 1
Приклад 2