Description

You are given a tree with $n$ vertices, numbered from $1$ to $n$. Each vertex is colored either black or white. Select exactly $m$ black vertices so that the maximum distance among all pairs of selected black vertices is minimized. Output this minimal possible maximum distance.

Input Format

The first line contains two integers $n$ and $m \ (1 \leq m \leq n \leq 100)$, representing the number of vertices in the tree and the number of black vertices 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$, then vertex $i$ is black; otherwise it is white. The testdata guarantees that there are at least $m$ black vertices.

The next $n - 1$ lines each contain two integers $v_i$ and $u_i \ (1 \leq v_i, u_i \leq n)$, indicating that there is an edge between vertices $v_i$ and $u_i$ in the tree. The testdata guarantees that these edges form a tree.

Output Format

Output one integer, which is the answer.

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

Hint

In the first sample, the only possible choice is to select vertices $1$, $2$, and $4$, and the maximum distance is $2$.

In the second sample, one feasible choice is to select vertices $1$, $3$, $8$, and $9$. The maximum distance is the distance between vertices $3$ and $9$.

Translated by ChatGPT 5