Marisa's garden can be represented as a tree with $n$ vertices. She has planted trees at some of the vertices.
She needs to install an irrigation system with $m$ water sprinklers at $m$ vertices. Each second, if a vertex has water, the water flows to its adjacent vertices. Help Marisa find the optimal way to install the sprinklers so that it takes the least amount of time for all vertices with trees to be watered.
### Input
- The first line contains two integers $n$ and $m$.
- The second line contains $n$ integers, either $0$ or $1$. The $i$-th integer is $1$ if there is a tree at vertex $i$, and $0$ otherwise.
- The next $n-1$ lines each contain two integers $u$ and $v$, indicating that there is an edge between vertex $u$ and vertex $v$.
### Output
- Print a single integer representing the minimum time required for all the trees to be watered.
### Constraints
- $1 \leq m \leq n \leq 3 \times 10^5$.
- $1 \leq u < v \leq n$.
### Example
Input:
```
7 2
1 0 1 1 1 1 0
5 7
1 3
4 5
5 6
2 3
3 4
```
Output:
```
1
```
### Subtasks
- $10\\%$ of the tests have $n \le 10$.
- $40\\%$ of the tests have $n \le 1000$.
- The remaining tests have no additional constraints.
