Ôi không! Đêm đến rồi, cậu bé Fabijan rất sợ bóng tối. Tồi tệ hơn nữa, đèn chùm trong phòng cậu đã bị hỏng.

Đèn chùm được làm bằng ~n~ bóng đèn được kết nối bởi ~n-1~ dây điện, vì vậy mỗi dây sẽ kết nối ~2~ bóng đèn và tất cả các bóng đèn đều liên thông, bằng dây nối trực tiếp hoặc thông qua các bóng đèn khác. Nói cách khác, bộ đèn chùm này là cây.

Mỗi bóng đèn có ~1~ nút thay đổi trạng thái của nó. Nếu bóng đèn đang tắt, nhấn nút sẽ làm đèn bật lên, và nếu bóng đèn đang bật, nhấn nút sẽ làm tắt đèn. Ban đầu, một số bóng đèn đang bật, một số khác tắt (có thể tất cả bóng đèn đều tắt). Tất cả ~n~ bóng đèn cần được bật lên để Fabijan không còn cảm thấy sợ nữa, vì chỉ khi tất cả bóng đèn được bật lên, phòng mới đủ sáng đối với Fabijan.

Fabijan sẽ chọn một dãy các bóng đèn sao cho các bóng đèn liên tiếp trên dãy được nối trực tiếp bởi một số dây đèn. Các bóng đèn có thể được chọn nhiều lần. Sau đó anh ấy sẽ đi dọc theo các bóng đèn theo thứ tự chúng xuất hiện trong dãy. Vì Fabijan rất thích nhấn nút, bất kể là bóng đèn, máy giặt, hay trong thang máy, mỗi lần anh ấy đến một bóng đèn anh sẽ nhấn nút tướng ứng với bóng đèn đó, làm thay đổi trạng thái của nó.

Hãy giúp Fabijan và xác định độ dài dãy bóng đèn ngắn nhất sao cho khi kết thúc tất cả các bóng đèn đều được bật. Ban đầu sẽ có ít nhất ~1~ bóng đèn tắt.

Input

Dòng đầu tiên chứa ~1~ số nguyên ~n~ ~(2≤5*10^5)~ , số lượng bóng đèn. Các bóng đèn được đánh số từ ~1~ đến ~n~ .

Dòng thứ hai chứa dãy ~n~ kí tự 0 hoặc 1 mô tả trạng thái ban đầu của các bóng đèn. Nếu kí tự thứ ~i~ là 0, bóng đèn thứ ~i~ đang tắt, và nếu kí tự thứ ~i~ là 1, bóng đèn đó đang bật. ~n-1~ dòng sau mỗi dòng chứa ~2~ số nguyên ~x~ và ~y~ ~(1≤x,y≤n)~ - chỉ số ~2~ bóng đèn được nối trực tiếp bằng dây.

Output

Xuất ra độ dài nhỏ nhất có thể của dãy sao cho khi kết thúc tất cả các bóng đèn đều bật.

Có thể chứng minh rằng dãy như vậy luôn luôn tồn tại.

Sample 1

Input

3
010
1 2
2 3

Output

4

Sample 2

Input

5
00000
1 2
2 3
2 4
3 5

Output

7

Sample 3

Input

5
00100
1 2
2 3
2 4
3 5

Output

8

Subtask

• ~9~ test đầu có ~2≤n≤100~
• ~5~ test sau input thỏa mãn mỗi bóng đèn được nối trực tiếp với nhiều nhất ~2~ bóng khác.
• ~7~ test sau input thỏa mãn tất cả các bóng đèn ban đầu đều tắt.
• ~9~ test cuối cùng không có điều kiện gì thêm.

Giải thích ví dụ 1:

Fabijan có thể chọn dãy ~1,2,3,2.~