题目背景

矿山深处有一片互相连通的洞窟群，部分洞窟里存放着待销毁的废旧炸药。安全员计划同时在若干个洞窟点燃引线，让所有炸药尽早起爆，请你帮他计算理论上能达到的最短时间。

题目描述

矿洞由 $n$ 个洞窟和连接它们的 $n-1$ 条巷道组成，任意两个洞窟之间有且仅有一条不离开矿洞的通路。

部分洞窟中存放着炸药，每条巷道内都铺设有引线。在每个洞窟中，与之相连的巷道的引线汇聚于一点，并连接到这个洞窟里的炸药（如果有的话）。引线在两个相邻洞窟之间燃尽恰好需要 $1$ 个单位时间，火焰到达某个洞窟时，里面的炸药会立即爆炸。

我们希望在 $m$ 个洞窟（引线的汇聚点）同时点燃引线，使得所有炸药都能爆炸，且从点燃到全部炸药爆炸的时间尽可能短。请计算这个最短的可能时间。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 300\ 000$），用一个空格分隔，分别表示洞窟数量和可以点燃引线的洞窟数量。

洞窟从 $1$ 到 $n$ 编号。

下一行包含 $n$ 个整数 $d_1,d_2,\cdots,d_n$（$d_i \in \{0,1\}$），用空格分隔。$d_i=1$ 表示第 $i$ 个洞窟中有炸药，$d_i=0$ 表示没有。接下来的 $n-1$ 行每行包含两个整数 $a,b$（$1 \le a \lt b \le n$），表示有一条巷道连接洞窟 $a$ 和 $b$。每条巷道恰好出现一次。

输出格式

输出一行一个整数，表示从点燃引线到所有炸药爆炸所需的最短时间。

样例

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

1

提示

对于 $10\%$ 的数据，$1 \le n \le 10$。

对于 $40\%$ 的数据，$1 \le n \le 10^3$。