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

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

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

Yêu cầu: Xác định số đỉnh ít nhất của một đường đi tốt. Chú ý rằng một đỉnh có thể được đi qua nhiều lần, và ban đầu luôn tồn tại ít nhất một đỉnh màu đen.

Input

Dòng đầu tiên chứa số nguyên ~n~ (~2 ≤ n ≤ 5×10⁵~) — số đỉnh của cây.

Dòng thứ hai chứa một xâu gồm ~n~ ký tự '0' hoặc '1':

'0' nghĩa là đỉnh ban đầu có màu đen

'1' nghĩa là đỉnh ban đầu có màu trắng

~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 ≤ u, v ≤ n~) mô tả một cạnh nối đỉnh ~u~ và ~v~.

Output

Một số nguyên là số đỉnh tối thiểu của một đường đi tốt.

Test mẫu

Input

3
010
1 2
2 3

Output

4

Giải thích: Một trong những đường đi tối ưu: 1 → 2 → 3 → 2

Xuất phát từ đỉnh 1, đổi màu 1 (đen → trắng)

Đến đỉnh 2, đổi màu 2 (trắng → đen)

Đến đỉnh 3, đổi màu 3 (đen → trắng)

Quay lại đỉnh 2, đổi màu 2 (đen → trắng) → Tất cả các đỉnh đều trắng.

Input

5
01100
1 2
1 5
2 3
2 4

Output

5

Giải thích: Một trong những đường đi tối ưu: 5 → 1 → 2 → 4 → 2

Scoring

Subtask 1 (~27\%~ số điểm): ~2 ≤ n ≤ 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ả các đỉnh đều tô màu đen từ đầu

Subtask 4 (~25\%~ số điểm): Không có ràng buộc thêm