Hyperspace Disruption#3033
Year 3 ABY (After the Battle of Yavin). Much of the Outer Rim remains under Imperial occupation, but the Empire is troubled by a well-organized Rebel Alliance resistance.
Recently, a transmission from the Rebel Command announced that the Alliance fleet is planning a major offensive against Imperial forces. The message emphasizes the importance of the resistance cells, requiring them to carry out a sabotage operation on the hyperspace network just before the offensive begins.
The Rebels have identified all star systems in the occupied area where Imperial forces are stationed, and for each , they know A_i, the number of Imperial troops stationed in the -th system. The Empire relies on hyperspace routes for rapid troop deployment. A detailed star map shows exactly bidirectional hyperspace lanes. Each lane connects two star systems, allowing travel in both directions. No two systems are connected by more than one hyperspace lane. The Rebels are well aware of the Empire's pragmatism: for any two systems and (1 \leq S, F \leq N, S \neq F), there is exactly one hyperspace path between and . That is, there is a unique sequence of systems P_1, P_2, \ldots, P_K (possibly empty), such that there is a hyperspace lane between and P_1, a lane between P_K and , and for each from to K - 1, a lane connects P_i and P_{i+1}.
The Rebels have two ion disruptive charges, which they want to use to disable two hyperspace lanes and prevent the rapid deployment of Imperial troops to the center of the offensive. The Rebels do not know from which system the Alliance attack will begin, so they want to choose two lanes so that, after the disruptions, the maximum military strength of any resulting sector is minimized.
A sector is defined as a maximal set of star systems such that any two systems in this set are connected by hyperspace routes. The military strength of a sector is the sum of A_i for all systems within that sector. Initially, all systems form a single sector.
Figure №1. Description of the second example. N = 5, M = 4.
Your task is to help the Rebels determine which two hyperspace lanes to disable so that the maximum military strength of the resulting sectors after the disruptions is minimized.
The first line of the input contains two integers (3 \leq N \leq 100000) and (2 \leq M \leq 1000000).
The second line contains exactly integers A_i (1 \leq A_i \leq 10^9, \sum A_i \leq 10^9)—the number of Imperial troops in system , separated by spaces.
The next lines describe the hyperspace lanes between systems. Each line contains two integers X_i and Y_i (1 \leq X_i, Y_i \leq N, X_i \neq Y_i), separated by a space, which are the indices of the systems connected by the hyperspace lane.
The output should be a single line containing two numbers—the indices of the hyperspace lanes to be disabled, minimizing the maximum military strength of the resulting sectors. The lanes are numbered consecutively from to in the order they are provided. If multiple solutions exist, output any of them. The order of the lane numbers does not matter.
Example 1
Example 2