Tôm có một cái đèn chùm gồm có N bóng đèn nhỏ đánh số từ 1 đến N, các bóng đèn nhỏ được nối với nhau bởi N-1 dây dẫn, mỗi dây dẫn sẽ nối trực tiếp hai bóng đèn nhỏ. Các dây được thiết kế sao cho giữa hai bóng đèn nhỏ bất kì đều được nối với nhau thông qua một số dây dẫn trực tiếp hoặc gián tiếp. Ở mỗi bóng đèn nhỏ có một công tắc bật (tắt), nếu bấm vào công tắc thì đèn đó đang sáng sẽ tắt và ngược lại đang tắt sẽ sáng. Ban đầu, có một số (lớn hơn 0) bóng đèn nhỏ ở trạng thái tắt. Tôm cần chọn ra một dãy các bóng đèn nhỏ sao cho giữa hai bóng đèn liên tiếp được chọn sẽ có dây dẫn trực tiếp, lưu ý trong dãy bóng này, các bóng đèn có thể lặp lại. Sau đó, Tôm lần lượt đi qua hết các bóng đèn theo thứ tự đã chọn, đi tới đâu Tôm sẽ bấm công tắc một lần ở bóng đèn đó, kết thúc một lượt bấm công tắc như vậy thì tất cả N bóng đèn nhỏ sẽ ở trạng thái bật sáng.

Yêu cầu: Chọn dãy bóng đèn nhỏ như mô tả trên sao cho dãy đó có độ dài ngắn nhất.

Dữ liệu: Vào từ tệp văn bản DENCHUM.INP theo khuôn dạng:

• Dòng đầu ghi số nguyên dương N (N ≤ 100);
• Dòng thứ hai chứa một xâu kí tự độ dài N, chỉ gồm các kí tự '0' hoặc '1'. Kí tự thứ i bằng '1' tức là bóng đèn thứ i ban đầu đang sáng, ngược lại bằng '0' tức là bóng đèn thứ i ban đầu tắt (với mọi i = 1..N).
• Mỗi dòng trong N-1 dòng tiếp theo ghi 2 số u, v (1 ≤ u, v ≤ N) mô tả có một dây dẫn trực tiếp giữa u và v.

  Kết quả: Ghi ra tệp văn bản DENCHUM.OUT một số nguyên duy nhất là độ dài của dãy bóng đèn tìm được theo yêu cầu. Dữ liệu đảm bảo luôn tồn tại đáp án.

Ví dụ:

DENCHUM.INP 
5
00100
1 2
2 3
2 4
3 5 
DENCHUM.OUT 
8   
Giải thích ví dụ
Dãy bóng đèn có độ dài bằng 8 tìm được là: 
1 2 4 2 3 5 3 2

Ràng buộc:

• Có 3 điểm có N ≤ 20.
• Có 3 điểm còn lại không có ràng buộc gì thêm.