도시 관광

몰도바에는 도시가 $N$개 있고 1번부터 $N$번까지 번호가 붙어 있다. 도시 사이는 양방향 도로로 이어져 있는데, 정부는 예산을 아끼려고 도로를 정확히 $N - 1$개만 놓았다. 그래도 어느 두 도시 사이든 도로를 따라 오갈 수 있다.

법령에 따라 모든 도시에는 음이 아닌 정수인 아름다움 값이 하나씩 정해져 있다. $i$번 도시의 아름다움은 $a_i$이다. 서로 다른 두 도시의 아름다움이 같을 수도 있다.

여행자 기젤은 지금 1번 도시에 있다. 아름다운 도시를 많이 보고 싶지만 시간이 모자라고 결정을 잘 내리지 못한다. 몰도바에 $K$일 더 머무르며 하루에 도시를 하나씩 방문한다. $i$일째에는 전날 도착한 도시 $x$에서 출발하고(첫날이면 $x = 1$이다), $a_y - d(x, y)$가 최대인 도시 $y$($y \ne x$)를 찾는다. 여기서 $d(x, y)$는 $x$에서 출발해 $y$에 도착할 때까지 지나야 하는 도로의 최소 개수이다. 최댓값을 만드는 도시가 여럿이면 번호가 가장 작은 도시를 고른다. 기젤은 $y$로 이동해 그날 남은 시간을 그곳에서 보내고, 다음 날 같은 규칙을 다시 적용한다.

$K$일째가 끝났을 때 기젤이 어느 도시에 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 수 $N$과 기젤이 머무르는 날수 $K$가 주어진다. 둘째 줄에 $N$개의 정수 $a_1, a_2, \dots, a_N$이 주어지며, $a_i$는 $i$번 도시의 아름다움이다. 다음 $N - 1$개 줄에는 두 정수 $u_i$와 $v_i$가 주어지고, $u_i$번 도시와 $v_i$번 도시를 잇는 양방향 도로가 있다는 뜻이다.

$K$일째가 끝났을 때 기젤이 있는 도시의 번호를 한 줄에 출력한다.

• $2 \le N \le 3 \times 10^5$
• $1 \le K \le 10^{18}$
• $0 \le a_i \le 10^9$
• $1 \le u_i, v_i \le N$
• $u_i \ne v_i$
• 도로 $N - 1$개는 모든 도시를 연결한다.

첫 번째 예제에서 기젤은 1일째에 1번 도시를 떠나 3번 도시로 가고, 2일째에 3번 도시에서 5번 도시로, 3일째에 5번 도시에서 2번 도시로 이동한다. 마지막 날인 4일째에는 2번 도시를 떠나 다시 5번 도시로 간다.