当前没有测试数据。

题目描述

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

输入格式

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

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

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

输出格式

输出第 $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 \le n \le 3\times 10^5, 1 \le k \le 10^{18}, 0 \le a_i \le 10^9$，保证城市间是联通的。