Problem Statement

You are given a tree with $N$ vertices numbered from $1$ to $N$. The $i$-th edge connects vertex $a_i$ and vertex $b_i$.
Each vertex is painted either white or black, and the color of vertex $i$ is $c_i$, where $c_i=0$ represents white and $c_i=1$ represents black.
You may perform the following operation any number of times, possibly 0. Determine whether it is possible to make all vertices black, and if it is possible, find the minimum number of operations required.

(Operation)
Choose one $i$ satisfying $1\leq i \leq N-1$, and invert the colors of vertex $a_i$ and vertex $b_i$. That is, a black vertex becomes white, and a white vertex becomes black.

Input

$N$
$a_1~b_1$
$\vdots$
$a_{N-1}~b_{N-1}$
$c_1~\cdots~c_N$

All inputs are integers and satisfy the following constraints.

• $2\leq N \leq 2\times 10^5$
• $1\leq a_i < b_i \leq N$
• If $i\neq j$, then $(a_i, b_i)\neq(a_j, b_j)$
• $c_i$ is 0 or 1

Output

Output the minimum number of operations required to make all vertices black.
However, if it is impossible to make all vertices black no matter how many operations are performed, output -1.
Print a newline at the end.

Sample

3
1 2
2 3
0 1 0

2

3
1 2
2 3
1 0 1

-1

10
1 4
3 5
5 9
8 10
5 7
1 3
4 10
2 9
6 9
1 0 0 0 1 0 0 0 1 1

6