Задача №111140. Диверсия
Партизаны обладают двумя взрывными устройствами, которые они хотят использовать для подрыва двух железных дорог, чтобы предотвратить быструю переброску вражеских войск в очаг наступления. Партизанам неизвестен город, с которого начнется наступление, поэтому они хотят выбрать такие две железные дороги, чтобы в результате взрыва максимальное значение военного потенциала всех образовавшихся после взрыва регионов было минимальным.
Регионом будем называть такое максимальное по включению множество городов, что для любых двух городов из данного множества существует маршрут, связывающий их. Военным потенциалом региона будем называть сумму Ai для всех городов, входящих в данный регион. Вначале все N городов образуют один регион.
Ваша задача – помочь партизанам определить такие две железные дороги, взорвав которые максимальное значение военного потенциала получившихся в результате взрыва регионов было минимальным.
Первая строка входного файла содержит два целых числа N (3 ≤ N ≤ 100 000) и M (2 ≤ M ≤ 1000 000) соответственно. Вторая строка содержит ровно N целых чисел Ai (1 ≤ Ai ≤ 10^9, ∑Ai ≤ 10^9) – количество вражеских солдат в городе i, числа разделены одиночными пробелами. Следующие M строк описывают железные дороги между городами. Каждая строка содержит два целых числа Xi и Yi (1 ≤ Xi, Yi ≤ N, Xi ≠ Yi), разделенных одиночным пробелом, где Xi и Yi – это номера городов, связанных железной дорогой.
Первая и единственная срока выходного файла должна содержать два числа – номера железных дорог, взорвав которые максимальное значение военного потенциала получившихся после взрывов регионов будет минимально. Дороги нумеруются последовательно от 1 до M в порядке их ввода. Если существует несколько решений, то выведете любое из них. Порядок вывода номеров дорог не имеет значения.
4 3 1 1 2 2 2 4 1 2 3 1
3 1
5 4 10 20 20 30 30 1 2 4 1 1 3 3 5
2 4