Nhà máy điện JOI có $N$ cơ sở được đánh số từ $1$ đến $N$. Các cơ sở được nối với nhau bởi $N-1$ dây dẫn. Dây dẫn thứ $i$ ($1 \le i \le N-1$) nối cơ sở $A_i$ và cơ sở $B_i$ theo cả hai chiều. Có thể đi từ bất kỳ cơ sở nào đến bất kỳ cơ sở nào khác bằng cách đi qua một số dây dẫn.

Mỗi cơ sở của nhà máy điện JOI có nhiều nhất một máy phát điện. Mỗi máy phát điện có một công tắc. Ban đầu, công tắc của mọi máy phát điện đều ở trạng thái TẮT. Bạn là giám đốc nhà máy điện JOI. Bạn có thể chọn một số máy phát điện và chuyển công tắc của các máy đã chọn sang trạng thái BẬT. (Bạn được phép không chọn máy nào.) Các máy phát điện có những tính chất sau.

• Giả sử các cơ sở $x,y,z$ đều có máy phát điện. Đồng thời, giả sử có thể đi từ cơ sở $x$ đến cơ sở $y$, rồi từ cơ sở $y$ đến cơ sở $z$ theo thứ tự đó mà không đi qua cùng một dây dẫn hai lần. Nếu công tắc của các máy phát điện tại cơ sở $x$ và $z$ đều BẬT thì máy phát điện tại cơ sở $y$ sẽ bị hỏng.
• Một máy phát điện sẽ hoạt động nếu công tắc của nó BẬT và nó không bị hỏng.

Cuối cùng, bạn sẽ nhận được tiền thưởng từ các máy phát điện đang hoạt động. Bạn nhận được 1 yên cho mỗi máy phát điện đang hoạt động. Tuy nhiên, bạn cũng phải trả chi phí sửa chữa cho các máy phát điện bị hỏng. Bạn phải trả 1 yên cho mỗi máy phát điện bị hỏng. Tổng tiền thưởng trừ tổng chi phí sửa chữa là lợi nhuận của bạn.

Hãy viết chương trình, khi biết cách bố trí các cơ sở và dây dẫn cùng thông tin về các máy phát điện, tính lợi nhuận lớn nhất của bạn.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

$$ \begin{array}{ll} N\\ A_1&B_1\\ \vdots\\ A_{N-1}&B_{N-1}\\ S \end{array} $$

Ở đây, $S$ là một xâu độ dài $N$ biểu diễn các máy phát điện tại các cơ sở. Mỗi ký tự của $S$ là 0 hoặc 1. Ký tự thứ $i$ ($1 \le i \le N$) mô tả máy phát điện tại cơ sở $i$. Ký tự đó là 0 nếu cơ sở $i$ không có máy phát điện và là 1 nếu cơ sở $i$ có máy phát điện.

Dữ liệu ra

Ghi một dòng ra đầu ra chuẩn. Dòng này phải chứa lợi nhuận lớn nhất của bạn khi chọn một số máy phát điện và chuyển tất cả công tắc của các máy đã chọn sang trạng thái BẬT.

Giới hạn

• $1 \le N \le 200\,000$.
• $1 \le A_i \le N$ ($1 \le i \le N-1$).
• $1 \le B_i \le N$ ($1 \le i \le N-1$).
• $A_i \ne B_i$ ($1 \le i \le N-1$).
• Có thể đi từ bất kỳ cơ sở nào đến bất kỳ cơ sở nào khác bằng cách đi qua một số dây dẫn.
• $S$ là một xâu độ dài $N$ chỉ gồm 0 và 1.
• $S$ chứa ít nhất một ký tự 1.

Nhiệm vụ con

1. (6 điểm) $N \le 16$.
2. (41 điểm) $N \le 2\,000$.
3. (53 điểm) Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

6
2 3
4 3
1 3
3 5
6 2
110011

Dữ liệu ra 1

3

Ghi chú

Trong ví dụ này, các cơ sở $1,2,5,6$ có máy phát điện.

Nếu bạn chuyển công tắc tại các cơ sở $1,2,5$ sang BẬT thì các máy phát điện tại cơ sở $1,2,5$ sẽ hoạt động và bạn nhận được 3 yên. Vì không phải trả chi phí sửa chữa, lợi nhuận của bạn là 3 yên. Đây là lợi nhuận lớn nhất nên hãy in 3.

Mặt khác, nếu bạn chuyển công tắc tại các cơ sở $1,5,6$ sang BẬT thì máy phát điện tại cơ sở $2$ sẽ bị hỏng, còn các máy phát điện tại cơ sở $1,5,6$ sẽ hoạt động. Bạn nhận được 3 yên và phải trả 1 yên chi phí sửa chữa. Do đó, lợi nhuận của bạn là 2 yên.

Nếu bạn chuyển công tắc tại các cơ sở $1,2,5,6$ sang BẬT thì máy phát điện tại cơ sở $2$ sẽ bị hỏng, còn các máy phát điện tại cơ sở $1,5,6$ sẽ hoạt động. Bạn nhận được 3 yên và phải trả 1 yên chi phí sửa chữa. Do đó, lợi nhuận của bạn là 2 yên.

Dữ liệu vào 2

8
1 2
3 5
6 4
4 5
5 2
7 2
2 8
11111111

Dữ liệu ra 2

3

Dữ liệu vào 3

16
7 10
5 11
9 4
14 12
2 11
14 16
4 2
1 13
11 3
7 1
15 9
2 1
11 6
14 9
8 9
0111111001001110

Dữ liệu ra 3

5