Village Sentiment Simulation

In country C there are \(N\) villages numbered from 1 to \(N\) and \(N-1\) bidirectional roads connecting them such that any village is reachable from any other (i.e. the villages form a tree). Initially, village \(i\) has a sentiment value \(A_i\).

There are \(M\) days of travel. On each day, the traveler S chooses to visit the village with the highest sentiment value. If there are multiple such villages, S chooses the one with the smallest index. Suppose on a day S visits village \(X\); then at the end of that day the sentiment values of all villages directly adjacent to \(X\) (i.e. those connected to \(X\) by a single road) are increased by 1. Note that village \(X\) itself does not get an increase that day because S spent the day there.

After \(M\) days, determine the village with the highest sentiment value. If there are multiple villages with the same highest sentiment value, output the one with the smallest index.

Input Format: The first line contains two integers \(N\) and \(M\). The second line contains \(N\) integers \(A_1, A_2, \ldots, A_N\). Each of the following \(N-1\) lines contains two integers \(U\) and \(V\) meaning there is a bidirectional road between villages \(U\) and \(V\>.

Output Format: Print a single integer: the index of the village with the highest sentiment value after \(M\) days (choosing the smallest index in case of ties).

inputFormat

The first line contains two space‐separated integers \(N\) and \(M\).
The second line contains \(N\) space‐separated integers \(A_1, A_2, \ldots, A_N\) representing the initial sentiment values for each village.
The next \(N-1\) lines each contain two space‐separated integers \(U\) and \(V\) indicating there is a bidirectional road between villages \(U\) and \(V\>.

outputFormat

Output a single integer representing the index of the village with the highest sentiment value after \(M\) days. If multiple villages tie for the highest sentiment, output the one with the smallest index.

sample

3 1
1 2 3
1 2
2 3

2