Problem Description

Given a tree with $n$ nodes, numbered from $1$ to $n$. Each node is either black or white. Select exactly $m$ black nodes such that the maximum distance between any two black nodes is minimized. Output this minimum maximum distance.

Input Format

The first line contains two integers $n$ and $m \ (1 \leq m \leq n \leq 100)$, representing the number of nodes in the tree and the number of black nodes to be selected.

The second line contains $n$ integers $p_1, p_2, \dots, p_n \ (0 \leq p_i \leq 1)$. If $p_i=1$, node $i$ is black; otherwise, it is white. It is guaranteed that there are at least $m$ black nodes.

The next $n-1$ lines each contain two integers $v_i$ and $u_i \ (1 \leq v_i, u_i \leq n)$, representing an edge connecting node $v_i$ and node $u_i$ in the tree. It is guaranteed that these edges form a tree.

Output Format

Output a single integer, representing the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2

Sample Input #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

Sample Output #2

5

Notes

In the first sample, the only way to select nodes is to choose nodes $1, 2$, and $4$, with a maximum distance of $2$.

In the second sample, one possible selection is nodes $1, 3, 8$, and $9$, with the maximum distance being the distance between nodes $3$ and $9$.

见题面 Input 部分

见题面 Output 部分