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 Pi of the city.
One of the N cities will become the region's cultural capital. This will be decided by the following properties:
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:
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.
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 Pi in order, separated by spaces(1 ≤ Pi ≤ 100 000). Next N – 1 lines contain two numbers i and j that specify cities that are connected by direct roads.
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.
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|