Byteotian 洞穴由 $n$ 个房间和连接它们的 $n-1$ 条走廊组成。对于任意两个房间，都存在唯一的路径可以在不离开洞穴的情况下从一个房间到达另一个房间。某些房间内放置了炸药。每条走廊都铺设了导火索。在每个房间中，来自相邻走廊的导火索汇聚于一点，如果该房间内有炸药，导火索也会连接到炸药上。两个相邻房间之间的导火索燃烧需要正好一个单位时间，炸药会在火到达其所在房间的瞬间爆炸。

我们希望在 $m$ 个房间（导火索的连接点）点燃导火索，使得所有炸药在点火后能以最短的时间全部爆炸。编写一个程序来确定这个最短时间。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le m \le n \le 300,000$)，由一个空格分隔，分别表示洞穴中房间的数量以及可以点燃导火索的房间数量。房间编号从 $1$ 到 $n$。下一行包含 $n$ 个整数 $d_{1}, d_{2}, \dots, d_{n}$ ($d_{i} \in \{0, 1\}$)，由空格分隔。如果 $d_{i}=1$，则第 $i$ 个房间内有炸药；如果 $d_{i}=0$，则没有。接下来的 $n-1$ 行描述了洞穴的走廊。每行包含两个整数 $a, b$ ($1 \le a < b \le n$)，由一个空格分隔，表示连接房间 $a$ 和 $b$ 的走廊。每条走廊在描述中仅出现一次。

你可以假设在占总分 $10\%$ 的测试用例中，满足 $n \le 10$；在占总分 $40\%$ 的测试用例中，满足 $n \le 1,000$。

输出格式

标准输出的第一行且仅包含一个整数，表示从点燃导火索到所有炸药爆炸所需的最短时间。

样例

输入 1

7 2
1 0 1 1 0 1 1
1 3
2 3
3 4
4 5
5 6
5 7

输出 1

1

说明

对于样例输入：

我们在房间 3 和 5 点燃导火索。房间 3 中的炸药在零时刻爆炸，房间 1、4、6 和 7 中的炸药在一个单位时间后爆炸。