题目描述

给定一棵 $n$ 个点的树，点的编号从 $1$ 到 $n$。每个点有黑色或白色的颜色。选出恰好 $m$ 个黑点，使得黑点两两之间的距离的最大值最小。输出这个最小的最大值。

输入格式

第一行包含两个整数 $n$ 和 $m \ (1 \leq m \leq n \leq 100)$，代表树的点数和要选出的黑点数量。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n \ (0 \leq p_i \leq 1)$。如果 $p_i=1$ 则点 $i$ 是黑色的，否则是白色的。数据保证黑点有不少于 $m$ 个。

接下来 $n-1$ 行每行包含两个整数 $v_i$ 和 $u_i \ (1 \leq v_i, u_i, \leq n)$，代表树上有一条连接点 $v_i$ 和 $u_i$ 的边。数据保证这些边构成一棵树。

输出格式

输出一个整数，代表答案。

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

2

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

5

提示

第一个样例中，唯一的选法是选点 $1, 2$ 和 $4$，距离的最大值为 $2$。

第二个样例中，可行的一种选法是选点 $1, 3, 8$ 和 $9$，最大的距离是点 $3$ 和 $9$ 的距离。