Diversion
Spring 1944. Much of Belarus remains under German occupation, but the enemy is troubled by a well-organized partisan movement.
Recently, a message from the commander's headquarters announced that the Soviet army is planning a major offensive, codenamed "Bagration." The message emphasizes the importance of the partisan movement, requiring them to conduct a sabotage operation just before the offensive begins.
The partisans have identified all N cities in the occupied territory where enemy troops are stationed, along with A_i, the number of enemy soldiers in the i-th city. The Germans rely on railways for troop movements. A detailed railway map shows exactly M two-way railway tracks. Each track connects two cities, allowing travel in both directions. No two cities are connected by more than one railway. The partisans understand that for any two cities S and F (1 ≤ S, F ≤ N, S ≠ F), there is exactly one path connecting them. This means there is a unique sequence of cities P_1, P_2, …, P_K (possibly empty), such that there is a railway between S and P_1, a railway between P_K and F, and for each i from 1 to K - 1, a railway connects P_i and P_i+1.
The partisans have two explosive devices and aim to destroy two railways to hinder the rapid deployment of enemy troops to the offensive's focal point. Since they don't know the starting city of the offensive, they want to choose two railways such that, after the explosions, the maximum military potential of any resulting region is minimized.
A region is defined as a maximal set of cities where any two cities are connected by a route. The military potential of a region is the sum of A_i for all cities in that region. Initially, all N cities form one region.
Figure №1. Description of the second example.N = 5, M = 4.
Your task is to help the partisans determine which two railways to destroy so that the maximum military potential of the regions formed after the explosions is minimized.
Input
The first line of the input contains two integers N (3 ≤ N ≤ 100000) and M (2 ≤ M ≤ 1000000).
The second line contains exactly N integers A_i (1 ≤ A_i ≤ 10^9, ∑A_i ≤ 10^9)—the number of enemy soldiers in city i, separated by spaces.
The next M lines describe the railways between cities. Each line contains two integers X_i and Y_i (1 ≤ X_i, Y_i ≤ N, X_i ≠ Y_i), separated by a space, indicating the cities connected by a railway.
Output
The output should be a single line containing two numbers—the indices of the railways to be destroyed, minimizing the maximum military potential of the resulting regions. The railways are numbered consecutively from 1 to M in the order they are provided. If multiple solutions exist, any valid solution is acceptable. The order of the railway numbers does not matter.