E. Coloring Trees
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Dean has received a tree as a gift. A tree is a connected graph without cycles (there is exactly one path without repeating vertices between each pair of vertices). However, Dean's tree has a special property: its vertices are painted in 2 colors: white and black. Dean does not like to mix these two colors, so he decides to turn it into a monochromatic tree (all vertices have the same color). Of course, he wants to do this in the minimum number of steps. In each step, he can do the following:

- Select a set $$$S$$$ of vertices such that all are connected and of the same color, and change their color.

Help Dean find the minimum number of steps he needs to convert his tree.

Input

The input starts with a number $$$t$$$, the number of test cases. This is followed by the $$$t$$$ cases. Each case starts with an integer $$$n$$$, the number of vertices in the tree. This is followed by $$$n-1$$$ lines with 2 integers $$$a$$$ and $$$b$$$, $$$0 \leq a, b \leq n-1$$$ each, indicating that vertices $$$a$$$ and $$$b$$$ are connected by an edge. Next, there is a line with $$$n$$$ integers indicating the initial color of each vertex ($$$0$$$ if it is white, $$$1$$$ if it is black).

Output

Print $$$t$$$ lines, each with a single integer: the minimum number of steps Dean must take to achieve his goal in each case.

Scoring

$$$0 \leq n \leq 10$$$ (11 points)

$$$0 \leq n \leq 5000$$$ (27 points)

$$$0 \leq n \leq 100000$$$ and the tree is a chain, that is, vertex $$$i$$$ is connected to $$$i+1$$$, for all $$$i$$$ such that $$$0 \leq i \leq n-1$$$ (19 points)

$$$0 \leq n \leq 100000$$$ and the tree is a star, that is, vertex $$$0$$$ is connected to $$$i$$$, for all $$$i$$$ such that $$$1 \leq i \leq n$$$ (8 points)

$$$0 \leq n \leq 100000$$$ and there are no additional restrictions (35 points)

Example
Input
2
2
0 1
1 1
5
0 1
1 2
2 3
2 4
0 1 1 1 0
Output
0
1