Description

The CFF cave consists of n caverns connected by n-1 passageways. For every pair of caverns, there is a unique path from one to the other without leaving the cave. Explosives are placed in certain caverns. Each passageway has a fuse. In every cavern, the fuses of adjacent passageways meet at a junction. If a cavern contains explosives, the fuses are connected to them. The time it takes for the fire to burn through the fuse between two adjacent caverns is exactly one unit of time. As soon as the fire reaches a cavern with explosives, the explosives will detonate immediately.

We want to ignite the fuses at the junctions in m caverns (ignited at the fuse junctions) such that after ignition, all explosives detonate in the shortest possible time. Write a program to determine this minimum possible time.

Input Format

The first line contains two integers, n and m, representing the number of caverns in the cave and the number of fuses that can be ignited, respectively.

The next line contains n integers, d_i. If d_i=1, cavern i contains explosives; if d_i=0, it does not.

The following n-1 lines each contain two integers, a and b, indicating a passageway connecting cavern a and cavern b.

Output Format

A single integer representing the minimum time required to detonate all explosives.

```input1 7 2 1 0 1 1 0 1 1 1 3 2 3 3 4 4 5 5 6 5 7 ``` ```output1 1 ``` ## Hint

【Sample Explanation】

We can ignite the fuses in caves 3 and 5. The explosives in cave 3 are detonated at time 0, and the explosives in caves 1, 4, 6, and 7 are all detonated one unit of time later.

【Data Range】

For all data, 1 ≤ m ≤ n ≤ 3×10^5, d_i ∈ {0,1}, 1 ≤ a < b ≤ n;

For 10% of the score, n ≤ 10;

For 40% of the score, n ≤ 10^3.

Source

Adapted from POI 2011 problem