题目描述

在 Moldova 王国有 n 个用双向道路连接着的城市，编号为 1 到 n。为了节约开支，政府建了 n−1 条双向道路连接这些城市，使得任意两个城市之间可以互相到达。因为一条法令，这 n 个城市各自有着非负数的美化指数比如第 i 个城市的美化指数等于 ai​。不同的城市可能有着相同的美化指数。Gigel 来到了 Moldova 王国，且现在在第 1 个城市。他早就迫不及待地想要参观这些美丽的城市，但是因为时间有限，他犹豫着无法决定去哪些城市。他将在 Moldova 王国停留 k 天，每天他可以去参观一些城市。在第 i 天，他将会从前一天停留的城市 x 开始（如果 i=1，则 x=1)，前往另一个城市 y，而城市 y 是最大化 ay−d(x,y) 的城市(x=y)。其中 d(x,y) 是从城市 x 到城市 y 所需经过的最少的道路条数。如果有多个城市同时取得最大值，则选定编号最小的城市。然后第 i 天他会在城市 y 停留一整天。第二天他又会重复这一进程。Gigel 想要知道第 k 天他会在哪个城市停留一整天，于是他来请求你的帮助。

输入格式

第一行包含两个数字，城市的数量 n ，和 Gigel 参观城市的天数 k。

第二行包含 n 个用空格隔开的 n 个数字 ai​，ai​ 表示第 i 个城市的美化指数。

接下来的 n−1 行，每行包括两个数字 ui​,vi​，表示城市 ui​ 和城市 vi​ 之间有一条双向道路直接相连。

输出格式

输出第 k 天 Gigel 停留了一整天的城市编号。

5 4
1 1 3 2 4
1 2
1 3
2 4
2 5

5

样例说明

第一天，Gigel 将会离开城市 1 前往城市 3；

第二天，他将会离开城市 3 前往城市 5；

第三天，他将会离开城市 5 前往城市 2；

第四天，他将会离开城市 2 前往城市 5；

数据规模与约定

对于 100% 的数据，1≤n≤3×105,1≤k≤1018,0≤ai​≤109，保证城市间是联通的。