You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

众所周知，徐老师很喜欢画关于树的画，最近不是很空嘛（为什么很空？参见徐老师的春秋大梦）于是他反手就画出了一棵有 $n$ 个结点根为 $1$ 的树。

然后他随意的把这 $n$ 个节点随机染成黑色或者白色。

现在他想知道，在这棵树上任意选择恰好 $m$ 个黑色节点，这 $m$ 个黑色节点之间的距离的最大值最小是多少？

输入格式

第一行输入两个整数 $n,m$,，分别代表结点的个数以及你需要选取的黑色结点的个数。

接下来的一行输入 $n$ 个整数 $a_1,a_2 \dots a_n$ 。 如果 $a_i = 1$，那么说明第 $i$ 个结点是黑色的，否则则是白色的。

接下来 $n - 1$ 行，每行包含两个整数 $x,y$ 表示 $x,y$ 之间存在一条双向边。

输出格式

输出一行，代表答案。

样例

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

2

样例解释

在第一组样例中，选择结点 $1,2,4$ 或者 $1,5,6$，他们的距离最大值是 $2$。

数据范围

特别的保证：输入的数据保证黑色结点至少有 $m$ 个，并且输入的数据一定是一棵树。