Cho một đồ thị cây gồm ~n~ đỉnh, mỗi đỉnh được tô một trong hai màu, trắng hoặc đen. Trên đồ thị cây này ta định nghĩa một thao tác ~changeColor(u)~ với ~u~ là một đỉnh bất kì của cây, thao tác này có tác dụng đổi màu tất cả các đỉnh ~v~ mà tất cả các đỉnh nằm trên đường đi ngắn nhất từ ~u~ đến ~v~ (kể cả ~u, v~) có cùng một màu.

Bạn hãy tìm cách sử dụng ít thao tác ~changeColor~ nhất sao cho tất cả các đỉnh của cây có cùng một màu.

Yêu cầu: Tìm số thao tác ít nhất để đưa toàn bộ các đỉnh của cây về cùng một màu.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 2 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~c_i~ (~0 \le c_i \le 1~) tương ứng là màu của các đỉnh, ~c_i = 0~ ứng với màu trắng, ~c_i = 1~ ứng với màu đen.
• Tiếp theo có ~n - 1~ dòng, mỗi dòng gồm 2 số nguyên ~u, v~ (~1 \le u, v \le n~) miêu tả một cạnh của đồ thị.

Output

• Ghi ra một dòng duy nhất là số thao tác ít nhất cần thực hiện để đưa toàn bộ các đỉnh của cây về cùng một màu.

Sample Input 1

11
0 0 0 1 1 0 1 0 0 1 1
1 2
1 3
2 4
2 5
5 6
5 7
3 8
3 9
3 10
9 11

Sample Output 1

2

Sample Input 2

4
0 0 0 0
1 2
2 3
3 4

Sample Output 2

0