Capital

In some far away region, there are N cities, connected by N – 1 bidirectional roads so that between any two cities there is one unique road (one direct road or one formed by several direct roads). For any city i it is known the population P_i of the city.

One of the N cities will become the region's cultural capital. This will be decided by the following properties:

• The capital has to be directly connected by at least two other cities.
• In order to stabilize the traffic on the roads entering the capital, the capital has to be the city for which the traffic on the incident edges has the smallest variation. The traffic on one edge is given by the total population which uses that edge to go to the capital. The variation is the maximum absolute difference between the values. For example:

City number 2 is the one to become the capital since it is directly connected by at least two other cities (4 in this case), and the population that will use the incident edges of city 2 is:

edge (2,1) : P1 + P8 = 2 + 4 = 6
edge (2,4) : P3 + P4 + P6 = 1 + 2 + 2 = 5
edge (2,5) : P5 = 5
edge (2,7) : P7 = 6


The absolute variation is 6 – 5 = 1 and there is no other city with smaller variation.

Given the region defined by cities, population, and roads, find the city that will become capital, according to the requirements and also the traffic variation for that city.

Input Specification

The input contains on the first line N, the number of cities (3 ≤ N ≤ 20 000). On the second line there are N numbers, the values P_i in order, separated by spaces(1 ≤ P_i ≤ 100 000). Next N – 1 lines contain two numbers i and j that specify cities that are connected by direct roads.

Output Specification

The output will contain only one line with two numbers separated by space: the index of the city that will become the capital and the smallest variation between the values of the traffic on the incident edges of the capital. If there are multiple cities that can become capital (with minimum variation), print the one with the smallest index.

Sample Input

1. 8
2. 2 5 1 2 5 2 6 4
3. 3 4
4. 6 4
5. 4 2
6. 7 2
7. 2 5
8. 1 8
9. 2 1

download as text file

Output for Sample Input

1. 2 1

download as text file