Trời đã tối cậu bé Fabian sợ bóng tối mà chiếc đèn chùm trong phòng của cậu lại bị hỏng. Đèn chùm được tạo thành từ \(n\) bóng đèn nối với nhau bằng \(n - 1\) dây, sao cho mỗi dây nối hai bóng đèn và tất cả các bóng đèn được kết nối trực tiếp hoặc thông qua bóng đèn khác. Nói cách khác, đèn chùm là một cây.

Mỗi bóng đèn có một nút thay đổi trạng thái của nó. Nếu bóng đèn tắt, nhấn nút nó sẽ bật, và nếu nó bật, nhấn nút nó sẽ tắt. Lúc đầu, một số bóng đèn bật và một số bóng đèn tắt (có thể tất cả đều bị tắt). Cần phải bật tất cả \(n\) bóng đèn lên để Fabian không còn sợ hãi nữa, vì chỉ sau đó sẽ có đủ ánh sáng trong phòng.

Fabian sẽ chọn một số dãy bóng đèn sao cho các bóng đèn liên tiếp trong dãy đó được kết nối trực tiếp bằng một số dây. Bóng đèn có thể được lặp lại. Sau đó anh ta sẽ đi vòng quanh các bóng đèn theo thứ tự chúng xuất hiện trong dãy và bấm nút tương ứng một lần thay đổi trạng thái của nó.

Yêu cầu: Hãy giúp Fabian xác định độ dài của dãy bóng đèn ngắn nhất sao cho cuối cùng tất cả các bóng đèn đều được bật. Ban đầu sẽ có ít nhất một bóng đèn bị tắt.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên \(n ( 2 ≤ n ≤ 500000) \) là số bóng đèn. Bóng đèn được dán nhãn bằng số nguyên từ 1 đến \(n\).

• Dòng thứ hai chứa một dãy gồm \(n\) ký tự \('0'\) và \('1'\). Nếu ký tự thứ \(i\) bằng \('0'\), thì lúc đầu bóng đèn thứ \(i\) tắt và nếu nó bằng \('1'\) thì nó sẽ sáng.

• Mỗi dòng trong số \(n - 1\) dòng sau chứa hai số nguyên \(x\) và \(y (1 ≤ x,y ≤ n)\) – nhãn của bóng đèn được nối trực tiếp bằng dây.

Kết quả:

• Ghi độ dài tối thiểu có thể có của chuỗi sao cho cuối cùng tất cả các bóng đèn đều được bật.

Ràng buộc:

• Subtask 1 (18% test): \(2 ≤ n ≤ 100\)

• Subtask 2 (27% test): Mỗi bóng đèn được nối trực tiếp với tối đa hai bóng đèn khác.

• Subtask 3 (28% test): Tất cả các bóng đèn đều được tắt ngay từ đầu.

• Subtask 4 (27% test): Không có ràng buộc thêm

Sample Input

3
010
1 2
2 3

Sample Output

4

Giải thích:

• Fabian có thể chọn trình tự 1, 2, 3, 2