In the country of Nocrae, there exists villages, the th of which contains people. The Nocraean villages are connected to each other by roads of length such that it is possible to reach any village from any other village while only using these roads. The villages wish to establish a meeting place where all of the villagers can meet up. Knowing that any single village might be too far for some people to go to, the villages decided to choose two distinct villages as meeting places for the villagers to meet up. The inconvenience of each villager is defined to be the distance between his village and the closer of the two meeting places. The villagers want to know the minimum possible total inconvenience that is achievable.
Constraints
In all subtasks,
Subtask 1 [10%]
Subtask 2 [10%]
The number of roads going to or from each village is at most .
Subtask 3 [30%]
Subtask 4 [50%]
No additional constraints.
Input Specification
The first line contains one integer, .
The next line contains space-separated integers, .
lines follow, each one containing two space-separated integers, and , describing the road connecting the th and th villages.
Output Specification
Output one integer, the minimum possible total inconvenience.
Sample Input 1
Copy
7
3 2 1 3 2 1 3
1 3
2 4
3 5
4 6
1 7
6 5
Sample Output 1
Copy
11
Explanation for Sample Output 1
A possible choice of meeting places is villages and . It is impossible to achieve an inconvenience lower than .
Sample Input 2
Copy
5
1 2 3 4 5
1 3
2 4
1 5
1 2
Sample Output 2
Copy
9
Explanation for Sample Output 2
A possible choice of meeting places is villages and . It is impossible to achieve an inconvenience lower than .
Comments