Cho một cây vô hướng gồm $N$ đỉnh, được đánh số từ $1$ đến $N$.

Trong cây có các đỉnh đặc biệt. Chúng ta muốn thêm các cạnh vào cây để tạo thành một đường đi sao cho mọi đỉnh đặc biệt đều được ghé thăm đúng một lần. Trong quá trình này, không được phép ghé thăm bất kỳ đỉnh nào quá một lần. Các đỉnh không phải là đỉnh đặc biệt (đỉnh thường) có thể nằm trên đường đi, nhưng không bắt buộc phải ghé thăm tất cả các đỉnh thường.

Hãy tìm số lượng cạnh tối thiểu cần thêm vào để tạo ra một đường đi ghé thăm tất cả các đỉnh đặc biệt đúng một lần.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ $(1 \leq N \leq 200\,000)$.

Từ dòng thứ hai đến dòng thứ $N$, mỗi dòng chứa hai số nguyên $u, v$ biểu thị một cạnh nối giữa hai đỉnh $u$ và $v$ $(1 \leq u, v \leq N)$.

Dòng thứ $N+1$ chứa $N$ số nguyên cách nhau bởi dấu cách. Nếu số nguyên thứ $i$ là $0$, đỉnh $i$ là đỉnh thường; nếu là $1$, đỉnh $i$ là đỉnh đặc biệt.

Đồ thị được cho là một cây.

Dữ liệu ra

In ra số lượng cạnh tối thiểu cần thêm vào để tạo thành đường đi.

Ví dụ

Dữ liệu vào 1

21
1 2
1 3
2 4
2 5
3 6
3 7
3 8
3 9
4 10
5 11
5 12
6 13
6 14
10 15
10 16
13 17
16 18
16 19
17 20
17 21
0 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 1 0

Dữ liệu ra 1

4

Dữ liệu vào 2

4
1 2
2 3
3 4
0 0 0 0

Dữ liệu ra 2

0

Dữ liệu vào 3

6
1 2
1 3
2 4
3 5
6 3
1 1 0 1 1 1

Dữ liệu ra 3

1