There is an undirected tree consisting of $N$ vertices, labeled from $1$ to $N$.

The tree contains special vertices. We want to add edges to the tree to create a path that visits every special vertex exactly once. In this path, no vertex may be visited more than once. Non-special vertices (regular vertices) may be included in the path, but it is not necessary to visit all regular vertices.

Find the minimum number of edges that must be added to create a path that visits every special vertex exactly once.

Input

The first line contains the number of vertices $N$. $(1 \leq N \leq 200\,000)$

The next $N-1$ lines each contain two integers $u$ and $v$, representing an edge between vertex $u$ and vertex $v$. $(1 \leq u, v \leq N)$

The $(N+1)$-th line contains $N$ integers separated by spaces. If the $i$-th integer is $0$, vertex $i$ is a regular vertex; if it is $1$, vertex $i$ is a special vertex.

The graph provided in the input is a tree.

Output

Output the minimum number of edges required to create the path.

Examples

Input 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

Output 1

4

Input 2

4
1 2
2 3
3 4
0 0 0 0

Output 2

0

Input 3

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

Output 3

1