Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

In a red-blue tree, each vertex is either red or blue and adjacent vertices always have different colours.

You are given a tree with $N$ vertices (numbered $1$ through $N$). It is not necessarily a red-blue tree, but its vertices are still coloured red and blue. You may perform the following operation any number of times (including zero): choose two adjacent vertices and swap their colours.

Find the smallest number of operations required to transform the tree into a red-blue tree or determine that it is impossible.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N-1$ lines follow. Each of these lines contains two space-separated integers $u$ and $v$ denoting that vertices $u$ and $v$ are connected by an edge.
The last line contains a string $S$ with length $N$. For each valid $i$, the $i$-th character of this string is either '0' if the $i$-th vertex is initially red or '1' if it is initially blue.

------ Output ------
Print a single line containing one integer ― the smallest number of operations or $-1$ if it is impossible to transform the tree into a red-blue tree.

------ Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100,000$
$1 ≤ u, v ≤ N$
$S$ contains only characters '0' and '1'
the sum of $N$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------
1

7

1 2

1 3

2 4

2 5

3 6

3 7

0010010
----- Sample Output 1 ------
3
----- explanation 1 ------
Example case 1: We can perform the following operations:
- Swap the colours of vertices $1$ and $3$; the string of colours becomes "1000010".
- Swap the colours of vertices $1$ and $2$; the string of colours becomes "0100010".
- Swap the colours of vertices $6$ and $3$; the string of colours becomes "0110000", so the tree is a red-blue tree.

见题面

见题面