Bạn được cho một cây có \(n\) đỉnh, mỗi đỉnh đều có màu trắng hoặc màu đen. Hãy chọn chính xác \(m\) đỉnh màu đen sao cho khoảng cách lớn nhất giữa \(2\) đỉnh màu đen là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m(2 \leq m \leq n \leq 100)\) - số đỉnh của đồ thị và số đỉnh màu đen bạn phải chọn.
• Dòng thứ hai chứa \(n\) số nguyên \(p_1, p_2, ..., p_n(0 \leq p_i \leq 1)\). Nếu \(p_i=1\) thì nút thứ \(i\) có màu đen, \(p_i=0\) thì nút có màu trắng.
• \(n-1\) dòng tiếp theo chứa hai số nguyên dương \(u_i\) và \(v_i(1 \leq u_i, v_i \leq n)\), giữa hai đỉnh \(u_i\) và \(v_i\) có cạnh nối.
• Input luôn đảm bảo có cách chọn \(m\) đỉnh màu đen từ đồ thị.

Output

• Giá trị nhỏ nhất khoảng cách lớn nhất trong các cách chọn \(m\) đỉnh màu đen.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(m = 2\).
• Subtask \(2\) (\(60\%\) số điểm): \(m > 2\).

Example

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

2