Cho một đồ thị dạng cây có ~n~ đỉnh, ~n - 1~ cạnh, các đỉnh được đánh số từ ~1~ đến ~n~, mỗi đỉnh đều đã được tô màu đen hoặc trắng.

Một đường đi ~P~ gọi là tốt nếu ta thu được cây chỉ gồm đỉnh trắng sau khi áp dụng quy trình tô màu dưới đây trên đồ thị ban đầu:

• Đi dọc theo ~P~, mỗi lần đi qua một đỉnh ~u~ thì màu của ~u~ sẽ bị thay đổi (đen thành trắng, trắng thành đen).

Hãy xác định số đỉnh ít nhất của một đường đi tốt. Chú ý một đỉnh có thể đi lại nhiều lần và ban đầu luôn có ít nhất một đỉnh màu đen.

Yêu cầu: Xác định số đỉnh ít nhất của một đường đi tốt.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~2 \le n \le 5 \cdot 10^5~);
• Dòng thứ hai chứa xâu gồm ~n~ ký tự '0' hoặc '1'. Nếu ký tự thứ ~i~ bằng '0', thì ban đầu đỉnh ~i~ có màu trắng, nếu bằng '1' thì nó màu đen;
• Dòng thứ ~i~ trong ~n - 1~ dòng tiếp theo chứa hai số nguyên ~u_i~ và ~v_i~ (~1 \le u_i, v_i \le n~) mô tả cạnh nối hai đỉnh ~u_i, v_i~.

Output

Ghi ra một số nguyên là số đỉnh ít nhất của một đường đi tốt.

Sample Input 1

3
010
1 2
2 3

Sample Output 1

4

Trong ví dụ đầu tiên, một trong những đường đi tối ưu là: ~1 \to 2 \to 3 \to 2~. Quá trình tô màu diễn ra như sau: xuất phát từ đỉnh 1, đổi màu đỉnh 1 từ đen thành trắng. Đến đỉnh 2, đổi màu từ trắng thành đen. Đến đỉnh 3 đổi màu đen thành trắng. Quay lại đỉnh 2, đổi màu đen thành trắng. Như vậy ta thu được cây chỉ gồm các đỉnh trắng.

Sample Input 2

5
01100
1 2
1 5
2 3
2 4

Sample Output 2

5

Trong ví dụ thứ hai, một trong những đường đi tối ưu là: ~5 \to 1 \to 2 \to 4 \to 2~.

Ràng buộc

• Subtask 1 (27% số điểm): ~2 \le n \le 100~;
• Subtask 2 (20% số điểm): Mỗi đỉnh có bậc không quá 2;
• Subtask 3 (28% số điểm): Tất cả đỉnh đều tô màu đen từ đầu;
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.